[email@example.com: Re: [GHC] #1218: Add sortNub and sortNubBy
duncan.coutts at worc.ox.ac.uk
Wed Mar 21 18:17:41 EDT 2007
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
> 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.
More information about the Libraries