> >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?
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.
signature.asc
Description: Digital signature
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
