For me, the key takeaway from this paper is the idea of separating the two parts of any data structure transformation: how you traverse the structure and what you do at each step.
Recursion schemes are reusable tactics for traversing data structures in different ways, allowing you to focus purely on what you want to do with your data. You write much less code and are shielded from bugs in repetitive traversal code because you don’t write any.
I discovered recently that if your data structures are always finite, then katamorphisms and anamorphisms are no longer dual on those data structures. Katamorphisms on finite data structures are halting, but anamorphisms need not halt.
For me, the key takeaway from this paper is the idea of separating the two parts of any data structure transformation: how you traverse the structure and what you do at each step.
Recursion schemes are reusable tactics for traversing data structures in different ways, allowing you to focus purely on what you want to do with your data. You write much less code and are shielded from bugs in repetitive traversal code because you don’t write any.
This blog post series does a great job of breaking down each tactic and showing how you can use them in Haskell: https://blog.sumtypeofway.com/posts/introduction-to-recursion-schemes.html
Every time I see something like this I want to figure out an excuse to use Haskell for a toy project.
Do you have any ideias? I would like to work on a Haskell side project.
Not at the moment. I don’t want it to be anything too useful, in case it winds up being something other people want.
I might do an implementation of the SQL-ish DSL that Obsidian Dataview uses.
A true classic!
I discovered recently that if your data structures are always finite, then katamorphisms and anamorphisms are no longer dual on those data structures. Katamorphisms on finite data structures are halting, but anamorphisms need not halt.