[Haskell-cafe] Optimization problem

[Matthias Fischmann]

> >Magnus Jonsson <magnus at smartelectronix.com> 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.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20060914/1999c8ab/attachment.bin