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

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, 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 :

...

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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe