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

[Duncan Coutts]

On Wed, 2007-03-21 at 16:18 +0100, Nils Anders Danielsson wrote:
> On Tue, 20 Mar 2007, Duncan Coutts <duncan.coutts at worc.ox.ac.uk> wrote:

> Well, the report says (about the Prelude, but I think the same applies
> to the libraries):
> 
>   "It constitutes a specification for the Prelude. Many of the
>   definitions are written with clarity rather than efficiency in mind,
>   and it is not required that the specification be implemented as
>   shown here."
> 
> I interpret this as "you can change (optimise) the definitions, but
> the user shouldn't be able to observe the difference (except by
> measuring resource usage)". What else could "specification" mean?

In particular does that mean that an implementation must have *exactly*
the same strictness as given in the report? It never says explicitly.
Probably it should mean that, but in that case there are a handful of
cases where the report needs to be fixed. There are a couple cases where
the report is stricter than is necessary and conversely a couple cases
where it is lazier than was probably really indented.

I will set out the detail on this to the libraries and haskell' list
soonish.

> I'd say you still need to define a function observationally equivalent
> to the one given in the report.

Then we would really have to use insertion sort, not quicksort, or
mergesort or heapsort. I don't think that's what the spec intends.

It does after all say for the various *By functions that we can assume
the passed function is an equivalence or a total order:

        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.

It also defines sort = sortBy compare and nub = nubBy (==) so we can
also assume that Eq is an equivalence and Ord instance is a total order
for the purposes of defining sort, nub etc. But only for those library
functions, not in general.

Duncan