🎓 A1Learner
🔍
0 of 45 lessons completed

Recursion Schemes

A recursion scheme is a reusable recursion shape with the combining step passed in as an argument. The shape walks the data once and the step decides what each piece means.

One fold sums a tree

The leaf step keeps each value and the combine step adds. The fold walks the whole tree and prints the total.

sealed trait Tree
case class Leaf(value: Int) extends Tree
case class Branch(left: Tree, right: Tree) extends Tree
def fold[A](tree: Tree)(leafFn: Int => A)(combine: (A, A) => A): A =
  tree match
    case Leaf(v) => leafFn(v)
    case Branch(l, r) => combine(fold(l)(leafFn)(combine), fold(r)(leafFn)(combine))
@main def main(): Unit =
  val tree = Branch(Branch(Leaf(1), Leaf(2)), Leaf(3))
  println(fold(tree)(v => v)((a, b) => a + b))

A new step counts the leaves

The same fold walks the same tree again. A different leaf step and combine step now count leaves instead of summing.

sealed trait Tree
case class Leaf(value: Int) extends Tree
case class Branch(left: Tree, right: Tree) extends Tree
def fold[A](tree: Tree)(leafFn: Int => A)(combine: (A, A) => A): A =
  tree match
    case Leaf(v) => leafFn(v)
    case Branch(l, r) => combine(fold(l)(leafFn)(combine), fold(r)(leafFn)(combine))
@main def main(): Unit =
  val tree = Branch(Branch(Leaf(1), Leaf(2)), Leaf(3))
  println(fold(tree)(v => 1)((a, b) => a + b))

A new step collects the values

The fold shape stays unchanged a third time. The leaf step wraps each value in a list and the combine step joins the lists.

sealed trait Tree
case class Leaf(value: Int) extends Tree
case class Branch(left: Tree, right: Tree) extends Tree
def fold[A](tree: Tree)(leafFn: Int => A)(combine: (A, A) => A): A =
  tree match
    case Leaf(v) => leafFn(v)
    case Branch(l, r) => combine(fold(l)(leafFn)(combine), fold(r)(leafFn)(combine))
@main def main(): Unit =
  val tree = Branch(Branch(Leaf(1), Leaf(2)), Leaf(3))
  println(fold(tree)(v => List(v))((a, b) => a ++ b))

Example

sealed trait Tree
case class Leaf(value: Int) extends Tree
case class Branch(left: Tree, right: Tree) extends Tree
def fold[A](tree: Tree)(leafFn: Int => A)(combine: (A, A) => A): A =
  tree match
    case Leaf(v) => leafFn(v)
    case Branch(l, r) => combine(fold(l)(leafFn)(combine), fold(r)(leafFn)(combine))
@main def main(): Unit =
  val tree = Branch(Leaf(2), Branch(Leaf(3), Leaf(4)))
  println(fold(tree)(v => v)((a, b) => a + b))
  println(fold(tree)(v => v)((a, b) => if a > b then a else b))
  println(fold(tree)(v => 1)((a, b) => a + b))

Key points

  • Tree: A tree is data that branches, with leaves holding values and branches holding smaller trees.
  • Catamorphism: A catamorphism is a fold that collapses a whole structure into one result.
  • Fold function: The fold function handles the walking, so callers never write the recursion again.
  • Leaf step: The leaf step turns one leaf value into a partial result.
  • Combine step: The combine step merges two partial results from two branches into one result.

In this example, one tree is folded three times with the same fold function. The first fold sums the values and the second fold finds the largest value. The third fold counts the leaves, so one recursion shape serves three jobs.

Note

Scala has no built-in fold for a custom tree, so this fold is written once by hand and then reused.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Scastie

Exercise

What changes when you reuse a tree fold for a new job?