Re: [Haskell-cafe] Optimization problem

On Thu, 14 Sep 2006, Ketil Malde wrote:

Magnus Jonsson writes:

...

splitStreams::Ord a=>[(a,b)]->[(a,[b])]

...

...

splitStreams [(3,x),(1,y),(3,z),(2,w)] [(3,[x,z]),(1,[y]),(2,[w])]

[...]

...

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?

I guess it should be possible to use a quicksort-like algorithm, splitting the stream into three streams with keys less than, equal, and greater than the first element, and recurse on the less/equal streams?

-k

That is probably the best we can do. I think in a hypothetical concurrent Haskell with futures/promises, the split stream problem could be solved. But if it can be solved in regular Haskell, I would be pleasantly surprised. / Magnus