Generalized Folds

The technique we used to derive foldtree works for any OCaml variant type t:

  • Write a recursive fold function that takes in one argument for each constructor of t.

  • That fold function matches against the constructors, calling itself recursively on any value of type t that it encounters.

  • Use the appropriate argument of fold to combine the results of all recursive calls as well as all data not of type t at each constructor.

This technique constructs something called a catamorphism, aka a generalized fold operation. To learn more about catamorphisms, take a course on category theory, such as CS 6117.

results matching ""

    No results matching ""