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.
Agreed, these things could definitely do with plain, descriptive names rather than "hylo-mylo-bananafofylo-morphism". Like cata -> recursiveFold, ana -> [co]recursiveUnfold, hylo -> recursiveRefold, etc. It's tricky because i.e. there are many different "refold"s, but the others could be qualified further (and are comparatively rare in the field, I think...)
I think so. It's about factoring the recursion part out of a task, much like "map" is about factoring iteration out, and "fold" is about factoring out iteration+accumulation. I think scheme has both of these things; recursion schemes are the same idea but for recursion.
8 comments
[ 2.8 ms ] story [ 34.4 ms ] threadThe 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
Incredible that someone can say this and not be shitposting.
0: https://raw.githubusercontent.com/slamdata/matryoshka/master...