[Haskell-cafe] Optimization problem
Ross Paterson
ross at soi.city.ac.uk
Thu Sep 14 11:56:37 EDT 2006
Here's my attempt, also using the quicksort idea, but using two passes
instead of tying the knot:
> import Data.Set hiding (map)
First a binary search tree, with a lookup function:
> data Tree k v = Node (Tree k v) k v (Tree k v)
> get :: Ord a => a -> Tree a b -> b
> get a (Node l k v r) = case compare a k of
> LT -> get a l
> EQ -> v
> GT -> get a r
There's no empty case: we'll ensure that we only search for keys that
are in the tree.
Now to make a tree of lists from the list of pairs:
> mkTree :: Ord a => [(a,b)] -> Tree a [b]
> mkTree [] = error "unused"
> mkTree ((a,b):abs) = Node l a (b:bs) r
> where l = mkTree [(a',b') | (a',b') <- abs, a' < a]
> r = mkTree [(a',b') | (a',b') <- abs, a' > a]
> bs = [b' | (a',b') <- abs, a' == a]
It remains to extract from this tree the list of second elements
corresponding to the each distinct first element in the input list:
> splitStreams :: Ord a => [(a,b)] -> [(a,[b])]
> splitStreams abs = [(a, get a t) | a <- uniq (map fst abs)]
> where t = mkTree abs
where uniq computes the list of unique elements of a list:
> uniq :: Ord a => [a] -> [a]
> uniq = u empty
> where u s [] = []
> u s (x:xs)
> | member x s = u s xs
> | otherwise = x : u (insert x s) xs
There's no rebalancing, so it suffers from the same problems as
quicksort.
More information about the Haskell-Cafe
mailing list