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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
