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
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
