[Haskell-cafe] Weaving fun
haskell at brecknell.org
Tue Apr 10 20:56:24 EDT 2007
> Talk about synchronicity! I was just wondering whether 'weaving' of
> infinite lists is possible.
> eg weave the infinite lists [2,4..], [3,6..], [5,10..]
> to get [2,3,4,5,6,8,9,10,..]
> Is this kind of lazy evaluation possible?
The base library version of (concat . transpose) can do that, since for
infinite lists, you don't have the termination requirements of the OP.
By the way, there is an error in my previous version of weave:
*Main> weave [[1,1,1,1],[2,2],[3,3,3]]
Dan's version also has this behaviour.
So, a correct list-based solution that doesn't use reverse or quadratic
concatenation isn't immediately obvious. However, Chris Mears' solution
can easily be adapted to use the O(1) snoc from Data.Sequence:
> import Data.Sequence
> weave = weaveSeq . fromList where
> weaveSeq xs = case viewl xs of
> (x:xs) :< xss -> x : weaveSeq (xss |> xs)
> _ -> 
More information about the Haskell-Cafe