/recursion-schemes-cookbook

A friendly guide for leveraging the power of recursion schemes in real-world applications

Recursion Schemes Cookbook

Welcome to the recursion schemes cookbook! This document is intended as a complement to matryohska's documentation. Its goal is to help you come up with strategies to solve real-life problems using matryoshka (and recursion schemes in general).

Reading this book

We can see recursion schemes as a (quite unusual) way to build functions by using a recursive data structure as a blueprint of the computation (a... pattern). Understanding how the three ingredients work together requires a little effort but is within the reach of any motivated programmer. On the other hand, this being a rather unusual way to express computations, the main difficulty is to find the right ingredients to solve a concrete problem.

That's the goal of this cookbook: provide you with detailed examples of the most frequent uses of recursion schemes that explain the thought process that leads from the definition of a problem to the expression of a solution in terms of pattern-functors and f-algebras.

In turns out that people seem to use recursion schemes to solve two major families of problems:

  • Compiling or interpreting programs (ie working with ASTs)
  • Manipulating schemas (or any generic representation of data)

Both come with its own set of challenges (although those sets have a non-empty intersection). This cookbook is therefore divided in two main parts, each dedicated to one of these two families of problems.

Table of contents