MuniHac 2022 - Cass Alexandru: Structured Traversals for (Mutually) Recursive Algebraic Data Types
Structured traversals (a.k.a. recursion schemes) show up all the time when working with inductive algebraic datatypes (s.a. lists), once you know what to look for. We examine the simplest of these, the humble catamorphism (foldr for lists), following its journey from motivation, then via its origin in category theory into the more turbulent waters of mutually recursive datatypes (s.a. ASTs), putting Haskell's amenities for type-level programming and basic dependent types to work along the way.
The theoretical foundation for the presentation is the multirec paper by Andres Löh et al. The presentation has a literate Haskell source, so all code on the slides is real. Additionally, the repo has a pinned nix shell so you can build everything at home.
