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

[Ketil Malde]

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?

For types where there is no observable difference between EQ elements
(which you know when you instantiate Ord for the type), 'sort [a,b]'
could return [a,a] when a == b, saving you space.  For types with
observably different but EQual values (like Neil's (Foo Int
(Int->Int))), you would need to fall back to the old behavior.

Just wondering.

-k
-- 
If I haven't seen further, it is by standing in the footprints of giants