Складной, Моноид и Монада

Monoid и Monad

Вау, на самом деле это один из редких случаев, когда мы можем использовать цитату:

Монада - это просто моноид в категории эндофункторов, [...]

Начнем с моноида. Моноид в категории Set наборов - это набор элементов m с пустым элементом mempty и ассоциативной функцией mappend для объединения элементов таким образом, что

mempty `mappend` x == x -- for any x
x `mappend` mempty == x -- for any x
-- and
a `mappend` (b `mappend` c) == (a `mappend` b) `mappend` c -- for all a, b, c

Обратите внимание, что моноид не ограничен наборами, также существуют моноиды в категории Cat категорий (монад) и так далее. Практически всегда, когда у вас есть ассоциативная бинарная операция и идентификатор для нее.

Теперь монада, представляющая собой «моноид в категории эндофункторов», обладает следующими свойствами:

Это эндофунктор, то есть он имеет тип * -> * в Категории Hask типов Haskell.

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

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

Возвращаясь к монаде, мы теперь видим, что «моноид в категории эндофункторов» должен подвергаться двум естественным преобразованиям. Назовем нашу монаду эндофунктором M:

Естественное преобразование тождественного (эндо) функтора в монаду:

η :: 1 -> M -- this is return

И естественное преобразование из состава двух монад и создания третьей:

μ :: M × M -> M

Поскольку × - это композиция функторов, мы можем (грубо говоря) также написать:

μ :: m a × m a -> m a
μ :: (m × m) a -> m a
μ :: m (m a) -> m a -- join in Haskell

Удовлетворяя этим законам:

μ . M μ == μ . μ M
μ . M η == μ . η M

Итак, монада - это частный случай моноида в категории эндофункторов. Вы не можете написать экземпляр моноида для монады в обычном Haskell, поскольку понятие композиции в Haskell слишком слабое (я думаю; это потому, что функции ограничены Hask, а оно слабее, чем Cat). См. это для получения дополнительной информации.

А что насчет Foldable?

Теперь что касается Foldable: существуют определения fold, использующие настраиваемую двоичную функцию для объединения элементов. Теперь вы, конечно, можете предоставить любую функцию для комбинирования элементов или использовать существующую концепцию комбинирования элементов, моноид. Опять же, обратите внимание, что этот моноид ограничен установленным моноидом, не каторическим определением моноида.

Поскольку mappend моноида ассоциативно, foldl и foldr дают одинаковый результат, поэтому сворачивание моноидов может быть уменьшено до fold :: Monoid m, Foldable t => t m -> m. Это очевидная связь между моноидом и складным.

@danidiaz уже указывал на связь между Applicative, Monoid и Foldable, используя Const функтор Const a b = Const a, аппликативный экземпляр которого требует, чтобы первый параметр Const был моноидом (нет pure без mempty (без учета undefined)).

На мой взгляд, сравнение монады и foldable - это немного натянуто, поскольку монада более мощная, чем foldable в том смысле, что foldable может только накапливать значения списка в соответствии с функцией сопоставления, но привязка монады может структурно изменять контекст (a -> m b) .

Резюме: (>>=) и traverse выглядят одинаково, потому что они оба являются стрелочными отображениями функторов, а foldMap (почти) является специализированным traverse.

Прежде чем мы начнем, нужно пояснить одну терминологию. Рассмотрим fmap:

fmap :: Functor f => (a -> b) -> (f a -> f b)

Haskell Functor - это функтор из категории Hask (категория с функциями Haskell в виде стрелок) к самому себе. В терминах теории категорий мы говорим, что (специализированный) fmap - это отображение стрелок этого функтора, поскольку это часть функтора, которая переводит стрелки на стрелки. (Для полноты: функтор состоит из сопоставления стрелок и сопоставления объектов. В этом случае объекты являются типами Haskell, и поэтому сопоставление объектов принимает типы в типы - более конкретно, отображение объекта Functor является его конструктором типа.)

Мы также хотим иметь в виду законы категорий и функторов:

-- Category laws for Hask:
f . id = id
id . f = f
h . (g . f) = (h . g) . f

-- Functor laws for a Haskell Functor:
fmap id = id
fmap (g . f) = fmap g . fmap f

Далее мы будем работать с категориями, отличными от Hask, и функторами, которые не являются Functor. В таких случаях мы заменим id и (.) соответствующими идентификаторами и составом, fmap соответствующим отображением стрелок и, в одном случае, = соответствующим равенством стрелок.

(=<<)

Начнем с более знакомой части ответа: для данной монады m функции a -> m b (также известные как стрелки Клейсли) образуют категорию (категория Клейсли m) с return как идентичностью и (<=<) как составом. В данном случае законы трех категорий - это просто законы монад:

f <=< return = return
return <=< f = f
h <=<  (g <=<  f) = (h <=<  g) <=<  f

Теперь вы спросили о перевернутой привязке:

(=<<) :: Monad m => (a -> m b) -> (m a -> m b)

Оказывается, (=<<) - это стрелочное отображение функтора из категории Клейсли m в Hask. Законы функторов, применяемые к (=<<), составляют два закона монад:

return =<< x = x -- right unit
(g <=< f) =<< x = g =<< (f =<< x) -- associativity 

траверс

Далее нам нужно объехать Traversable (набросок доказательства результатов в этом разделе приведен в конце ответа). Во-первых, отметим, что a -> f b функции для всех аппликативных функторов f, взятых одновременно (в отличие от одного в каждый момент времени, как при указании категории Клейсли), образуют категорию с Identity в качестве идентификатора и Compose . fmap g . f в качестве сочинение. Чтобы это сработало, мы также должны принять более мягкое равенство стрелок, которое игнорирует шаблон Identity и Compose (что необходимо только потому, что я пишу это на псевдо-Haskell, а не в правильной математической нотации). Точнее, мы будем считать, что любые две функции, которые могут быть взаимно преобразованы с использованием любой композиции _ 34_ и _ 35_ изоморфизмов как равные стрелки (или, другими словами, мы не будем различать a и Identity a, а также f (g a) и Compose f g a).

Давайте назовем эту категорию «проходимой категорией» (так как я не могу сейчас придумать лучшего названия). В конкретных терминах Haskell стрелка в этой категории - это функция, которая добавляет дополнительный уровень Applicative контекста «под» любыми предыдущими существующими уровнями. Теперь рассмотрим traverse:

traverse :: (Traversable t, Applicative f) => (a -> f b) -> (t a -> f (t b))

При выборе проходимого контейнера traverse - это стрелка, отображающая функтор из «проходимой категории» в себя. Законы функторов для него равносильны законам проходимости.

Короче говоря, и (=<<), и traverse являются аналогами fmap для функторов, включающих категории, отличные от Hask, и поэтому неудивительно, что их типы немного похожи друг на друга.

foldMap

Нам еще предстоит объяснить, какое отношение все это имеет к foldMap. Ответ состоит в том, что foldMap можно восстановить из traverse (см. ответ Данидиаза - он использует traverse_, но как аппликативный функтор Const m результат по сути тот же):

-- cf. Data.Traversable
foldMapDefault :: (Traversable t, Monoid m) => (a -> m) -> (t a -> m)
foldMapDefault f = getConst . traverse (Const . f)

Благодаря изоморфизму _53 _ / _ 54_ это явно эквивалентно:

foldMapDefault' :: (Traversable t, Monoid m)
                => (a -> Const m b) -> (t a -> Const m (t b))
foldMapDefault' f = traverse f

Это просто traverse специализировано для Monoid m => Const m аппликативных функторов. Хотя Traversable не Foldable и foldMapDefault не является foldMap, это дает достойное оправдание того, почему тип foldMap похож на тип traverse и, транзитивно, тип (=<<).

В качестве последнего наблюдения отметим, что стрелки «проходимой категории» с аппликативным функтором Const m для некоторых Monoid m не образуют подкатегорию, поскольку идентичность отсутствует, если Identity не входит в число возможных вариантов аппликативного функтор. Это, вероятно, означает, что с точки зрения этого ответа о foldMap больше нечего сказать. Единственный выбор аппликативного функтора, который дает подкатегорию, - это Identity, что совсем не удивительно, учитывая, что обход с Identity составляет fmap в контейнере.

Приложение

Вот приблизительный набросок получения результата traverse, взятый из моих заметок, сделанных несколько месяцев назад, с минимальным редактированием. ~ означает «равный (некоторому релевантному) изоморфизму».

-- Identity and composition for the "traversable category".
idT = Identity
g .*. f = Compose . fmap g . f

-- Category laws: right identity
f .*. idT ~ f
f .*. idT
Compose . fmap f . idT
Compose . fmap f . Identity
Compose . Identity . f
f -- using getIdentity . getCompose 

-- Category laws: left identity
idT .*. f ~ f
idT .*. f
Compose . fmap Identity . f
f -- using fmap getIdentity . getCompose

-- Category laws: associativity
h .*. (g .*. f) ~ (h .*. g) .*. f
h .*. (g .*. f) -- LHS
h .*. (Compose . fmap g . f)
Compose . fmap h . (Compose . fmap g . f)
Compose . Compose . fmap (fmap h) . fmap g . f
(h .*. g) .*. f -- RHS
(Compose . fmap h . g) .*. f
Compose . fmap (Compose . fmap h . g) . f
Compose . fmap (Compose . fmap h) . fmap g . f
Compose . fmap Compose . fmap (fmap h) . fmap g . f
-- using Compose . Compose . fmap getCompose . getCompose
Compose . Compose . fmap (fmap h) . fmap g . f -- RHS ~ LHS

-- Functor laws for traverse: identity
traverse idT ~ idT
traverse Identity ~ Identity -- i.e. the identity law of Traversable

-- Functor laws for traverse: composition
traverse (g .*. f) ~ traverse g .*. traverse f
traverse (Compose . fmap g . f) ~ Compose . fmap (traverse g) . traverse f 
-- i.e. the composition law of Traversable

Когда контейнер Foldable, существует связь между foldMap и Applicative (который является суперклассом Monad).

Foldable имеет функцию traverse_ с подписью:

traverse_ :: Applicative f => (a -> f b) -> t a -> f ()

Один из возможных Applicative - это Constant. Чтобы быть аппликативным, он требует, чтобы параметр "аккумулятор" был Monoid:

newtype Constant a b = Constant { getConstant :: a } -- no b value at the term level!

Monoid a => Applicative (Constant a)

Например:

gchi> Constant (Sum 1) <*> Constant (Sum 2) :: Constant (Sum Int) whatever
Constant (Sum {getSum = 3})

Мы можем определить foldMap в терминах traverse_ и Constant следующим образом:

foldMap' :: (Monoid m, Foldable t) => (a -> m) -> t a -> m
foldMap' f = getConstant . traverse_ (Constant . f)

Мы используем traverse_, чтобы пройти через контейнер, накапливая значения с помощью Constant, а затем мы используем getConstant, чтобы избавиться от newtype.