Stack overflow when folding infinite lists?

Question

Consider the following function:

(<.>) :: [[a]] -> [[a]] -> [[a]]
xs <.> ys = zipWith (++) xs ys

This essentially takes two two-dimensional arrays of as and concatanates them, left to right, e.x.:

[[1,2],[3,4]] <.> [[1,2],[3,4]] == [[1,2,1,2],[3,4,3,4]]

I would like to be able to write something like the following:

x = foldr1 (<.>) $ repeat [[1,2],[3,4]]

Which should make sense due to Haskell's lazy evaluation, i.e. we should obtain:

x !! 0 == [1,2,1,2,1,2,1,2...]
x !! 1 == [3,4,3,4,3,4,3,4...]

However, when I try to run this example with GHCi, either using foldr1 or foldl1, I either get a non-terminating computation, or a stack overflow.

So my question is:

1. What's going on here?
2. Is it possible to do what I'm trying to accomplish here with some function other than foldr1 or foldl1? (I'm happy if I need to modify the implementation of <.>, as long as it computes the same function)

Also, note: I'm aware that for this example, map repeat [[1,2],[3,4]] produces the desired output, but I am looking for a solution that works for arbitrary infinite lists, not just those of the form repeat xs.

Answer 1

I'll expand on what's been said in the comments here. I'm going to borrow (a simplified version of) the GHC version of zipWith, which should suffice for the sake of this discussion.

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith f [] _ = []
zipWith f _ [] = []
zipWith f (x:xs) (y:ys) = f x y : zipWith f xs ys

Now, here's what your computation ends up looking like, in it's glorious infinite form.

[[1, 2], [3, 4]] <.> ([[1, 2], [3, 4]] <.> ([[1, 2], [3, 4]] ... ) ... )

Okay, so the top-level is a <.>. Fine. Let's take a closer look at that.

zipWith (++) [[1, 2], [3, 4]] ([[1, 2], [3, 4]] <.> ([[1, 2], [3, 4]] ... ) ... )

Still no problems yet. Now we look at the patterns for zipWith. The first pattern only matches if the left-hand-side is empty. Welp, that's definitely not true, so let's move on. The second only matches if the right-hand-side is empty. So let's see if the right-hand-side is empty. The right-hand-side looks like

[[1, 2], [3, 4]] <.> ([[1, 2], [3, 4]] <.> ([[1, 2], [3, 4]] ... ) ... )

Which is what we started with. So to compute the result, we need access to the result. Hence, stack overflow.

Now, we've established that our problem is with zipWith. So let's play with it. First, we know we're going to be applying this to infinite lists for our contrived example, so we don't need that pesky empty list case. Get rid of it.

-- (I'm also changing the name so we don't conflict with the Prelude version)
zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith' f (x:xs) (y:ys) = f x y : zipWith' f xs ys

(<.>) :: [[a]] -> [[a]] -> [[a]]
xs <.> ys = zipWith' (++) xs ys

But that fixes nothing. We still have to evaluate to weak head normal form (read: figure out of the list is empty) to match that pattern.

If only there was a way to do a pattern match without having to get to WHNF... enter lazy patterns. Let's rewrite our function this way.

zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith' f ~(x:xs) ~(y:ys) = f x y : zipWith' f xs ys

Now our function will definitely break if given a finite list. But this allows us to "pretend" pattern match on the lists without actually doing any work. It's equivalent to the more verbose

zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith' f xs ys = f (head xs) (head ys) : zipWith' f (tail xs) (tail ys)

And now we can test your function properly.

*Main> let x = foldr1 (<.>) $ repeat [[1, 2], [3, 4]]
*Main> x !! 0
[1,2,1,2,1,2,1,2,1,...]
*Main> x !! 1
[3,4,3,4,3,4,3,4,3,...]

The obvious downside of this is that it will definitely fail on finite lists, so you have to have a different function for those.

*Main> [[1, 2], [3, 4]] <.> [[1, 2], [3, 4]]
[[1,2,1,2],[3,4,3,4],*** Exception: Prelude.head: empty list

Answer 2

zipWith is not -- in fact, it can't possibly be -- as lazy as you'd like. Consider this variation on your example:

GHCi> foldr1 (zipWith (++)) [ [[1,2],[3,4]], [] ]
[]

Any empty list of lists in the input will lead to an empty list of lists result. That being so, there is no way to know any of the elements of the result until the whole input has been consumed. Therefore, your function won't terminate on infinite lists.

Silvio Mayolo's answer goes through some potential workarounds for this issue. My suggestion is using non-empty-lists of lists, instead of plain lists of lists:

GHCi> import qualified Data.List.NonEmpty as N
GHCi> import Data.List.NonEmpty (NonEmpty(..))
GHCi> take 10 . N.head $ foldr1 (N.zipWith (++)) $ repeat ([1,2] :| [[3,4]])
[1,2,1,2,1,2,1,2,1,2]

N.zipWith doesn't have to deal with an empty list case, so it can be lazier.