[Haskell-cafe] Optimization problem

[Twan van Laarhoven]

Magnus Jonsson wrote:
> Dear Haskell Cafe,
> 
> When programming the other day I ran into this problem. What I want to 
> do is a function that would work like this:
> 
> splitStreams::Ord a=>[(a,b)]->[(a,[b])]
> 
>> splitStreams [(3,x),(1,y),(3,z),(2,w)]
> 
> [(3,[x,z]),(1,[y]),(2,[w])]

A O(n log(n)) algorithm is easy if you use Data.Map:

 > import qualified Data.Map as Map
 >
 > splitStreamsMap :: Ord a => [(a,b)] -> Map.Map a [b]
 > splitStreamsMap = foldl add Map.empty
 >  where add (a,b) m = Map.insertWith (++) a [b]
 >
 > splitStreams = Map.fromList . splitStreamsMap

Twan