In Haskell, if we evaluate:
[1..] ++ 
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
> 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.
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.
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.
Leave a comment!
Martijn loves to receive comments! Add yours by filling out the fields below.