Re: [Haskell-cafe] Optimization problem

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