Складные, моноидные и монады

Ответ 1

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 категорий (монады) и т.д. В принципе, каждый раз, когда у вас есть ассоциативная двоичная операция и идентификация для нее.

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

Это endofunctor, то есть он имеет тип * -> * в категории Hask типов Haskell.

Теперь, чтобы идти дальше, вы должны знать немного теории категорий, которую я попытаюсь объяснить здесь: учитывая два функтора F и G, существует естественное преобразование от F до G, если там существует функция α такая, что каждый F a может быть отображен на 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 был моноидом (no pure без mempty (без учета undefined)).

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

Ответ 2

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

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

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

A Haskell Functor является функтором из категории Hask (категория с функциями Haskell как стрелки) для себя. В категориях теории терминов мы говорим, что (специализированный) fmap является стрелочным отображением этого функтора, поскольку он является частью функтора, который принимает стрелки к стрелкам. (Для полноты: функтор состоит из сопоставления стрелок и сопоставления объектов. В этом случае объекты являются типами Haskell, поэтому сопоставление объектов принимает типы для типов - точнее, отображение объекта a 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 s. В таких случаях мы заменим id и (.) соответствующим тождеством и композицией, fmap соответствующим отображением стрелок и в одном случае = подходящим равенством стрелок.

(= < <)

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

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

Теперь ваш вопрос о перевернутом bind:

(=<<) :: 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, в отличие от правильной математической записи), Точнее, мы будем считать, что любые две функции, которые могут быть взаимно конвертированы с использованием любой композиции Identity и Compose как равные стрелки (или, другими словами, мы не будем различать 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 (см. ответ danidiaz - он использует traverse_, но поскольку прикладной функтор Const m результат по существу тот же):

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

Благодаря изоморфизму const/getConst это, очевидно, эквивалентно:

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 и, транзитивно, на (=<<).

Приложение

Вот приблизительный эскиз вывода результата 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

Ответ 3

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

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

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

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

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, чтобы избавиться от нового типа.