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