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

[Don Stewart]

dan.doel:
> On Sunday 09 March 2008, Krzysztof Skrzętnicki wrote:
> > Ok, I did some search and found Data.Map, which can be used to implement
> > pretty fast sorting:
> >
> > import qualified Data.Map as Map
> >
> > treeSort :: Ord a => [a] -> [a]
> > treeSort = map (\(x,_) -> x ) . Map.toAscList . Map.fromList . map
> > (\x->(x,()))
> >
> > In fact It is likely to behave like sort, with the exception that it is 23%
> > faster. I did not hovever check the memory consumption. It works well on
> > random, sorted and reverse-sorted inputs, and the speed difference is
> > always about the same. I belive I could take Data.Map and get datatype
> > isomorphic to specialized *Data.Map a ()* of it, so that treeSort will
> > became Map.toAscList . Map.fromList. This may also bring some speedup.
> >
> > What do you think about this particular function?
> 
> Some thoughts:
> 
> 1) To get your function specifically, you could just use Data.Set.Set a 
> instead of Map a ().
> 
> 2) What does it do with duplicate elements in the list? I expect it deletes 
> them. To avoid this, you'd need to use something like fromListWith, keeping 
> track of how many duplicates there are, and expanding at the end.

And a little QuickCheck to help things along:

    import qualified Data.Map as Map
    import Data.List
    import Test.QuickCheck

    treeSort :: Ord a => [a] -> [a]
    treeSort = map (\(x,_) -> x ) . Map.toAscList . Map.fromList . map (\x->(x,()))

    main = quickCheck prop_sort

    prop_sort xs = sort xs == treeSort xs
        where _ = xs :: [Int]

Running:

    $ runhaskell A.hs
    Falsifiable, after 11 tests:
    [-2,-2,5]