The purpose of this article is not for you to learn about recursion schemes - although that’d be a nice side effect. This is really more of a revenge story.
See, a few years ago, I was learning about functional programming. It takes a while, there’s a lot of new concept to learn and old ones to unlearn, but I finally got to a place where I felt I knew - not everything I needed, certainly, but at least enough to start writing code I didn’t have to be ashamed of.
But then about 5 minutes later, a friend of mine came to me and asked Do you know about recursion schemes?, to which I had to confess that I didn’t even understand all the words in that question. And so I started studying again, and after a while, I came to the conclusion that… well, recursion schemes are a bit rubbish, really.
They sound incredibly pretentious, are surprisingly hard to put together, and all for a payoff that is somewhat undewhelming. The standard pitch goes something like:
If you want to write an interpreter for a simple mathematical expression language, then using recursion schemes is almost as good as not using them.
I didn’t find that compelling.
So I went to my friend and told him all that, but he answered no but you don’t understand - you can’t be a proper functional programmer if you don’t understand recursion schemes. Which I felt was a bit of a low blow, because I dearly want to be a proper functional programmer!
So I went back to studying, and after a while, came to a new conclusion: the problem, in my case, was not recursion schemes, but the way they are taught. They’re a beautiful theorical construct, and are almost always approached that way - but that’s not how I work. I need to understand why something is useful before I can devote that much brain power to the underlying theory.
This article is the result of that conclusion - the introduction material I wish I’d found when I started out. And my promise to you is: once you’re done reading, you will, through the prism of two simple recursion schemes, understand the purpose of all the others, and how to study and create them by yourselves.
Oh, and of course, you, too, will be a proper functional programmer.