Поэтому я часто слышу слова «катаморфизм» и «схемы рекурсии». О чем это?

Катаморфизмы (или ката) являются обобщением концепции складки в функциональном программировании. Учитывая F-алгебру и рекурсивную структуру данных, катаморфизм будет производить значение путем рекурсивной оценки вашей структуры данных.

Что такое F-алгебра? Может быть, вы можете сначала показать несколько примеров кода?

Настройка не так проста, поэтому давайте начнем с простого. Допустим, у вас есть следующая структура данных для представления выражения:

А простое выражение может выглядеть так:

Бесполезно иметь только структуру данных выражения, конечно, вам понадобится функция для оценки и получения результата:

Вот здесь и появляется обобщение катаморфизма:

🤨, а в чем смысл? Вы просто применяете аргумент к функции?

Потому что это notReallyCata. Настоящая cata функция является универсальной и не зависит от какой-либо конкретной структуры данных или функции оценщика. Видите ли, создание рекурсивной структуры данных с последующим ее сворачиванием - это общий шаблон, который cata пытается обобщить.

Хорошо, тогда как выглядит настоящая ката?

🤯

Вот почему мы начали с notReallyCata. Мы разберем реализацию позже, пока она не станет щелчком. Но теперь давайте продолжим наш Expression пример. Во-первых, нам нужно избавиться от рекурсии, введя параметр типа:

Все ссылки на Expression заменяются параметром типа a, поэтому структура данных больше не является рекурсивной.

Почему в конце конструкторов типов стоит F?

Рад, что вы спросили - это намек на то, что ExpressionF может быть Functor:

Ничего особенного, просто применяю некоторую функцию к обернутой структуре, сохраняющей значение.

Не уверен, зачем нам это нужно

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

Но получился другой тип:

expr сворачивает все в один Expression, а exprF кодирует информацию об уровне вложенности нашего дерева выражений. Говоря об оценке, вот как мы можем реализовать eval для ExpressionF:

Основное отличие от исходного evalExpr состоит в том, что у нас нет рекурсивного вызова evalExprF (ExpressionF не рекурсивный, помните?). Это также означает, что наш оценщик может работать только с выражением одноуровневого:

И не будем компилировать на этом:

Просто потому, что exprF ожидает ExpressionF Int, а мы выставляем ExpressionF (ExpressionF Int).

Чтобы заставить его работать, мы могли бы определить другого оценщика:

Выглядит немного специально, что, если у вас есть глубоко вложенные выражения?

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

Есть способ обобщить это вложение с новым типом:

Исправить? Похоже на рекурсивную структуру данных, которая мало что делает. Чем это полезно?

Давайте сначала посмотрим на выражение перед знаком равенства: действительно Fix - это рекурсивная структура данных с одним параметром типа f. Этот параметр имеет вид * -> *, например. он также принимает параметр типа. Например, вы не можете построить Fix с указанием Int или Bool, это должно быть что-то вроде Maybe, List или… ExpressionF. Вот почему мы ввели параметр типа для ExpressionF. Далее, после знака равенства у нас есть конструктор одного типа Fx, принимающий единственный аргумент типа f (Fix f), который по сути является выражением, конструирующим значение f. В случае Maybe это будет Maybe (Fix Maybe), а затем все будет упаковано с Fx в тип Fix Maybe.

Сигнатура типа сначала сбивает с толку, потому что конструктор типа может иметь то же имя, что и сам тип, плюс ссылки на себя. Но это не что иное, как просто перенос типа более высокого порядка в структуру данных. Кстати, unfix является противоположностью Fx, и все, что он делает, это сопоставление с образцом на Fx и возвращает значение в оболочке, ничего страшного.

Теперь мы заменим каждый ExpressionF в нашем дереве выражения на Fix ExpressionF. Обратите внимание на разницу в построении выражений с Fx и без него - они в основном одинаковы, за исключением того, что нам нужно добавить Fx $:

Результирующий тип «фиксированной» версии - Fix ExpressionF, поэтому мы вернулись к рекурсивному представлению, но теперь мы должны использовать unfix функцию, чтобы вернуть нашу нерекурсивную структуру данных.

Каковы преимущества использования Fix? Похоже, это тот же подход, что и исходный тип Expression, но теперь у нас есть эта странная Fix и unfix ерунда?

Да, но мы пытаемся обобщить процесс сворачивания, он требует введения дополнительных абстракций, таких как Fix и Algebra, которые мы обсудим позже. Потерпите меня, позже это станет более понятным.

Итак, у нас есть «фиксированная» структура данных, как будет выглядеть функция оценки?

Учитывая Fix ExpressionF, единственное, что мы можем сделать с ним, - это вызвать unfix, который выдаст ExpressionF (Fix ExpressionF):

Возвращенный ExpressionF может быть одним из наших ValueF, AddF или MultF с Fix ExpressionF в качестве параметра типа. Имеет смысл провести сопоставление с образцом и решить, что делать дальше:

Да, он выглядит так же, как наш самый первый рекурсивный вычислитель для Expression, с добавлением необходимости разворачивать выражение с помощью unfix. Так зачем вообще возиться с Fix?

Вот ключ: мы повторно будем использовать нашу исходную программу оценки "без исправлений" для ExpressionF и каким-то образом распространим ее по структуре Fix ExpressionF. Итак, это должна быть функция, принимающая два аргумента - оценщик и структура для оценки:

Давайте попробуем разобраться в реализации - первое, что нужно сделать, это использовать unfix для получения ExpressionF, а затем, возможно, передать его в evaluator:

Очевидно, это не работает, evaluator ожидает ExpressionF Int, а не ExpressionF (Fix ExpressionF). Кстати, помните, что ExpressionF - это Functor? Здесь это удобно - мы можем использовать fmap, чтобы применить тот же процесс к внутреннему уровню нашего дерева выражений:

Найдите минутку и подумайте, что происходит: мы передаем рекурсивную функцию almostCata evaluator в fmap. Если текущее выражение AddF или MultF, тогда эта функция будет передана на один уровень глубже, и fmap будет вызван снова. Это будет происходить до тех пор, пока мы не достигнем ValueF, fmapping over ValueF вернет значение типа ExpressionF Int, и это именно то, что принимает наша evaluator функция.

Глядя на almostCata, мы видим, что на самом деле он не имеет ничего специфического для типа ExpressionF или Int и теоретически может быть обобщен с помощью некоторого параметра типа f. Единственным ограничением должно быть наличие экземпляра Functor для f, потому что мы используем fmap:

И это последняя версия cata. Вот полная реализация с некоторыми примерами использования:

Думаю, это круто. Но почему?

Многие концепции теории категорий и функционального программирования довольно абстрактны, и иногда трудно найти немедленное практическое применение той или иной идее. Но поиск абстракций и обобщений полезен для поиска шаблонов и элегантных решений проблем, которые в противном случае требуют специальной реализации.

Кстати, обобщив нашу ExpressionF -> Int функцию на Functor f => (f a -> a), мы обнаружили еще одну важную концепцию, которая называется F-алгебра. По сути, F-алгебра - это тройка функтора f, некоторого типа a и функции-вычислителя f a -> a. Обратите внимание, что a здесь не полиморфный - это должен быть конкретный тип, например Int или Bool, и он называется типом носителя. Для любого эндофунктора f вы можете создать на его основе несколько F-алгебр. Возьмем наш пример выражений: эндофунктор f - это ExpressionF, a - это Int, а вычислитель - это evalExprF. Но мы можем изменить тип носителя и создать больше алгебр:

Это просто разные оценщики, которые можно передать в cata, верно?

Да, мы выбираем разные типы операторов связи и нашу реализацию. Но вот трюк - есть мать всех оценщиков, которых мы можем создать, выбрав для нас тип оператора… Fix ExprF.

Оценка до Int или Bool имеет смысл, но что будет оценивать этот initialAlgebra? Когда мне нужно получить Fix что-то в результате работы моего оценщика?

Конечно, вы сами не напишете ничего подобного, просто хотите показать вам более глубокий смысл f-алгебр и ката. Фактически, у нас уже есть реализация для такого оценщика, и это именно Fx конструктор:

Подождите, Fx оценщик? Это безумие.

Да, и он делает самое простое, что вы можете сделать - сохранять выражение в структуре данных. В то время как все другие оценщики (algebra0, algebra1) вырабатывали какое-то значение, уменьшая выражение (например, выполняя сумму или конкатенацию), Fx просто обертывает выражение без потери каких-либо данных.

Вот почему мы в первую очередь ввели Fix - вы сначала оцениваете свою исходную структуру данных с помощью Fx в начальной алгебре Fix f, а затем, используя cata, «реальная» оценка происходит путем fmap обработки вашего конкретного оценщика над начальной алгеброй.

С точки зрения теории категорий все алгебры, основанные на одном и том же эндофункторе, образуют категорию. Эта категория имеет начальный объект, который является нашей начальной алгеброй, созданной путем выбора типа носителя как Fix f. В блоге Бартоша Милевски есть несколько замечательных сообщений, которые я настоятельно рекомендую проверить, если вы хотите получить глубокое категоричное понимание.

Это все еще довольно сложно понять, я не думаю, что полностью понимаю концепцию

Всегда лучше работать руками: попробуйте заново реализовать Fix и cata самостоятельно, подумайте о возможных структурах данных и алгебрах. Например, String можно представить рекурсивно (как Char начало и конец String), length строки можно вычислить с cata. Вот несколько полезных ресурсов для дальнейшего чтения: