[Haskell-cafe] Optimization problem

[Magnus Jonsson]

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

I don't care about the order that the pairs are output, so the answer 
could just as well be [(2,[w],(3,[x,z]),(1,[y])]. However I do care about 
the order of the xyzw:s, so (3,[z,x]) could not be part of the solution in 
this example.

Furthermore it should work on infinite lists. It can't eat the whole 
list before producing any output.

Now, it's not too hard to come up with an inefficient solution that 
traverses the input list multiple times. For example a sieving solution:

import Data.List

splitStreams [] = []
splitStreams ((channel,msg):rest) =
     let (myMsgs,otherMsgs) =
           partition (\(c,_)->c==channel) rest
     in (channel, msg : map snd myMsgs) : splitStreams otherMsgs

I'm afraid this algorithm is O(n*m) time in the worst case, where n is the 
length of the input list, and m is the number of unique channels.

But is there any way to write it such that each element is touched only 
once? Or at least an O(n*log(m)) algorithm?

Any takers?

/ Magnus Jonsson