Recursion schemes: алгебра рекурсии cata, ana, hylo, para

В уроке 12 мы написали парсер арифметики и руками собрали рекурсивный eval-функцию: для каждого вида узла свой case, в binop рекурсивно идём в left и right, в neg в child. Это работало, но если присмотреться, за разными case-ами скрыта одна и та же форма обхода: спустись к листам, верни значение, склей снизу вверх.

Сегодня мы выясним, что эта форма имеет имя, и не одно. Свёртка снизу вверх это catamorphism, обратная процедура (из семени развернуть структуру) это anamorphism, их композиция это hylomorphism. Каждое имя соответствует конкретной алгебраической форме, и вместе они составляют семейство “recursion schemes”.

После урока ты прочитаешь без шифровки Patrick Thomson, Bartosz Milewski, и поймёшь, почему recursion-schemes в Haskell это не библиотека для параноиков, а способ структурировать обход любой рекурсивной структуры.

Fix: вынос рекурсии из типа

Начнём с обыкновенного списка. Привычное определение:

type List<A> = { readonly kind: 'nil' } | { readonly kind: 'cons'; readonly head: A; readonly tail: List<A> };

tail ссылается на сам List<A>. Рекурсия зашита в тип.

Вынесем рекурсию наружу. Сделаем нерекурсивную версию ListF<A, R>, где R это “точка рекурсии”:

type ListF<A, R> =
  | { readonly kind: 'nil' }
  | { readonly kind: 'cons'; readonly head: A; readonly tail: R };

Это просто структура с дыркой R там, где раньше был List<A>. Чтобы вернуть рекурсию, оборачиваем ListF в Fix:

type Fix<F> = { readonly unfix: F };

// Список через Fix:
type ListR<A> = Fix<ListF<A, ListR<A>>>;

const nil = <A>(): ListR<A> => ({ unfix: { kind: 'nil' } });
const cons = <A>(head: A, tail: ListR<A>): ListR<A> => ({
  unfix: { kind: 'cons', head, tail },
});

const sample: ListR<number> = cons(1, cons(2, cons(3, nil())));

Fix это просто обёртка { unfix: F }, которая разрешает рекурсию: каждый узел ListF<A, _> имеет в роли _ ещё один Fix<ListF<A, _>>. Это самая дорогая часть рекурсии-схем: нужно перевести знакомые типы в эту форму. После перевода все комбинаторы становятся простыми и универсальными.

Аналогично для бинарного дерева:

type TreeF<A, R> =
  | { readonly kind: 'leaf' }
  | { readonly kind: 'node'; readonly value: A; readonly left: R; readonly right: R };

type Tree<A> = Fix<TreeF<A, Tree<A>>>;

И для AST из урока 12:

type ExprF<R> =
  | { readonly kind: 'num'; readonly value: number }
  | { readonly kind: 'binop'; readonly op: '+' | '-' | '*' | '/'; readonly left: R; readonly right: R }
  | { readonly kind: 'neg'; readonly child: R };

type Expr = Fix<ExprF<Expr>>;

ExprF<R> это AST с дырками вместо вложенных выражений. Expr = Fix<ExprF<Expr>> возвращает рекурсию. Прелесть в том, что теперь форма ExprF это просто Functor (с очевидным map), и поверх этого Functor мы получим все обходы как алгебры.

Catamorphism: универсальный fold

cata принимает F-алгебру F<A> -> A и Fix<F>, возвращает A:

type Algebra<F, A> = (fa: F) => A;

const cata =
  <F, A>(map: <X, Y>(f: (x: X) => Y, fa: F & object) => F & object) =>
  (alg: (fa: F) => A) =>
  (fix: Fix<F>): A =>
    alg(map((sub: Fix<F>) => cata(map)(alg)(sub), fix.unfix));

Текстом: чтобы посчитать значение в узле, сначала рекурсивно посчитай значения в детях (это map), потом примени алгебру alg к узлу, в котором дети уже свёрнуты в A.

Чтобы это работало, каждой нашей F нужен Functor-инстанс. Для ListF<A, _>:

const mapListF = <A, R, S>(f: (r: R) => S, fa: ListF<A, R>): ListF<A, S> =>
  fa.kind === 'nil' ? { kind: 'nil' } : { kind: 'cons', head: fa.head, tail: f(fa.tail) };

Теперь свёртка списка тривиальна:

const cataList = <A, B>(alg: (fa: ListF<A, B>) => B) => (list: ListR<A>): B => {
  const go = (l: ListR<A>): B => alg(mapListF(go, l.unfix));
  return go(list);
};

// сумма списка через cata
const sumAlg: (fa: ListF<number, number>) => number = (fa) =>
  fa.kind === 'nil' ? 0 : fa.head + fa.tail;

const total = cataList(sumAlg)(sample); // 1 + 2 + 3 = 6

Сравни с обычным reduce:

const sumReduce = (xs: number[]) => xs.reduce((acc, x) => acc + x, 0);

Семантика та же. Но cata универсален: тот же cataList сворачивает не только в число, но и в строку, в дерево, в html. Меняется только алгебра.

Ещё один пример, длина списка:

const lenAlg: (fa: ListF<unknown, number>) => number = (fa) =>
  fa.kind === 'nil' ? 0 : 1 + fa.tail;

const len = cataList(lenAlg)(sample); // 3

Логика обхода списка одна, написана один раз. Алгебры разные.