[Haskell-cafe] Re: (flawed?) benchmark : sort
dan.doel at gmail.com
Mon Mar 10 08:45:31 EDT 2008
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.
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.
More information about the Haskell-Cafe