[Haskell-cafe] Optimization problem

[Ross Paterson]

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.