Adrian Hey
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