Каким образом у Scala Option складывается катаморфизм?

Question

Ответ на этот вопрос предполагает, что метод сгиба на Option в Scala является катаморфизмом. Из википедии катамофизм - это "уникальный гомоморфизм из начальной алгебры в некоторую другую алгебру. Эта концепция была применена к функциональному программированию как складки". Так что это кажется справедливым, но приводит меня к начальной алгебре в качестве начального объекта в категории F-алгебр.

Таким образом, если сгиб на Option действительно является катамофизмом, то должен быть некоторый функтор F, чтобы создать категорию F-алгебр, где Option будет исходным объектом. Я не могу понять, что это за функтор.

Для списков типа A функтор F является F[X] = 1 + A * X, Это имеет смысл, потому что List является рекурсивным типом данных, поэтому если X является List[A] то вышеизложенное гласит, что список типов A либо пустой список (1), или же (+) пара (*) из A и List[A], Но вариант не рекурсивный. Option[A] будет просто 1 + A (Ничего или A). Так что я не вижу, где находится функтор.

Просто чтобы прояснить, я понимаю, что Option уже является функтором, поскольку A в Option[A], но то, что сделано для списков, отличается, A исправлен, и функтор используется для описания того, как рекурсивно конструировать тип данных.

С другой стороны, если это не катаморфизм, его, вероятно, не следует называть сгибом, так как это приводит к некоторой путанице.

Answer 1

Ну, комментарии в правильном направлении. Я только начинающий, поэтому у меня, вероятно, есть некоторые заблуждения. Да, весь смысл в том, чтобы иметь возможность моделировать рекурсивные типы, но я думаю, что ничто не исключает "нерекурсивную" F-алгебру. Поскольку исходная алгебра является решением "наименьшей неподвижной точки" уравнения X ~= F X. В случае Option решение является тривиальным, поскольку рекурсия здесь не используется:)

Другие примеры начальных алгебр:

Список [X] = 1 + A * X для представления списка = Nil | Минусы список

Дерево [X] = A + A * X * X для представления дерева = Лист a | Узел дерево дерево

Точно так же:

Опция [X] = 1 + A для представления опции = Нет | Некоторые

Обоснование существования "постоянного" функтора довольно просто, как вы представляете узел дерева? Фактически, для алгебраической модели (простых) рекурсивных типов данных вам нужны только следующие функторы:

• U (Единица, представляет пустой)
• K (постоянная, фиксирует значение)
• Я (идентичность, представляю рекурсивную позицию)
• * (товар)
• + (совместный продукт)

Хорошая ссылка, которую я нашел, - это функциональное общее программирование

Бесстыдный плагин: я играю с этими понятиями в коде в scala-reggen