10 Mar
2008
10 Mar
'08
8:45 a.m.
On Monday 10 March 2008, Neil Mitchell wrote:
That would be wrong. Consider:
data Foo = Foo Int Int
instance Ord Foo where compare (Foo a _) (Foo b _) = compare a b
sort [Foo 1 2, Foo 1 -2] must return the original list back, in that order. You cannot delete things and duplicate them later. To guarantee the ordering you must also do other stuff.
Ah! Quite right. So, instead, we'd have to store the elements themselves. Something like: treeSort = concatMap (reverse . snd) . Map.toAscList . Map.fromListWith (++) . map (\x -> (x,[x])) I had a feeling the duplicate counting one wasn't the correct answer, but your example slipped my mind last night. -- Dan