[Haskell-cafe] Optimization problem
Magnus Jonsson
magnus at smartelectronix.com
Wed Sep 13 20:26:16 EDT 2006
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
>
More information about the Haskell-Cafe
mailing list