[Haskell-cafe] Optimization problem

[Magnus Jonsson]

Nice try Twan but your example fails on infinite lists. I cleaned up 
your example so that it compiles:

import qualified Data.Map as Map

splitStreamsMap :: Ord a => [(a,b)] -> Map.Map a [b]
splitStreamsMap = foldl add Map.empty
   where add m (a,b) = Map.insertWith (++) a [b] m

splitStreams :: Ord a => [(a,b)] -> [(a,[b])]
splitStreams = Map.toList . splitStreamsMap

It fails to return a value on this test:

take 2 $ snd $ head $ splitStreams (map (\x -> (0 ,x)) [1..])

/ Magnus

On Thu, 14 Sep 2006, Twan van Laarhoven wrote:

> 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
>