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]