Why it is not possible to redefine (implement) foldr in terms of foldl

Question

We have that foldl can be implemented in terms of foldr. This is explained in detail in A tutorial on the universality and expressiveness of fold. In the paper it is stated that:

In contrast, it is not possible to redefine fold in terms of foldl , due to the fact that foldl is strict in the tail of its list argument but fold is not.

However I fail to see how this constitutes a proof on the impossibility of defining foldr in terms of foldl (note that in the original paper fold is a synonym for foldr). I'm quite puzzled trying to understand how strictness plays a role here. Can somebody expand on this explanation?

Answer 1

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f acc [] = acc
foldr f acc (x : xs) = f x (foldr f acc xs)

Note that when the list isn't empty, the recursive call to foldr is inside an argument passed to f. Haskell is lazily evaluated, so that recursive call to foldr isn't necessarily actually computed. If f can return a result without examining the second argument (but it can examine the first argument x to decide whether or not it wants to look at its second argument), then the foldr call can "stop early", without examining the whole list.

foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f acc [] = acc
foldl f acc (x : xs) = foldl (f acc x) xs

Here (when the list isn't empty) foldl recurses immediately, with the call to f inside the accumulator argument it passes to the recursive call. f doesn't get the opportunity to decide whether to examine the recursive call or not; foldl is in complete control of how long to keep recursing for, and it keeps doing so until it finds the end of the list.

So in particular, with foldr you can potentially process an infinite list; so long as the function you pass it eventually doesn't reference its second argument (acc). For example in GHCi:

Prelude> foldr (\x acc -> if x > 10 then "..." else show x ++ ", " ++ acc) "STOP" [1..5]
"1, 2, 3, 4, 5, STOP"

Prelude> foldr (\x acc -> if x > 10 then "..." else show x ++ ", " ++ acc) "STOP" [1..]
"1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ..."

With foldr, the lambda function is able to use that if statement to examine the list element x and decide whether or not to use the results of folding the rest of the list (which are referenced by acc but haven't actually been computed yet).

Alternatively, the function could return a result including the recursive call but store it in the field of a data constructor. This means the foldr will produce an infinitely nested data structure, but allows the caller of foldr to decide how much of that infinite structure it wants to look at, so the caller might still be able to return a finite result processing it. An example would be:

Prelude> take 10 $ foldr (\x acc -> x + 100 : acc) [] [1..]
[101,102,103,104,105,106,107,108,109,110]

Here I'm just using foldr to do the same job as map, adding 100 to each element of the infinite list, which produces an infinite list in turn, but then take 10 only grabs the first 10 of them. This works because the infinite "results of folding the result of the list" are simply stored in the second field of the list constructor :.

That ability to process an infinite list (whether you actually return a finite or infinite result) can't be simulated by foldl, because the function you pass into foldl doesn't get to decide "how much" of the recursion to use; foldl itself recurses all the way to the end of the list before it returns anything other than another call to foldl. If the list is infinite it simply never returns anything other than another call to foldl, no matter what function you pass to foldl or what wrapper you use to try to make it do the job of foldr.

It's not just about processing infinite lists either (if that seems esoteric); if all your lists are finite then you can use foldl to get the same results as foldr but you're still locked into examining the entire list, which can be very inefficient if you only actually needed a small prefix of it.

Answer 2

In what follows, I will refer to fold as foldr (since that is what its is called in the Haskell standard libraries).

---

Taking another look at the definition of foldl,

foldl :: (β -> α -> β) -> β -> [α] -> β
foldl f v [] = v
foldl f v (x:xs) = foldl f (f v x) xs

note that the base case requires the list argument to be [] - in all other cases the list is evaluated to WNHF and we recurse immediately using the tail of the list. That establishes the fact that foldl is strict in its (last) list argument.

Now, we can write a version of foldr using foldl, but it will only work on lists of finite length. See this page for the motivation.

foldr' :: (α -> β -> β) -> β -> [α] -> β
foldr' f v xs = foldl (\g u x -> g (f u x)) id xs v 

To see the problem, let's try to write a version of head which is total¹ using a right fold.

import Control.Applicative ((<|>))

safeHead :: [α] -> Maybe α
safeHead = foldr (\x y -> Just x <|> y) Nothing

If we replace foldr with our foldl-based foldr', we are no longer able to find the head of an infinite list safeHead [1..]. Even if safeHead only needs to look at the first element of the list, the underlying foldl will try to traverse the whole infinite list.

---

¹ Such a function actually already exists in the Prelude, it is called listToMaybe