Matryoshka

Generalized folds, unfolds, and traversals for fixed point data structures in Scala.

External Resources

Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire – the iconic paper that collected a lot of this info for the first time
Recursion Schemes: A Field Guide (Redux) – Ed Kmett’s summary of various folds and unfolds, with links to Haskell code
Unifying Structured Recursion Schemes – a newer paper on how to generalize recursion schemes
Efficient Nanopass Compilers using Cats and Matryoshka – Greg Pfeil’s talk on this library (and some other things)
Fix Haskell (by eliminating recursion) – Greg Pfeil’s talk on recursion schemes in Haskell

Introduction

This library is predicated on the idea of rewriting your recursive data structures, replacing the recursive type reference with a fresh type parameter.

sealed trait Expr
final case class Num(value: Long)      extends Expr
final case class Mul(l: Expr, r: Expr) extends Expr

could be rewritten as

sealed trait Expr[A]
final case class Num[A](value: Long) extends Expr[A]
final case class Mul[A](l: A, r: A)  extends Expr[A]

This trait generally allows a Traverse instance (or at least a Functor instance). Then you use one of the fixed point type constructors below to regain your recursive type.

Fixpoint Types

These types take a one-arg type constructor and provide a recursive form of it.

All of these types have instances for Recursive, Corecursive, FunctorT, TraverseT, Equal, Show, and Arbitrary type classes unless otherwise noted.

Fix – This is the simplest fixpoint type, implemented with general recursion.
Mu – This is for inductive (finite) recursive structures, models the concept of “data”, aka, the “least fixed point”.
Nu – This is for coinductive (potentially infinite) recursive structures, models the concept of “codata”, aka, the “greatest fixed point”.
Cofree[?[_], A] – Only has a Corecursive instance if there’s a Monoid for A. This represents a structure with some metadata attached to each node. In addition to the usual operations, it can also be folded using an Elgot algebra.
Free[?[_], A] – Does not have a Recursive instance. In addition to the usual operations, it can also be created by unfolding with an Elgot coalgebra.

So a type like Mu[Expr] is now isomorphic to the original recursive type. However, the point is to avoid operating on recursive types directly …

Algebras

A structure like this makes it possible to separate recursion from your operations. You can now write transformations that operate on only a single node of your structure at a time.

This diagram covers the major classes of transformations. The most basic ones are in the center and the arrows show how they can be generalized in various ways.

Here is a very simple example of an algebra (eval) and how to apply it to a recursive structure.

val eval: Expr[Long] => Long = {
  case Num(x)    => x
  case Mul(x, y) => x * y
}

def someExpr[T[_[_]]: Corecursive]: T[Expr] =
  Mul(Num(2).embed, Mul(Num(3).embed, Num(4).embed).embed).embed

someExpr[Mu].cata(eval) // ⇒ 24

The .embed calls in someExpr wrap the nodes in the fixed point type. embed is generic, and we abstract someExpr over the fixed point type (only requiring that it has an instance of Corecursive), so we can postpone the choice of the fixed point as long as possible.

Folds

Those algebras can be applied recursively to your structures using many different folds. cata in the example above is the simplest fold. It traverses the structure bottom-up, applying the algebra to each node. That is the general behavior of a fold, but more complex ones allow for various comonads and monads to affect the result.

Here is a cheat-sheet (also available in PDF) for some of them.

Contributing

Please note that this project is released with a Contributor Code of Conduct. By participating in this project you agree to abide by its terms.

Users

Quasar

jedesah/matryoshka