[Haskell-cafe] Optimization problem
Twan van Laarhoven
twanvl at gmail.com
Wed Sep 13 19:53:23 EDT 2006
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
More information about the Haskell-Cafe
mailing list