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!