[Перевод] Категории Клейсли
Композиция логирования Вы видели, как сделать категорию типов и чистых функций. Я также упомянул, что есть способ смоделировать побочные эффекты, или нечистые функции, в рамках теории категорий. Давайте рассмотрим пример: функции, которые логируют или записывают ход своего выполнения.Что-то, что в императивном языке, скорее всего, будет реализовано посредством мутации некоторого глобального состояния, например: string logger;
bool negate (bool b) { logger += «Not so!»; return! b; } Вы знаете, что это не чистая функция, потому что ее версия с кешированием результатов будет не в состоянии записать в лог. Эта функция имеет побочные эффекты.В современном программировании, мы стараемся держаться подальше от глобального изменяемого состояния, пока это возможно — как минимум, из-за сложностей с параллелизмом. И вы никогда не пишете подобный код в библиотеки.
К счастью для нас, можно сделать эту функцию чистой. Нужно просто передать лог в явном виде в функцию и из нее. Давайте сделаем это путем добавления строкового аргумента, и возвращение пары из основного результата и строки, содержащей обновленный журнал:
pair
Есть ли способ сделать то же самое менее навязчиво? Есть ли способ разделить проблемы? В этом простом примере, основная цель функции negate — превратить один Boolean в другой. Логирование вторично. Конечно, сообщение, которое логируется, является специфичным для функции, но агрегирование сообщений в один непрерывный лог — отдельная задача. Мы все еще хотим, что функция возвращала строку, но мы хотели бы освободить ее от задачи создания лога. Вот компромиссное решение:
pair
string toUpper (string s) {
string result;
int (*toupperp)(int) = &toupper; // toupper is overloaded
transform (begin (s), end (s), back_inserter (result), toupperp);
return result;
}
и другая, которая разбивает строку на вектор строк, разбивая ее по пробелам:
vector
Мы «обогатим» возвращаемые значения этих функций. Давайте сделаем это в общем виде путем определения шаблона Writer, который инкапсулирует пару, первый компонент которой — значение произвольного типа А, а второй компонент — строка:
template
Writer
Категория Writer Идея обогащать типы возвращаемых значений функций для того, чтобы прицепить некоторую дополнительную функциональность оказывается очень полезной. Мы увидим еще много таких примеров. Отправной точкой является наша обычная категория типов и функций. Мы оставим типы как объекты, но переопределим морфизмы, как обогащенные функции.Например, предположим, что мы хотим обогатить функцию isEven, которая преобразует int в bool. Мы превратим ее в морфизм, который представлен обогащенной функцией. Важно то, что этот морфизм до сих пор считается стрелкой между объектами int и bool, хотя украшенная функция возвращает пару:
pair
Writer на Haskell Та же конструкция на Haskell будет намного более лаконична, и компилятор нам поможет намного больше. Давайте начнем с определения типа Writer: type Writer a = (a, String) Здесь я просто определяю псевдоним типа, эквивалент typedef (или using) в C++. Тип Writer параметризирован переменной типа и эквивалентен паре a и String. Синтаксис для пар минимален: всего два имени в скобках, через запятую.Наши морфизмы — функции из произвольного типа к определенному типу Writer:
a → Writer b Мы объявим композицию как забавный инфиксный оператор, который иногда называют «рыба»: (>=>) :: (a → Writer b) → (b → Writer c) → (a → Writer c) Это функция от двух аргументов, каждый из которых сам по себе функция, и она возвращает функцию. Первый аргумент имеет тип (a → Writer b), второй (b → Writer c) и результат (a → Writer c).Вот определение этого инфиксного оператора — два аргумента m1 и m2, появляются по обе стороны от рыбного символа:
m1 >=> m2 = \x → let (y, s1) = m1 x (z, s2) = m2 y in (z, s1 ++ s2) В результате получается лямбда функция одного аргумента x. Лямбда записывается в виде обратной косой черты — можно думать о ней, как о греческой букве λ с ампутированной ногой.Слово let позволяет объявить вспомогательные переменные. Здесь результат вызова m1 сматчен с парой переменных (у, s1), а результат вызова m2 с аргументом y из первого паттерна, будет сматчен с (z, s2).
В Haskell матчинг пар — обычная замена использованию геттеров, как мы это делали в С++. Помимо этого есть довольно простое соответствие между двумя реализациями.
Значение let выражения содержится после in: здесь это пара, чей первый компонент z, а второй компонент — объединение двух строк, s1 ++ s2.
Я также определю единичный морфизм для нашей категории, но по причинам, которые станут ясны значительно позже, я буду называть его return.
return: a → Writer a return x = (x,») Для полноты давайте напишем Haskell версии, обогащенных функций upCase (прим. переводчика: имелось ввиду toUpper из C++ примера, но функция с таким именем уже есть в стандартном модуле Prelude) и toWords: upCase: String → Writer String upCase s = (map toUpper s, «upCase »)
toWords: String → Writer [String] toWords s = (words s, «toWords ») Функция map соответствует функции transform в C++. Она применяет функцию на символах toUpper к строке s. Вспомогательная функция words определена в стандартной библиотеке Prelude.Наконец, композиция этих двух функций строится с помощью оператора рыбы:
process: String → Writer [String] process = upCase >=> toWords Категории Клейсли Вы, наверное, догадались, что я не придумал эту категорию на лету. Это пример так называемой категории Клейсли — категории на основе монады. Мы пока не готовы обсуждать монады, но я хотел показать, что они могут делать. Для наших ограниченных целей, категория Клейсли имеет типы, как объекты. Морфизмы из типа A в тип B — это функции, которые идут от A к типу, полученному из B с помощью особого обогащения. Каждая категория Клейсли определяет свой собственный способ композиции таких морфизмов, а также тождественные морфизмы по отношению к этой композиции. (Позже мы увидим, что неточный термин «обогащение» соответствует понятию эндофунктора в категории.)Конкретная монада, которую я использовал в качестве основы категории в этом посте называется writer и она используется для логирования или отслеживания выполнения функций. Она также является примером более общего механизма для встраивания эффектов в чистые вычисления. Вы видели ранее, что мы могли бы моделировать типы языка программирования и функции в категории множеств (без учета bottom, как обычно). Здесь мы расширили эту модель до несколько иной категории, категории, где морфизмы представлены обогащенными функциями, и их композиция делает больше, чем просто передать результат одной функции на вход другой. У нас есть на одну степень свободы больше: можно изменять саму композицию. Оказывается, что это именно эта степень свободы позволяет дать простую денотационную семантику программам, которые в императивных языках традиционно реализованы с использованием побочных эффектов.
Теория категорий для программистов: предисловиеКатегория: суть композицииТипы и функцииКатегории, большие и малыеКатегории Клейсли
