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

Of course it means that a function must have exactly the same strictness. If it doesn't have the same strictness it's not the same function. I agree the report should be fixed where the functions in the report do not have the appropriate strictness. But this is a change to the report. -- Lennart On Mar 21, 2007, at 22:17 , Duncan Coutts wrote:

On Wed, 2007-03-21 at 16:18 +0100, Nils Anders Danielsson wrote:

...

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

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries