# Fold as a chain of endomorphisms

A few months ago, Tom Ellis showed how to write `foldr'` as a chain of endomorphisms. The relevant code is pasted below, with a couple of changes Iâ€™ve made for clarityâ€™s sake:

```
compose :: [b -> b] -> b -> b compose [] = id
compose (f:fs) = f . compose fs
foldr' :: (a -> b -> b) -> b -> [a] -> b
foldr' combine base xs = compose (map combine xs) base
```

I originally saw Ellisâ€™s blog post on Reddit, tried to qualitatively understand it, shrugged my shoulders, and moved on. I acknowledged that his implementation worked, but I definitely missed the intuition behind it. Iâ€™d Googled the term â€œendomorphismâ€ (essentially a function of type `a -> a`), but I failed to make the connection between concept and code.

By coincidence, I recently had a short conversation with Andrew Braunstein about Haskell, and the notion of folding came up. He mentioned that the idea of folding could be understood by imagining replacing every `(:)` in a list with `combine`.

It was at that point that I put two and two together! First, Iâ€™ll show by example. Letâ€™s say that you have a list of integers `1:2:3:4:5:[]`, and you want to sum them. You can conceptually think about summing the list by replacing every `(:)` with `(+)` (and replacing the empty list with the additive identity, zero). You obviously get `1+2+3+4+5+0`.

Ellisâ€™s code represents this idea of mapping one function into another, albeit in an abstract way. `compose` itself takes a list of endomorphisms and a starting value, and it feeds the result of one function into another. Remember, since an endomorphism is a function with the type `a -> a` (or in the sample codeâ€™s case, `b -> b`), we can easily achieve this chained computation.

All we have to do is map `combine` over our input list. In the example of summing integers, weâ€™ll have a new list of functions that can be thought of abstractly as `1+ : 2+ : 3+ : 4+ : 5+ : []`. Note that each function in the list takes an integer and returns an integer, hence we have a list of endomorphisms.

Finally, when we call `compose (map combine xs) 0`, weâ€™ll recurse our way down to the end of this list of functions. When we reach the empty list at the end, weâ€™ll return the base case, `0`, and feed that into the last function of the list, `5+`. Of course, `5 + 0 == 5`, so we feed *that* result into the previous function, `4+`, and so on and so forth.

In practice, this is the same thing as replacing each `(:)` with ` combine` and evaluating right to left.

I plan on using this idea, in a less formal way, to teach students new to functional programming how folding works.

Pretty cool stuff, if you ask me!