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

[Lennart Augustsson]

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 <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
>
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://www.haskell.org/mailman/listinfo/libraries