Effectful Recursion Schemes

Marvin Borner, 2026-04-20

import set

Common functional programming languages such as Haskell use recursion schemes to generalize folding/unfolding patterns. This typically requires infinitely recursive types and some notion of functor instancing. Today I want to showcase an effectful implementation of recursion schemes that instead makes use of refunctionalizing data structures to effects and handlers.

In fact, this post is much more about showcasing effects and handlers than it is about recursion schemes themselves:

This is an interactive blog, you are encouraged to experiment with the code!

Let’s start by constructing some basic lambda terms as the running example data structure.

type Term { Sym(name: String) Lam(name: String, body: Term) App(function: Term, argument: Term) }

For example, the identity function λx.x is encoded as the following term:

Lam("x", Sym("x")).show

In Effekt, we can traverse these terms by matching and recursively calling the traversing function. For example, in order to use a custom show implementation instead of the default one:

... continue reading