[Haskell-cafe] Re: (flawed?) benchmark : sort

Krzysztof Skrzętnicki gtener at gmail.com
Wed Mar 12 19:53:08 EDT 2008


In OCaml you have sort and fastsort - the latter doesn't have to be stable.
It currently is, because fastsort = sort.
I think it is a good thing to leave people an option, if there is something
important to choose.

On Thu, Mar 13, 2008 at 12:48 AM, <ajb at spamcop.net> wrote:

> G'day all.
>
> Adrian Hey wrote:
>
> >> This might be a reasonable thing to say about *sortBy*, but not sort
> >> as the ordering of equal elements should not be observable (for any
> >> correct instance of Ord). It should be impossible to implement a
> >> function which can discriminate between [a,a],[a,b],[b,a],[b,b] if
> >> compare a b = EQ.
>
> Nonsense.  Consider a Schwartzian transform wrapper:
>
> data OrdWrap k v = OrdWrap k v
>
> instance (Ord k) => Ord (OrdWrap k v) where
>     compare (OrdWrap k1 v1) (OrdWrap k2 v2) = OrdWrap k1 k2
>
> It would be incorrect (and not sane) for sort [a,b] to return [a,a] in
> this case, though a case could be made that either [a,b] or [b,a] make
> sense.
>
> Quoting Jules Bean <jules at jellybean.co.uk>:
>
> > Stability is a nice property. I don't understand why you are arguing
> > against this so aggressiviely.
>
> Stability is an occasionally very useful property.  However, if there
> is a tradeoff between stability and performance, I'd prefer it if the
> library didn't choose for me.
>
> Cheers,
> Andrew Bromage
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20080313/5bb33bbe/attachment.htm


More information about the Haskell-Cafe mailing list