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!