Left and Right Folding over an Infinite list

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.