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

[Adrian Hey]

Ketil Malde wrote:
> Adrian Hey <ahey at iee.org> writes:
> 
>> So really I think the docs have this backwards. It's sortBy that
>> implements a stable sort (assuming a suitably sane comparison function
>> I guess) and apparently sort is whatever you get from (sortBy compare).
>> But this is unduly restrictive on possible correct sort implementations
>> IMO.
> 
> Somebody (maybe you?) suggested that 'sort' should be a function in
> class Ord, giving the implementer freedom to decide exactly what is
> optimal for that particular data type.
> 
> Could this also be used to solve the Data.Map issue?  I mean, could
> Data.Map.insert use 'sort' instead of 'compare' to place new elements?

I don't really think so. To be consistent people would have to do this
all over the place, not just in Data.Map/Set. Anywhere where you have
code like this (for Ord instances)

if (x==y) then f x -- f y should be just as good!
           else g x y

you'd now have to have something like..

if (x==y) then f (head (sort ([x,y]))
           else g x y

Also, since the problem is with the concept of equality, in that we're
now admitting that things can be equal but also not equal at the same
time then choice should really be a method of the Eq class..

Something like..

-- Returns Nothing if args are not equal
--         Just p if args are equal, where p is the prefered equal value
chose :: Eq a => a -> a -> Maybe a

Like I said, this way lies madness!!

Regards
--
Adrian Hey