Аппликативы составляют, а монады - нет

110

Аппликативы составляют, а монады - нет.

Что означает приведенное выше утверждение? А когда одно предпочтительнее другого?

пропавший
источник
5
Откуда у вас это заявление? Может быть полезно увидеть некоторый контекст.
fuz
@FUZxxl: Я слышал это неоднократно от многих разных людей, в последнее время из debasishg в твиттере.
missingfaktor
3
@stephen Тетли: Обратите внимание , что многие из таких Applicativeлет, на самом деле целая семья из Monadх, а именно : по одному для каждой «формы» структуры возможной. ZipListне a Monad, а ZipLists фиксированной длины. Readerэто удобный частный (или общий?) случай, когда размер «структуры» фиксируется как мощность типа среды.
CA McCann,
3
@CAMcCann Все эти быстрые аппликативы (независимо от того, усекают ли они или дополняют) ограничиваются монадами, если вы исправляете форму способом, который сводится к Readerмонаде с точностью до изоморфизма. Как только вы исправляете форму контейнера, он эффективно кодирует функцию с позиций, как памятка. Питер Хэнкок называет такие функторы «наперианами», поскольку они подчиняются законам логарифмов.
Свинарник
4
@stephen tetley: другие примеры включают аппликатив константного моноида (который является композицией монад, но не монадой) и аппликатив единичной задержки (который лучше не допускает соединения).
Свинарник

Ответы:

115

Если сравнить типы

(<*>) :: Applicative a => a (s -> t) -> a s -> a t
(>>=) :: Monad m =>       m s -> (s -> m t) -> m t

мы понимаем, что разделяет эти два понятия. То, что (s -> m t)в типе (>>=)показывает, что значение в sможет определять поведение вычисления в m t. Монады допускают взаимодействие между слоями значений и вычислений. (<*>)Оператор не допускает таких помех: функция и аргумент вычисления не зависят от значений. Это действительно кусается. Сравнить

miffy :: Monad m => m Bool -> m x -> m x -> m x
miffy mb mt mf = do
  b <- mb
  if b then mt else mf

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

iffy :: Applicative a => a Bool -> a x -> a x -> a x
iffy ab at af = pure cond <*> ab <*> at <*> af where
  cond b t f = if b then t else f

который использует значение abдля выбора между значениями двух вычислений atи af, выполнив оба, возможно, к трагическим последствиям.

Монадическая версия в основном полагается на дополнительную (>>=)возможность выбора вычисления из значения, и это может быть важно. Однако поддержка этой силы затрудняет сочинение монад. Если мы попытаемся построить двойную привязку

(>>>>==) :: (Monad m, Monad n) => m (n s) -> (s -> m (n t)) -> m (n t)
mns >>>>== f = mns >>-{-m-} \ ns -> let nmnt = ns >>= (return . f) in ???

мы зашли так далеко, но теперь наши слои перемешаны. У нас есть n (m (n t)), поэтому нам нужно избавиться от внешнего n. Как говорит Александр С, мы можем это сделать, если у нас есть подходящий

swap :: n (m t) -> m (n t)

переставить nвнутрь и joinего на другое n.

Более слабое «двойное применение» гораздо легче определить

(<<**>>) :: (Applicative a, Applicative b) => a (b (s -> t)) -> a (b s) -> a (b t)
abf <<**>> abs = pure (<*>) <*> abf <*> abs

потому что нет интерференции между слоями.

Соответственно, хорошо понимать, когда вам действительно нужна дополнительная мощность Monads, а когда можно обойтись жесткой структурой вычислений, которая Applicativeподдерживает.

Заметьте, кстати, что, хотя составление монад сложно, это может быть больше, чем вам нужно. Тип m (n v)указывает вычисление с m-effects, затем вычисление с n-effects до v-value, где m-effects заканчиваются до начала n-effects (отсюда необходимость swap). Если вы просто хотите чередовать m-effects с n-effects, то композиция - это слишком много, чтобы просить!

свинарник
источник
3
В качестве сомнительного примера вы заявляете, что он «использует значение ab для выбора между значениями двух вычислений at и af, выполнив оба вычисления, возможно, с трагическим эффектом». Разве от этого вас не защищает ленивая природа Haskell? Если у меня есть list = (\ btf -> if b, то t else f): [], а затем выполните оператор: list <*> pure True <*> pure "hello" <*> pure (error "bad"). ... Я получаю "привет", а ошибки никогда не возникает. Этот код далеко не так безопасен и не контролируется, как монада, но сообщение, похоже, предполагает, что аппликативы вызывают строгую оценку. В целом отличный пост! Спасибо!
shj
7
Вы по-прежнему получаете эффекты обоих, но чистый (ошибка «плохо») не имеет их. Если, с другой стороны, вы попробуете iffy (pure True) (pure "hello") (error "bad"), вы получите ошибку, которую miffy избегает. Более того, если вы попробуете что-то вроде iffy (pure True) (pure 0) [1,2], вы получите [0,0] вместо [0]. У аппликаторов есть своего рода строгость в том, что они создают фиксированные последовательности вычислений, но значения, полученные в результате этих вычислений, по-прежнему лениво комбинируются, как вы заметили.
Свинарник 01
Верно ли, что для любой монады mи nвы всегда можете написать монады трансформатор mt, и работать в n (m t)использовании mt n t? Значит, вы всегда можете составлять монады, это просто сложнее, используя трансформаторы?
ron
4
Такие преобразователи часто существуют, но, насколько я знаю, нет канонического способа их создания. Часто есть настоящий выбор, как разрешить чередующиеся эффекты от разных монад, классическим примером являются исключения и состояния. Должно ли исключение изменить состояние отката или нет? У обоих вариантов есть свое место. Сказав это, есть «свободная монада», которая выражает «произвольное чередование». data Free f x = Ret x | Do (f (Free f x))Тогда data (:+:) f g x = Inl (f x) | Tnr (g x)и рассмотрим Free (m :+: n). Это задерживает выбор способа выполнения чередования.
pigworker
@pigworker По поводу ленивых / строгих дебатов. Я думаю, что с помощью аппликативов вы не можете контролировать эффект изнутри вычислений, но слой эффекта вполне может решить не оценивать более поздние значения. Для (прикладных) синтаксических анализаторов это означает, что если синтаксический анализатор выходит из строя раньше, последующие синтаксические анализаторы не оцениваются / не применяются к входным данным. Потому что Maybeэто означает, что раннее Nothingбудет подавлять оценку aболее позднего / последующего Just a. Это верно?
ziggystar
75

Аппликативы составляют, а монады - нет.

Монады действительно составляют, но результатом может быть не монада. Напротив, композиция из двух аппликативов обязательно является аппликативом. Я подозреваю, что намерение первоначального утверждения заключалось в том, что «аппликативность составляет, а монадность - нет». Перефразируя, « Applicativeзакрыто по составу и Monadне является».

Конал
источник
24
Кроме того, любые два аппликатива составляют полностью механически, тогда как монада, образованная композицией двух монад, специфична для этой композиции.
Apocalisp
12
Более того, монады складываются другими способами, продукт двух монад - это монада, и только их копроизведения нуждаются в каком-то распределительном законе.
Эдвард КМЕТТ
С, @Apocalisp, комментарием, это лучший и самый краткий ответ.
Paul Draper
39

Если у вас есть аппликативы A1и A2, тогда тип data A3 a = A3 (A1 (A2 a))также является аппликативным (вы можете написать такой экземпляр в общем виде).

С другой стороны, если у вас есть монады, M1и M2тогда тип data M3 a = M3 (M1 (M2 a))не обязательно является монадой (нет разумной универсальной реализации для композиции >>=или joinдля нее ).

Одним из примеров может быть типа [Int -> a](здесь мы составляем конструктор типа []с (->) Int, оба из которых являются монады). Вы легко можете написать

app :: [Int -> (a -> b)] -> [Int -> a] -> [Int -> b]
app f x = (<*>) <$> f <*> x

И это относится к любому аппликативу:

app :: (Applicative f, Applicative f1) => f (f1 (a -> b)) -> f (f1 a) -> f (f1 b)

Но толкового определения

join :: [Int -> [Int -> a]] -> [Int -> a]

Если вы не уверены в этом, рассмотрите это выражение:

join [\x -> replicate x (const ())]

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

Ротзор
источник
1
... так что избегайте монад, когда подойдет функция?
Эндрю Кук
2
@andrew, если вы имели в виду функтор, то да, функторы проще и должны использоваться, когда их достаточно. Учтите, что это не всегда. Например, IOбез a Monadбыло бы очень сложно программировать. :)
Rotsor
17

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

Составление монад, http://web.cecs.pdx.edu/~mpj/pubs/RR-1004.pdf

Landei
источник
4
Tl; dr для нетерпеливых читателей: вы можете составлять монады, если (е?) Вы можете обеспечить естественное преобразованиеswap : N M a -> M N a
Александр С.
@Alexandre C .: Просто «если», я подозреваю. Не все преобразователи монад описываются прямой композицией функторов. Например, ContT r m aнет ни m (Cont r a)или Cont r (m a), а StateT s m aпримерно так Reader s (m (Writer s a)).
CA McCann,
@CA McCann: Кажется, я не могу перейти от (монады M, монады N, монады MN, монады NM) к (существует своп: MN -> NM natural). Так что давайте пока придерживаемся «если» (возможно, ответ находится в газете, я должен признаться, что нашел его быстро)
Alexandre C.
1
@Alexandre C .: Просто указать, что композиции представляют собой монады, в любом случае может быть недостаточно - вам также нужен способ связать две части с целым. Существование swapподразумевает, что композиция позволяет им как-то «сотрудничать». Также обратите внимание, что sequenceэто частный случай "свопа" для некоторых монад. Так и есть на flipсамом деле.
CA McCann,
7
Для того, чтобы написать swap :: N (M x) -> M (N x)это выглядит для меня , как вы можете использовать returns(соответственно fmapPED) для вставки Mна передней панели и Nна спине, переходя от N (M x) -> M (N (M (N x))), а затем использовать joinкомпозит , чтобы получить ваши M (N x).
Свинарник
7

Достаточно решения l: MN -> NM по распределительному закону

гарантировать монадичность НМ. Для этого вам понадобится агрегат и мульт. я сосредоточусь на мульт (единица измерения - unit_N unitM)

NMNM - l -> NNMM - mult_N mult_M -> NM

Это не гарантирует, что MN является монадой.

Однако важное наблюдение вступает в игру, когда у вас есть решения по закону распределения.

l1 : ML -> LM
l2 : NL -> LN
l3 : NM -> MN

таким образом, LM, LN и MN - монады. Возникает вопрос, является ли LMN монадой (либо по

(MN) L -> L (MN) или через N (LM) -> (LM) N

У нас достаточно структуры, чтобы делать эти карты. Однако, как отмечает Юджиния Ченг , нам нужно гексагональное условие (которое представляет собой представление уравнения Янга-Бакстера), чтобы гарантировать монадичность любой конструкции. Фактически, с условием гексагональности две разные монады совпадают.

user278559
источник
9
Вероятно, это отличный ответ, но он пролетел над моей головой.
Дэн Бертон
1
Это потому, что, используя термин Applicative и тег haskell, это вопрос о haskell, но с ответом в другой нотации.
codehot