Left and Right Folding over an Infinite list

Question

I have issues with the following passage from Learn You A Haskell (Great book imo, not dissing it):

One big difference is that right folds work on infinite lists, whereas left ones don't! To put it plainly, if you take an infinite list at some point and you fold it up from the right, you'll eventually reach the beginning of the list. However, if you take an infinite list at a point and you try to fold it up from the left, you'll never reach an end!

I just don't get this. If you take an infinite list and try to fold it up from the right then you'll have to start at the point at infinity, which just isn't happening (If anyone knows of a language where you can do this do tell :p). At least, you'd have to start there according to Haskell's implementation because in Haskell foldr and foldl don't take an argument that determines where in the list they should start folding.

I would agree with the quote iff foldr and foldl took arguments that determined where in the list they should start folding, because it makes sense that if you take an infinite list and start folding right from a defined index it will eventually terminate, whereas it doesn't matter where you start with a left fold; you'll be folding towards infinity. However foldr and foldl do not take this argument, and hence the quote makes no sense. In Haskell, both a left fold and a right fold over an infinite list will not terminate.

Is my understanding correct or am I missing something?

Answer 1

The key here is laziness. If the function you're using for folding the list is strict, then neither a left fold nor a right fold will terminate, given an infinite list.

Prelude> foldr (+) 0 [1..] ^CInterrupted. 

However, if you try folding a less strict function, you can get a terminating result.

Prelude> foldr (\x y -> x) 0 [1..] 1 

You can even get a result that is an infinite data structure, so while it does in a sense not terminate, it's still able to produce a result that can be consumed lazily.

Prelude> take 10 $ foldr (:) [] [1..] [1,2,3,4,5,6,7,8,9,10] 

However, this will not work with foldl, as you will never be able to evaluate the outermost function call, lazy or not.

Prelude> foldl (flip (:)) [] [1..] ^CInterrupted. Prelude> foldl (\x y -> y) 0 [1..] ^CInterrupted. 

Note that the key difference between a left and a right fold is not the order in which the list is traversed, which is always from left to right, but rather how the resulting function applications are nested.

• With foldr, they are nested on "the inside"

  foldr f y (x:xs) = f x (foldr f y xs) 

  Here, the first iteration will result in the outermost application of f. Thus, f has the opportunity to be lazy so that the second argument is either not always evaluated, or it can produce some part of a data structure without forcing its second argument.

• With foldl, they are nested on "the outside"

  foldl f y (x:xs) = foldl f (f y x) xs 

  Here, we can't evaluate anything until we have reached the outermost application of f, which we will never reach in the case of an infinite list, regardless of whether f is strict or not.

Answer 2

The key phrase is "at some point".

if you take an infinite list at some point and you fold it up from the right, you'll eventually reach the beginning of the list.

So you're right, you can't possibly start at the "last" element of an infinite list. But the author's point is this: suppose you could. Just pick a point waaay far out there (for engineers, this is "close enough" to infinity) and start folding leftwards. Eventually you end up at the start of the list. The same is not true of the left fold, if you pick a point waaaay out there (and call it "close enough" to the start of the list), and start folding rightwards, you still have an infinite way to go.

So the trick is, sometimes you don't need to go to infinity. You may not need to even go waaaay out there. But you may not know how far out you need to go beforehand, in which case infinite lists are quite handy.

The simple illustration is foldr (:) [] [1..]. Let's perform the fold.

Recall that foldr f z (x:xs) = f x (foldr f z xs). On an infinite list, it actually doesn't matter what z is so I'm just keeping it as z instead of [] which clutters the illustration

foldr (:) z (1:[2..])         ==> (:) 1 (foldr (:) z [2..]) 1 : foldr (:) z (2:[3..])     ==> 1 : (:) 2 (foldr (:) z [3..]) 1 : 2 : foldr (:) z (3:[4..]) ==> 1 : 2 : (:) 3 (foldr (:) z [4..]) 1 : 2 : 3 : ( lazily evaluated thunk - foldr (:) z [4..] ) 

See how foldr, despite theoretically being a fold from the right, in this case actually cranks out individual elements of the resultant list starting at the left? So if you take 3 from this list, you can clearly see that it will be able to produce [1,2,3] and need not evaluate the fold any farther.