[firstname.lastname@example.org: Re: [GHC] #1218: Add sortNub and sortNubBy to
lennart at augustsson.net
Wed Mar 21 19:41:37 EDT 2007
Of course it means that a function must have exactly the same
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
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>
>> Well, the report says (about the Prelude, but I think the same
>> to the libraries):
>> "It constitutes a specification for the Prelude. Many of the
>> definitions are written with clarity rather than efficiency in
>> 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
> 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
> 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
>> 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
> 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
> for the purposes of defining sort, nub etc. But only for those library
> functions, not in general.
> Libraries mailing list
> Libraries at haskell.org
More information about the Libraries