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