[Haskell-cafe] Weaving fun

Matthew Brecknell haskell at brecknell.org
Tue Apr 10 20:56:24 EDT 2007


Dave Feustel:
> 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]]
[1,2,3,1,2,3,1,1]

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 mailing list