Weaving lists

Posted on Sunday, 13 April 2008 at 21:06.

In Haskell, if we evaluate:

[1..] ++ [0]

then the zero is never reached, because the first list is infinite.

More generally, when concatenating a list L of lists, elements from lists after the first infinite list in L are never reached. For a problem I’m working on I needed a way to remedy this: to visit all elements in a “fair” way so that each element is reached sometime. I figured I needed something like

weave :: [[a]] -> [a]

Which has the same type as concat, as it is concat’s fair twin. But how to write this function?

I started out by solving an easier problem: the fair version of the append operator (++).

weave2 :: [a] -> [a] -> [a]
weave2 (x:xs) (y:ys) = x : y : weave2 xs ys
weave2    xs     ys  = xs ++ ys

So that:

> weave2 [0,2..] [1,3..]
[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14...

After some more thinking, I figured: if I see the list L of lists as a table, where L is the list of columns, then the table has a finite width and possible infinite height. Then I simply need to visit the table row by row instead of column by column. And so we end up with:

weave :: [[a]] -> [a]
weave = concat . transpose

It’s always exciting when a problem has a way simpler and more elegant solution than you thought at first.

Comments

By Chris on Monday, 14 April 2008 at 09:52:

In the AFP-course we had to solve a similar problem. If you take a look at Assignment 5 you can see a similar interesting problem: if you have a list of lists of integers, of which some might be infinite, find the shortest list and sum it up.

By Joris on Sunday, 20 April 2008 at 09:35:

Cool. This really shows off the power of laziness.

It’s even possible to generalize the weave function to accept an infinite list of infinite lists. That is a useful trick for certain problems in theoretical computer science, for example counting the infinite set of fractional numbers.

Weaving lists

Comments

Leave a comment!