[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:

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

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 other words we can assume Ord is a total order (for non-_|_ values)
> for the purposes of defining sort [...]

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

-- 
/NAD