An Introduction to Recursion Schemes (2014)

My experience with recursion schemes was mixed. I applied Matryoshka[1] to a problem involving an algebra of boolean operations on polygons. The implementation was elegant in so far as the essential recursion was lifted out of many separate functions and consolidated. Recursion is always a tricky thing to get right so using recursion schemes avoided an entire class of errors and the implementation was rock solid.

The challenge became one of communication. Whereas looping and branching structures are considered fundamental building blocks recursion schemes are not. Team members immediately hit a wall when encountering ana/cata/hylo/*-morphisms. It's like taking a walk through your neighborhood turning a corner and finding an alien artifact. It's also a case of "the math people got there first" ie: the nomenclature hurts rather than helps understanding. Many times during conversations I wondered how branching and loop control structures were received when introduced decades ago. Were they dismissed or embraced and how much of this was because they were given nice names (if/else/for/while)?

In hindsight I'm disappointed that I wasn't exposed to recursion schemes as an undergrad. Recursion schemes are exactly the kind of abstraction found elsewhere in computer science. Also I would also love to see a language with recursion schemes given the same first-class support as the branching and looping constructs we see in almost all languages today.

[1] - https://github.com/slamdata/matryoshka

This seems to be about statically typed languages like Haskell. Can it be used (and be useful) for dynamically typed languages like Scheme?

If anyone else has a problem reading this article, it significantly is easier to read with Chrome.

Previously on HN: https://news.ycombinator.com/item?id=18687372