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