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

[Duncan Coutts]

On Tue, 2007-03-20 at 14:11 +0100, Nils Anders Danielsson wrote:
> 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.

Aye.

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

Actually it's fine. The library report states that:

        When the "By" function replaces an Eq context by a binary
        predicate, the predicate is assumed to define an equivalence;
        when the "By" function replaces an Ord context by a binary
        predicate, the predicate is assumed to define a total ordering.

So we can assume they're ok for the specification of those List module
functions but as you say, beyond that we can't make any hard
assumptions.

In other words we can assume Ord is a total order (for non-_|_ values)
for the purposes of defining sort but not for rules like:
  sort . nub = sortDiscardingDuplicates
So Lennart is allowed to keep his bogus Eq instances, we have to promise
not to break his programs, although the implementation of the sort
function doesn't have to sort his values correctly (since presumably
it's allowed to use == as well as <= >= etc).

So can anyone break this hypothesis?

  nub . sort = map head . group . sort

ie sort first then discard duplicates?


Duncan