[Haskell-cafe] Re: (flawed?) benchmark : sort

[Dan Doel]

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