Re: [Haskell-cafe] Optimization problem

...

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?

something like this, then? splitStreams :: Ord a => [(a, b)] -> [(a, [b])] splitStreams [] = [] splitStreams ((a, b) : t) = (a, b : bs) : splitStreams t' where (bs, t') = foldr f ([], []) t f z@(a', b') (bs, t') = if a' == a then (b' : bs, t') else (bs, z : t') (i guess i should use a strictness '!' for (xs, ys), but i am still running ghc-6.5, and i don't like the case constructions that much. does this bite me here? i didn't check, really.) who can tune this any further? cheers, m.