[Haskell-cafe] Weaving fun

Chris Kuklewicz haskell at list.mightyreason.com
Wed Apr 11 06:00:16 EDT 2007


I have a simply recursive solution that operates efficiently...

Bas van Dijk wrote:
> Hello,
> 
> For my own exercise I'm writing a function 'weave' that "weaves" a
> list of lists together. For example:
> 
>  weave [[1,1,1], [2,2,2], [3,3]] ==> [1,2,3,1,2,3,1,2]
>  weave [[1,1,1], [2,2], [3,3,3]] ==> [1,2,3,1,2,3,1]
> 
> Note that 'weave' stops when a list is empty.

This version of weave works without Data.Sequence or using reverse, (++), or concat:

> weave :: [[a]] -> [a]
> weave [] = []
> weave xss = weave' id xss
>   where weave' _rest ([]:_) = [] -- end when any list is empty
>         weave' rest [] = weave (rest []) -- goto next, check for (weave [])
>         weave' rest ((x:xs):xss) = x : weave' (rest . (xs:)) xss

The first parameter of weave' is the usual "difference list" trick to allow
efficient append with simple lists.

It works lazily and handles infinite lists.  Though if you weave an infinite
number of lists together you will get unbounded memory usage.

Here it terminates when there is no element after the 15 in the second list:

*Main> weave [[1..],[11..15],[300..]]
[1,11,300,2,12,301,3,13,302,4,14,303,5,15,304,6]

-- 
Chris


More information about the Haskell-Cafe mailing list