Real World Haskell presents an interesting challenge in the chapter How to Think About Loops. How do you explain this `foldl`

implemented in terms of `foldr`

?

```
myFoldl :: (a -> b -> a) -> a -> [b] -> a
myFoldl f z xs = foldr step id xs z
where step x g a = g (f a x)
```

If you haven't given understanding it a try, I'd really encourage you to invest some time into it before reading this blog post.

Now, let's get into it. Look at the expression `foldr step id xs z`

. What is the signature of `foldr`

, by the way? It is `foldr :: (a -> b -> b) -> b -> [a] -> b`

. It needs three parameters. How many are we passing it here? Four! WTH?

What if we are still passing only three parameters? Just look at `foldr step id xs`

without the `z`

. Well, this is a valid `foldr`

application. But why the `z`

in the end? It's as if we are passing `z`

to whatever that comes out of `foldr`

. Hang on, what if `foldr`

really returned a function? Yeah, what if `foldr step id xs`

returned a function that takes `z`

? This makes sense.

So `foldr step id xs`

must return a function. Then its accumulator must be a function. Let's look at the starting value. `id`

. Yeah, `id`

*is* a function. We are on the track. Now, the `step`

is a mystery here. Before, we look at it, we must know what it must do. `step`

must take an element from `xs`

, of type `b`

(the type variable). Its accumulator must be a function. And, it must return a function.

Now, every function that we've seen go into `foldr`

took two parameters and returned one. But, `step`

here seems to take three! Let's again forget the last parameter `a`

. `step x g`

is a valid function to go into `foldl`

. What should `x`

be? It must be a value from the `xs`

list. Ok, this seems reasonable. Now, what should the next parameter, the accumulator, be? We agreed it must be a function. So, `g`

is a function. Have a look the implementation. `g (f a x)`

. We don't know what's going on over there but we do know that `g`

is a function there! Right? On the right track are we?

Come back once again to the `step x g`

. We know that `foldr`

will supply only two parameters to `step`

. So, `foldr`

will give our `step`

only the `x`

and `g`

. What happens if a function is missing the last parameter? Function currying! It will return a function! `foldr`

will get a function for not supplying the last parameter to `step`

. Isn't this what we wanted? We wanted our accumulator to be a function and it is. So, do you get the implementation of `foldr`

? I mean, we still don't know what `step`

does, but we at least know that `foldr`

takes the list we are supposed to fold over and a function that takes a function and and returns a function so that the whole thing folds up into a function. We finally supply a `z`

to it and get our result. Are we clear? Let's move on.

Let's look at the `step`

function now. First, what is `f`

? (Hoho, the F word! « awkward silence » Sorry.) `f`

is a function that takes an accumulator and an element from the list and returns another accumulator. Right, so `f a x`

means we are passing an accumulator, `a`

, and an element from the list, `x`

. We know `x`

is an element from the list. So we are right. But what is this `a`

anyway? It's that `a`

that our `step`

won't get from `foldr`

. So, the function that `foldr`

will finally return will be a function that takes a variable of the same type as `a`

.

We know that `step`

will get, as its accumulator, the value it returned previously. Now, since it's being partially applied, we'll get a function, `g`

, that takes `a`

as a parameter. Since, it won't have `a`

, it'll return another function that takes a new `a`

. This goes on until we reach the beginning of the list (we're actually folding right, so we start from the end) and we'll finally have a chain of functions all composed into one function that takes only one `a`

. When, we supply the `z`

in the end, we initiate a sort of chain reaction that computes the whole result.

To illustrate this point further, let's run an example mentally. Let's run `myFoldl (+) 0 [1..3]`

. First look at `f a x`

. We know `f`

is `(+)`

and `z`

is the intial value that we pass for `a`

. `x`

is the last element. So, `f a x`

is `(+) 0 3`

.

We have `g (f a x)`

where `g`

is `id`

. Hence, we have `id ((+) 0 3)`

. But, `a`

is not passed, remember? The value that is returned is a function that takes an a, right? The actual value return value is `(\a -> id ((+) a 3))`

.

Now this value is again fed as `g`

to which the next `f a x`

is applied. First let's assume `a`

is once again `0`

. So, `f a x`

here is `(+) 0 2`

. So, we have the whole value as `(\a -> id ((+) a 3)) ((+) 0 2)`

, right? Now, since we don't have that `0`

there, we need to introduce a new variable. So, we have `(\b -> (\a -> id ((+) a 3)) ((+) b 2))`

.

If we do this one more time, we get `(\c -> (\b -> (\a -> id ((+) a 3)) ((+) b 2)) ((+) c 1))`

.

To this we apply the final `z`

, (`0`

here), and we get `(\c -> (\b -> (\a -> id ((+) a 3)) ((+) b 2)) ((+) c 1)) 0`

. Go ahead, paste this into `ghci`

and you'll get `6`

.

Do you see how this evaluates? First, `c`

gets substituted by `0`

which leaves us with `((+) 0 1)`

or `(0 + 1)`

. This `(0 + 1)`

is substituted for `b`

, and we get `((0 + 1) + 2)`

. Do this once again, and you get `((0 + 1) + 2) + 3`

. This is what a `foldl`

does.

This turned out to be a very long post than I thought but I hope it'll give you a clear idea of what the function does. This was an amazing example that displayed the power of functional programming. You knew that functions are like other values but the idea of folding over functions to create new functions is awesome. How awesome? Barney Stinson awesome :). Anyway, have a good day and enjoy hacking in Haskell.