On Thu, 14 Sep 2006, Ketil Malde wrote:
Magnus Jonsson <[EMAIL PROTECTED]> 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
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
