[trac@galois.com: Re: [GHC] #1218: Add sortNub and sortNubBy to Data.List]

[Nils Anders Danielsson]

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,
for instance).

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
equivalent, though.

> 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
> sortBy).

Then I would say it is wrong (according to H98), yes.

-- 
/NAD