Я тут поминал уже (всё в nlab.org написано на самом деле), что списки являются инициальными алгебрами для функтора
1+A × X
, алгебры над которым - что-то вроде state machines.
Аналогично сидел и думал, э, а для функтора 1+X2
, у которого инициальной алгеброй (минимальной неподвижной точкой) является двоичное дерево, ака корень шестой степени из единицы, у этого функтора что за алгебры? Doh, задать такую алгебру эквивалентно заданию точки и бинарной операции.
Дык. Можно ж, наверное, и не одну бинарную операцию добавить, а также пару унарных или там тернарных. И инициальной алгеброй будет объект из всех возможных деревьев. AST, то есть.
Так это же мы пришли уже к алгебраическим теориям, в категорном смысле (см. везде).
Ну хм, а как насчёт лямбда-исчисления? Надо будет разобраться; ведь всё та же редукция. Всё тот же катаморфизм. Да? Нет? Не знаем? Надо подумать.