Writing foldl as foldr confusion

Question

I know there are other posts about this, but mine is slightly different.

I have a function that performs the task of foldl, using foldr. I have the solution given to me, but would like help understanding.

foldlTest:: (b -> a -> b) -> [a] -> (b -> b)

foldlTest f xs = foldr (\x r b -> r (f b x))
                (\b -> b)
                xs

And It is called using something like this:

foldlTest (-) [1,2,3] 10 = -4

---

First thing I understand is that my function takes in 2 arguments, but 3 are given in the above test case. This means that the 10 will take part in a lambda expression I assume.

1) Does the 10 take the place of the b in b -> b? (then the b would be the initial accumulator value)

What I don't understand is what the (\x r b -> r (f b x)) part does.

2) What is the value of each of the variables? I am very confused about this lambda function.

3) What exactly does the lambda function do and how is it different from a regular foldr?

Answer 1

OK, since none of our resident Haskell experts has yet stepped up to explain this, I thought I'd have a go. Please everyone, feel free to correct anything you see wrong, because I'm really just feeling my way towards the answer here, and the following will by its very nature be a bit rambling.

First, as always in Haskell, it's a good idea to look at the types:

Prelude> :t foldl
foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b

Since we're just interested in lists here, and not generic Foldables, let's specialise this to:

foldl ::  (b -> a -> b) -> b -> [a] -> b

and compare with the function you've been given:

foldlTest:: (b -> a -> b) -> [a] -> (b -> b)

Since Haskell functions are curried, which is another way of saying that -> arrows in type signatures are right associative, the last pair of parentheses there is unnecessary, so this is the same as:

foldlTest:: (b -> a -> b) -> [a] -> b -> b

Comparing with that for foldl above, we see that they're identical except for the fact that the last two parameters - the [a] and the b - have been flipped over.

So we can already observe that, while the library function foldl takes a fold function, a starting accumulator, and a list to fold, to produce a new accumulator, the foldlTest version takes a fold function, a list to fold, and a starting accumulator, to produce a new accumulator. That sounds like the exact same thing, which it is, but if we now reintroduce the pair of brackets which I took off a few steps ago, we see that foldlTest, in the form you've shown, can be thought of as:

taking a fold function and a list, and producing a function b -> b which describes how folding over the list transforms the initial accumulator into the final result.

Note in particular that what it returns, in this formulation, is indeed a function.

So now we're ready to look at the actual implementation that you've seen:

foldlTest f xs = foldr (\x r b -> r (f b x))
                (\b -> b)
                xs

I'll be the first to admit that this is rather complicated, even confusing. As ever, lets examine the types.

The input types are easy. We know from the above discussion that f has type b -> a -> b, and xs has type [a].

OK, what about that lambda? Let's take it in stages:

• It takes 3 arguments, x, r and b, in that order.
• The result of the function call is r (f b x). This already tells us a lot, if we sit down and think about it!
• For one, we know f has type b -> a -> b, so from f b x we know that b has type b and x has type a.
• As for r, we see that it must be a function, because it's applied to f b x. And we know the latter has type b (from the type signature of f). So r has type b -> c, for some type c.
• Therefore our complicated lambda function has the type a -> (b -> c) -> b -> c, where c is some type we haven't yet determined.
• Now comes a key point. This lambda is presented as the first argument (the fold function) to the foldr function. Therefore it must have the type d -> e -> e, for some types d and e.
• Remember that functions are curried, and although it seems like the lambda's signature takes 3 arguments, we can reduce it to 2 by rewriting as a -> (b -> c) -> (b -> c). That's an exact match for the signature we know foldr is looking for, with d equal to a and e equal to b -> c.

And it we specialise foldr's signature so that it accepts this type of function, we find that it is:

foldr :: (a -> (b -> c) -> (b -> c)) -> (b -> c) -> [a] -> (b -> c)`

We still don't know what c is - but we don't have to wonder much longer. The above is the signature for a fold which goes over a list of as, and produces a function from b to c. The next argument to foldr, which is of type b -> c, is given (by the implementation we're trying to decipher) as \b -> b. This is just the identity function, of course, and crucially it is a function from a type to itself. So the b -> c type must actually be b -> b, or in other words c was the same as b all along!

So that lambda must have the following type:

a -> (b -> b) -> (b -> b)

It takes an a, and an endomorphism on b (that just means a function from b to itself), and returns another endomorphism on b. And this is the function we will fold the list of as with, taking the identity function as a starting point, to produce the endomorphism b -> b that will implement the left fold we're after.

The above type signature on its own doesn't give us much clue of how to implement it, given that a and b could be anything. However, we do have our function f that relates them - recall it takes a b and an a, and produces a b. Given that (by undoing the currying again), the above function requires us, given an a, a b -> b function, and a b, to produce another b, I can only see two non-trivial ways to do it:

• apply the function to the b, then apply f to the a and the result.
• apply f to the a and the b, then apply the b -> b function to the result

The second of these two is exactly what that lambda you are asking about does, as hopefully is now obvious from looking at it. (The first option would be written \x r b -> f (r b) x. I'm not actually sure what overall effect this would produce, although I haven't thought about it much.)

I've covered a lot of ground, although it feels like more than it really is, because I've tried to be very painstaking. To recap, what the foldlTest function does is, given a list of as and a function f :: b -> a -> b, produces a function b -> b that is built by starting with the identity function, and walking right-to-left along the list, changing the current function r :: b -> b to the one that sends b to r (f b x) - where x :: a is the element of the list we are currently at.

That's a rather algorithmic description of what foldlTest does. Let's try to see what it does to an actual list - not a concrete one, but let's say a 3-element list [a1, a2, a3]. We start with the identity function \b -> b, and successively transform it into:

• b -> f b a3 (recall that r starts as the identity function)
• b -> f (f b a2) a3 (this is just substituting the previous function as r into \b -> r (f b x), with a2 now playing the role of x)
• b -> f (f (f b a1) a2) a3

I hope you can now see that this looks an awful lot like folding the list from the left with the same function f. And by "looks an awful lot like", I actually mean it's identical! (If you haven't seen or tried it before, try to write out the successive stages of foldl f b [a1, a2, a3] and you'll see the identical pattern.)

So apologies again that this has been a bit rambling, but I hope this has given you enough information to answer the questions you asked. And don't worry if it makes your brain hurt a bit - it does mine too! :)