Хабрахабр

Монады с точки зрения программистов (и немного теории категорий)

Он сам вам об этом расскажет в первые 5 минут общения и обязательно попробует объяснить. Как узнать, что человек понял, что такое монады? А ещё напишет об этом текст и по возможности где-нибудь его опубликует, чтобы все остальные тоже поняли, что такое монады.

Их часто пытаются объяснить, отталкиваясь от частных случаев и сразу приводя примеры использования. Среди функциональных программистов, особенно на Haskell, монады стали чем-то вроде локального мема. Из-за этого слушатель может не уловить основную суть понятия, а монады так и останутся чёрной магией, ну или просто средством костылизации побочных эффектов в чисто функциональных языках.

Я сначала расскажу про базовые понятия теории категорий, а затем мы с практической точки зрения подойдём к определению монады и увидим, что на самом деле очень многие программисты пользуются этой мощной абстракцией в одном из её проявлений.

Моё изложение во многом основывается на книге Бартоша Милевски "Теория категорий для программистов", которая создавалась как серия блогпостов, доступна в PDF, а недавно вышла в бумаге.

В упомянутой книге есть примеры и на С++, можете сравнить чистоту и понятность кода. Примеры приводятся на Haskell, предполагается, что читатель знаком с синтаксисом и основными понятиями языка.

Определение

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

Используется следующая нотация:

  • ObC — объекты категории C;
  • HomC(A, B) — морфизмы из A в B;
  • g ∘ f — композиция морфизмов f и g.

В определении категории на морфизмы накладываются дополнительные ограничения:

  1. Для пары морфизмов f и g, если f — морфизм из A в B (f ∈ Hom(A, B)), g — морфизм из B в C (g ∈ Hom(B, C)), то существует их композиция g ∘ f — морфизм из A в C (g ∘ f ∈ Hom(A, C)).
  2. Для каждого объекта задан тождественный морфизм idA ∈ Hom(A, A).

Существуют два важных свойства, которым должна удовлетворять любая категория (аксиомы теории категорий):

  1. Ассоциативность композиции: h ∘ (g ∘ f) = (h ∘ g) ∘ f;
  2. Композиция с тождественным морфизмом: если f ∈ Hom(A, B), то f ∘ idA = idB ∘ f = f.

В принципе, любой ориентированный граф можно достроить до категории, добавив композиции морфизмов и тождественные морфизмы, если необходимо. Категории очень легко и естественно визуализируются как ориентированные графы.

Это позволяет формулировать двойственные утверждения и теоремы, истинность которых не меняется при обращении стрелок. Для любой категории можно определить двойственную категорию (обозначается Cop, в которой морфизмы получены разворотом стрелок исходной категории, а объекты — те же самые.

Категории, в которых классы объектов и морфизмов всё-таки являются множествами, называются малыми категориями. Объекты и морфизмы не обязательно образуют множества (в классическом смысле из теории множеств), поэтому в общем случае используется словосочетание "класс объектов". Далее мы будем работать только с ними.

Типы и функции

Например, типы Int и Bool — это примеры объектов, а функция типа Int -> Bool — морфизм. Рассмотрим категорию, в которой объектами являются типы языка Haskell, а морфизмами — функции.

Тождественным морфизмом является функция id, возвращающая свой аргумент:

id :: a -> a
id x = x

Композиция морфизмов — это композиция функций, причём синтаксис этой операции на Haskell почти идентичен математической нотации:

f :: a -> b
g :: b -> c
g . f :: a -> c
(g . f) x = g (f x)

Типы также можно рассматривать как множества допустимых значений, а функции — как отображения множеств, но с одной оговоркой: вычисления могут не завершиться. Категория, в которой объекты представляют собой множества, а морфизмы — отображения, называется Set. Считается, что любая функция либо возвращает значение типа, указанного в сигнатуре, либо значение типа bottom. Для обозначения такой ситуации вводится специальный тип bottom, обозначаемый _|_. Для упрощения изложения мы будем работать с ней так же, как с категорией Set. Категория типов языка Haskell, в которой учитывается эта особенность, называется Hask. Действительно, функциональный тип a -> b — это тоже тип языка Haskell. Любопытно, что в этой категории морфизмы между двумя объектами в свою очередь образуют множество, которое является объектом в этой же категории: HomC(A, B) ∈ C.

Рассмотрим несколько примеров типов с точки зрения теории категорий.

Существует даже полиморфная функция absurd, которую можно определить, но невозможно вызвать, поскольку для вызова ей нужно передать значение типа Void, а таких значений нет: Пустому множеству соответствует тип Void, у которого нет значений (такой тип называется ненаселённым).

absurd :: Void -> a

Полиморфная функция unit возвращает это значение, принимая на вход любой другой тип: Множеству из одного элемента соответствует тип Unit, единственное значение которого — пустой кортеж, также обозначаемый ().

unit :: a -> Unit
unit _ = ()

Множество из двух элементов — логический тип Bool:

data Bool = True | False

Построим категорию, объектами в которой являются типы Void, Unit и Bool.

В обратную сторону морфизмов нет, поскольку мы никак не можем получить значения ненаселённого типа Void, просто потому что их не существует, а значит и не можем определить тело этой функции. Из Void выходят только морфизмы, соответствующие функции absurd, один в Bool, один в Unit.

А вот для реализации функции типа Unit -> Bool возможны варианты. Функция типа Bool -> Unit может быть только одна, unit, поскольку независимо от входного значения мы можем вернуть только пустой кортеж. Таким образом, получили два морфизма из Unit в Bool: Такая функция в любом случае будет принимать значение (), но вернуть можно либо True, либо False.

true, false :: a -> Bool
true _ = True
false _ = False

Морфизмы из Bool в Bool — это булевы функции от одного аргумента, которых 4 штуки (в общем случае количество булевых функций от n аргументов — 22n): id, true и false, которые мы уже определяли выше, а также функция not:

not :: Bool -> Bool
not True = False
not False = True

Добавив тождественные морфизмы, получим следующую категорию:

В дальнейшем изложении будем использовать Haskell-подобную нотацию сигнатуры типов для обозначения морфизмов.

Для двух категорий, C и D, функтор F осуществляет два вида преобразований. Функтор — это отображение категорий. Если a — объект из категории C, то F a — соответствующий ему объект из категории D, полученный в результате применения функтора. Во-первых, функтор преобразует объекты из категории C в объекты из категории D. Во-вторых, функтор действует на морфизмы: морфизм f :: a -> b в категории C преобразуется в морфизм F f :: F a -> F b в категории D.

Кроме того, должны выполняться "законы сохранения" композиции и тождественного морфизма:

  1. Если h = g ∘ f, то F h = F g ∘ F f.
  2. Если ida — тождественный морфизм для объекта a, то F ida = idF a — тождественный морфизм для объекта F a.

Это верно и для крайних случаев, например, когда результирующая категория состоит из одного объекта. Таким образом, функтор не "ломает" структуру категории: то, что было связано морфизмом в исходной категории, будет связано и в результирующей. Тогда все морфизмы исходной категории отобразятся в тождественный морфизм для этого объекта, но упомянутые выше законы нарушены не будут.

Для двух функторов, F :: C -> D и G :: D -> E можно определить композицию G . Функторы можно комбинировать аналогично функциям. Кроме того, для каждой категории несложно построить тождественный функтор, который будет переводить как объекты, так и морфизмы, в самих себя. F :: C -> E. Функторы, действующие из категории в неё саму, называются эндофункторы. Обозначим их IdC, IdD и IdE.

Получим категорию малых категорий, которая называется Cat (название периодически порождает сложные мемы с кошками). Посмотрим на эту картинку сильно издалека, так, чтобы сами категории превратились в точки-объекты, а функторы — в стрелки между ними (морфизмы).

Они преобразуют типы в другие типы и, кроме того, каким-то образом преобразуют функции, работающие с этими типами. Вернёмся к категории типов языка Haskell и будем работать с эндофункторами в этой категории.

Конструктор типа Maybe является примером такого функтора, он преобразует тип a в тип Maybe a (сам по себе Maybe не является типом!):

data Maybe a = Nothing | Just a

Это действие можно записать в виде функции высшего порядка fmap. Для преобразования морфизмов, необходимо уметь получать из функции f :: a -> b функцию F f :: Maybe a -> Maybe b. Обратите внимание, что тип этой функции как раз наглядно описывает преобразование морфизмов (из одной функции получаем другую):

-- f F f
-- /------\ /------------------\
fmap :: (a -> b) -> (Maybe a -> Maybe b)
fmap _ Nothing = Nothing
fmap f (Just x) = Just (f x)

Существует целый класс типов, который так и называется, Functor. Конечно, Maybe — не единственный функтор. Единственным методом этого класса является функция fmap, показывающая, как преобразуются морфизмы (а преобразование объектов — это применение конструктора типа к конкретным типам):

class Functor f where fmap :: (a -> b) -> f a -> f b

Если опустить скобки вокруг f a -> f b, как это сделано в определении выше, то такая сигнатура лучше подойдёт для описания функторов как контейнеров. В более прикладном смысле функторы — это контейнеры, которые хранят значения других типов, а функция fmap позволяет преобразовывать объекты внутри этих контейнеров.

предполагалось, что у них нет побочных эффектов. Все функции, которые были рассмотрены до этого, были чистыми, т.е. Это функции в математическом смысле: результат чистой функции зависит только от значения её аргумента, он не меняется из-за места или времени вызова.

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

Пока что их реализация всего лишь использует встроенные функции toUpper и words: В качестве примера возьмём функции для преобразования строк: upCase, переводящую все символы строки в верхний регистр, и toWords, разбивающую строки на слова.

upCase :: String -> String
upCase = map toUpper toWords :: String -> [String]
toWords = words

Типы функций позволяют составить их композицию:

processString :: String -> [String]
processString = toWords . upCase

Мы хотим, чтобы после применения функции processString в логе содержалась запись "upCase toWords". Чтобы не отвлекаться на сложности реализации, в качестве представления лога возьмём просто строку.

Хотелось бы во-первых, добавить информацию на уровне типов о том, что будет выполняться логгирование, и во-вторых, минимизировать дополнительные действия, которые придётся проделать сторонним разработчикам для работы с этими функциями. Запись в лог — побочное действие функций, мало относящееся к их основному функционалу.

Создадим новый тип данных, который будет помимо самих значений типа a хранить ещё и строку, в которую каждая вызванная функция будет добавлять своё имя.

newtype Writer a = Writer (a, String)

Заметим, что Writer — это функтор, мы легко можем описать для него функцию fmap:

instance Functor Writer where fmap f (Writer (x, s)) = Writer (f x, s)

Преобразуем функции upCase и toWords и сделаем так, чтобы они возвращали значение, "завёрнутое" в тип Writer:

upCase :: String -> Writer String
upCase s = Writer (map toUpper s, "upCase ") toWords :: String -> Writer [String]
toWords s = Writer (words s, "toWords ")

Определим специальную функцию для композиции, которая сначала получает значение типа b и первую строку, передаёт это значение второй функции, получает значение типа c и вторую строку и в качестве финального результата возвращает значение типа c и конкатенацию строк, полученных при вычислении: Теперь мы больше не можем записать композицию этих функций так же, как раньше, из-за несоответствия типов.

compose :: (a -> Writer b) -> (b -> Writer c) -> (a -> Writer c)
compose f g = \x -> let Writer (y, s1) = f x Writer (z, s2) = g y in Writer (z, s1 ++ s2)

Реализация функции processString принимает вид:

processString :: String -> [String]
processString = compose toWords upCase

Мы можем заменить все функции (морфизмы) типа a -> b на a -> Writer b и получить новую категорию, в которой такие функции являются новыми морфизмами между a и b. Вернёмся к понятиям теории категорий. функцию типа a -> Writer a: Осталось только определить тождественный морфизм, т.е.

writerId :: a -> Writer a
writerId x = Writer (x, "")

В этой категории объектами являются те же типы, но морфизмом между типами a и b являются функции типа не a -> b, а a -> m b, т.е. Таким образом, мы получили новую категорию, основанную на Hask. Такие функции мы будем называть обогащёнными (embellished). возвращаемый тип "завёрнут" в какой-то другой фиксированный конструктор типа m. Композиция морфизмов и тождественный морфизм зависят от m, реализация для Writer — лишь частный случай.

Построим категорию K, состоящую из тех же объектов, что и категория C, т.е. Обобщим сказанное выше для любой категории C и эндофунктора m. Морфизм a -> b в категории K соответствует морфизму a -> m b в исходной категории C: HomK(a, b) = HomC(a, m b). ObK = ObC. Для типов и функций это будет означать, что функции, работающие с типами в категории K — обогащённые функции в категории C.

Тогда полученная категория называется категорией Клейсли, а функтор m — монадой. Для того, чтобы получить настоящую категорию с такими морфизмами, необходимо определить ассоциативную композицию морфизмов и тождественный морфизм для каждого объекта таким образом, чтобы соблюдались аксиомы теории категорий. На Haskell это определение выглядит так (везде далее используются типы из категории Hask):

class Monad m where -- композиция морфизмов категории Клейсли (>=>) :: (a -> m b) -> (b -> m c) -> (a -> m c) -- тождественный морфизм return :: a -> m a

Побочные эффекты, работа с состоянием, исключения — всё это лишь частные случаи, они не определяют, что такое монады, но являются хорошими примерами их использования. Тип оператора >=>, который иногда называют "fish", показывает суть монад: это способ композиции обогащённых функций. Writer — тоже монада, определённая нами функция compose — это композиция морфизмов >=>, а функция writerId — тождественный морфизм return.

Результатом композиции двух обогащённых функций должна быть тоже функция, поэтому в реализации используем лямбда-выражение. Начнём реализовывать оператор >=> в общем виде. Аргумент этого выражения имеет тип a, и у нас есть функция f, которую к нему можно применить, а дальше работать с результатом её вычисления во вспомогательной функции, которую назовём bind:

f >=> g = \a -> let mb = f a in (bind mb g) where bind :: m b -> (b -> m c) -> m c

Тип результата у неё совпадает с типом результата >=>. Функция bind получает значение типа b "в контейнере" m и функцию, которая принимает на вход аргумент типа b и возвращает m c. Эту функцию необходимо реализовать для каждой монады, чтобы описать способ композиции обогащённых функций. Мы получили следующую сигнатуру типов: m b -> (b -> m c) -> m c. Мы подошли к "классическому" определению монад в Haskell в виде класса типов с методами >>=, или bind, и return:

class Monad m where (>>=) :: m a -> (a -> m b) -> m b return :: a -> m a

Вспомним, что изначально мы работаем с эндофунктором m, поэтому можем воспользоваться функцией fmap, которая в данном случае будет типа (a -> m b) -> m a -> m (m b). Теперь попробуем продолжить реализацию в общем виде, для чего каким-то образом нужно применить функцию типа b -> m c к значению типа b, но у нас есть только значение типа m b. Выразим это преобразование как функцию join: Для завершения реализации >>= необходимо преобразовать значение типа m (m b) к m b, "схлопнув" контейнеры, но это уже невозможно сделать в общем виде.

ma >>= g = join (fmap g ma) where join :: m (m a) -> m a

Например, для типа Writer реализация будет следующей:

join :: Writer (Writer a) -> Writer a
join (Writer ((Writer (x, s2)), s1)) = Writer (x, s1 ++ s2)

Мы пришли к третьему определению класса Monad:

class Functor m => Monad m where join :: m (m a) -> m a return :: a -> m a

Это ограничение не было нужно для предыдущих определений, поскольку функция fmap реализуется через >>=: Здесь присутствует явное требование на то, чтобы m был функтором.

fmap :: (a -> b) -> m a -> m b
fmap f ma = ma >>= (\a -> return (f a))

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

Недетерминированные вычисления

таких, у которых может быть несколько возможных результатов) реализуется с помощью списков. Абстракция недетерминированных вычислений (т.е.

Достаточно опытному программисту реализация может быть понятна из одной этой сигнатуры: Композиция обогащённых функций должна иметь тип (a -> [b]) -> (b -> [c]) -> (a -> [c]).

(>=>) :: (a -> [b]) -> (b -> [c]) -> (a -> [c])
f >=> g = \x -> concat (map g (f x))

Получив значение типа a, единственное, что можно с ним сделать — это применить функцию f и получить список [b]. Типы практически не оставляют возможности сделать неверный шаг. Чтобы получить нужный результат, конкатенируем их. Далее всё, что мы умеем делать со значениями типа b — применить функцию g к каждому из них в списке и получить в результате список списков: map g (f x) :: [[c]].

Тогда оператор >>= можно записать так:

(>>=) :: [a] -> (a -> [b]) -> [b]
xs >>= f = concat (map f xs)

Здесь реализация снова выводится из типа: Осталось реализовать функцию return :: a -> [a].

return :: a -> [a]
return x = [x]

Резюмируем эти реализации в классическом определении класса Monad:

instance Monad [] where xs >>= f = concat (map f xs) return x = [x]

Хорошим примером, когда это действительно так, является реализация искусственного интеллекта для игр. Конечно, список как результат функции не обязательно обозначает недетерминированность вычислений. Список может представлять возможные результаты хода игрока, ответных ходов может быть тоже несколько — всё время приходится работать со списками, списками списков и т.д.

Исключения

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

При штатной работе функции будут возвращать значение в конструкторе Just, при возникновении ошибки — значение Nothing. Для этого подойдёт, к примеру, уже рассмотренный функтор Maybe. Композиция таких обогащённых функций должна работать таким образом, чтобы каждая следующая функция не вызывалась, если ошибка уже произошла в предыдущем вызове:

(>=>) :: (a -> Maybe b) -> (b -> Maybe c) -> (a -> Maybe c)
f >=> g = \x -> case f x of Just y -> g y Nothing -> Nothing

Определение методов класса Monad для Maybe:

instance Monad Maybe where (Just x) >>= f = f x Nothing >>= f = Nothing return x = Just x

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

data Either a b = Left a | Right b

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

type WithException a = Either String a

Композиция функций описывается аналогично случаю с использованием Maybe:

(>=>) :: (a -> WithException b) -> (b -> WithException c) -> (a -> WithException c)
f >=> g = \x -> case f x of Right y -> g y err -> err

Определение экземпляра класса Monad уже не должно вызывать трудностей:

instance Monad WithException where (Right x) >>= f = f x err >>= f = err return x = Right x

Состояния

Модифицируем тип функции a -> b так, чтобы получить обогащённую функцию, работающую с состоянием. Пример с логгером, с которого мы начинали, реализует работу с write-only состоянием, но хотелось бы использовать состояние и для чтения. Добавим в тип функции один аргумент, обозначающий текущее состояние, а также изменим тип возвращаемого значения (теперь это пара, состоящая из самого значения и изменённого состояния):

a -> s -> (b, s)

Объявим синоним типа для работы с состоянием:

newtype State s a = State (s -> (a, s))

Нам понадобится вспомогательная функция runState: Фиксируем тип состояния s и покажем, что State s является функтором.

runState :: State s a -> s -> (a, s)
runState (State f) s = f s

Реализация класса Functor:

instance Functor (State s) where fmap f state = State st' where st' prevState = let (a, newState) = runState state prevState in (f a, newState)

Попробуем превратить его в монаду, реализовав их композицию: Таким образом, обогащённые функции из a в b, в которых ведётся работа с состоянием, имеют тип a -> State s b, причём State s — функтор.

(>=>) :: (a -> State s b) -> (b -> State s c) -> (a -> State s c)
f >=> g = \x -> State (\s -> let (y, s') = runState (f x) s in runState (g y) s')

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

instance Monad (State s) where stateA >>= f = State (\s -> let (a, s') = runState stateA s in runState (f a) s') return a = State (\s -> (a, s))

Можно сказать, что это морфизм из Unit в s в категории Клейсли, поэтому функция должна иметь тип Unit -> State s s: Функция для чтения состояния должна всегда возвращать текущее состояния, ей не нужны аргументы.

get :: Unit -> State s s
get _ = State (\s -> (s, s))

Здесь он добавлен для того, чтобы показать эту операцию с точки зрения теории категорий. Конечно, в реализации Unit можно опустить.

Нам важен только побочный эффект, но не возвращаемое значение, поэтому соответствующий морфизм идёт в обратную сторону, из s в Unit, а функция имеет тип s -> State s Unit: Запись состояния, наоборот, принимает новое значение состояния и записывает его.

put :: s -> State s Unit
put s = State (\_ -> ((), s))

В ней предполагается, что "окружающий мир" реализован в виде некоторого типа RealWorld, о котором неизвестно никаких подробностей. Реализация работы с состоянием вышла чуть более сложной, чем предыдущие примеры, но на её основе можно создать формальную модель для работы с вводом/выводом. Эту абстрактную концепцию можно реализовать с помощью состояния: При общении с внешним миром программа получает на вход объект типа RealWorld и производит какие-то действия, в результате которых получает нужный ей результат и изменяет внешний мир (например, выводит строку на экран или читает символ из потока ввода).

type IO a = State RealWorld a

Такой упрощённый взгляд на этот тип как на состояние для работы с внешним миром может помочь понять, почему это так. Тип IO — один из первых, о котором узнаёт начинающий пользователь Haskell, и наверняка сразу встречает пугающее слово "монада". Кончено, это описание очень поверхностно, но полноценный рассказ о том, как на самом деле реализован ввод-вывод, зависит от компилятора и выходит далеко за рамки статьи.

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть