Stack Unwinding

Let’s say you have a list of numbers. What can you do with it? Find its length, map a function over it, add them up, etc. Wouldn’t it be great if there were one function to rule them all, a function that generalizes what you can do with a list? In many languages, there is a higher-order function called fold that encapsulates a pattern of structural recursion over recursive structures: to specify a function on a list, you specify two exhaustive cases: what to do to an empty list, and what to do with any other list. A generalization of this generalization is the notion of a catamorphism, which is what I’m writing about today.

Like many aspiring software developers and computer scientists, I wanted to improve my art by going through Structure and Interpretation of Computer Programs. I fully expected to emerge from it all with Sherlock Holmes-esque abilities in programming. Yeah, that was about 7 years ago. Still, every so often, I’ll do some of the exercises and search online to see how my answers compared to others’.