[email@example.com: Re: [GHC] #1218: Add sortNub and sortNubBy to
Nils Anders Danielsson
nad at cs.chalmers.se
Tue Mar 20 09:11:41 EDT 2007
On Tue, 20 Mar 2007, Duncan Coutts <duncan.coutts at worc.ox.ac.uk> wrote:
> H98 requires that Eq and Ord be equality classes and total orders
Does it? I was under the impression that a compiler can never assume
that any laws hold of any user-defined instances (to do optimisations,
The report states the following:
"The Eq class provides equality (==) and inequality (/=) methods."
"The Ord class is used for totally ordered datatypes."
I interpret this as being mere usage guidelines, and nothing more.
What would it mean to state that Ord is a total order, by the way?
Should (<=) always return True or False, never ⊥? In that case there
is only one implementation of (<=): const (const True).
> So one could say that we can't really rely on any laws that should go
> along with type class instances, but that's clearly not right since then
> we cannot sort!
Libraries can of course depend on various laws (hopefully this
dependence is explicit in the documentation). I guess you can argue
whether rewrite rules are part of the compiler or the library. To me a
rewrite rule is fishy unless the two sides are observationally
> If we cannot rely on Ord then the current Data.List.sort implementation
> is wrong because it gives different answers from the H98 spec sort when
> the Ord instance is not a total order (this is easiest to see with
Then I would say it is wrong (according to H98), yes.
More information about the Libraries