[Haskell-cafe] Re: (flawed?) benchmark : sort
ketil at malde.org
Wed Mar 12 05:40:17 EDT 2008
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
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.
If I haven't seen further, it is by standing in the footprints of giants
More information about the Haskell-Cafe