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

On Tue, 2007-03-20 at 14:11 +0100, Nils Anders Danielsson wrote:

On Tue, 20 Mar 2007, Duncan Coutts 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