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.