Разница между Монадой и Аппликатором в Хаскелле

Я просто прочитал следующее из typeclassopedia о различии между Monad и Applicative . Я могу понять, что в Applicative соглашении нет. Но следующее описание выглядит неопределенным для меня, и я не мог понять, что именно подразумевается под «результатом» монадического вычисления / действия. Итак, если я ставлю значение в Maybe , что делает монаду, то каков результат этого «вычисления»?

Давайте посмотрим подробнее на тип (>> =). Основная интуиция заключается в том, что он объединяет два вычисления в один более крупный расчет. Первый аргумент, ma, является первым вычислением. Однако было бы скучно, если бы второй аргумент был всего лишь mb; то было бы невозможно, чтобы вычисления могли взаимодействовать друг с другом (на самом деле, это именно та ситуация, которая характерна для аппликативной). Итак, второй аргумент для (>> =) имеет тип a -> mb: функция этого типа, полученная в результате первого вычисления, может произвести второе вычисление, которое будет выполняться. … Интуитивно, именно эта способность использовать вывод из предыдущих вычислений, чтобы решить, какие вычисления будут выполняться дальше, что делает Monad более мощным, чем Applicative. Структура Аппликативного вычисления фиксирована, тогда как структура вычисления Монады может изменяться на основе промежуточных результатов.

Есть ли конкретный пример, иллюстрирующий «способность использовать вывод из предыдущих вычислений, чтобы решить, какие вычисления будут выполняться дальше», чего нет в Applicative?

Мой любимый пример – «чисто аппликативный Либо». Мы начнем с анализа базового экземпляра Monad для Либо

 instance Monad (Either e) where return = Right Left e >>= _ = Left e Right a >>= f = fa 

Этот экземпляр имеет очень естественное короткое замыкание: мы исходим слева направо, и как только одно вычисление «терпит неудачу» Left то все остальное тоже. Существует также естественный Applicative пример, что любая Monad имеет

 instance Applicative (Either e) where pure = return (<*>) = ap 

где ap – не более чем последовательность слева направо перед return :

 ap :: Monad m => m (a -> b) -> ma -> mb ap mf ma = do f <- mf a <- ma return (fa) 

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

 (>>=) :: ma -> (a -> mb) -> mb 

Если мы думаем о ma как «прошлом» и mb как «будущем», то (>>=) создает будущее из прошлого, пока оно может запускать «шаговый» (a -> mb) . Этот «степпер» требует, чтобы ценность действительно существовала в будущем ... и это невозможно для Either . Поэтому (>>=) требует короткого замыкания.

Поэтому вместо этого мы будем применять Applicative экземпляр, который не может иметь соответствующую Monad .

 instance Monoid e => Applicative (Either e) where pure = Right 

Теперь выполнение (<*>) - это особая часть, которую следует тщательно рассмотреть. Он выполняет некоторое количество «короткого замыкания» в первых трех случаях, но делает что-то интересное в четвертом.

  Right f <*> Right a = Right (fa) -- neutral Left e <*> Right _ = Left e -- short-circuit Right _ <*> Left e = Left e -- short-circuit Left e1 <*> Left e2 = Left (e1 <> e2) -- combine! 

Заметим еще раз, что если мы считаем левый аргумент «прошлым» и правильным аргументом как «будущее», то (<*>) является особым по сравнению с (>>=) поскольку ему разрешено «открывать» будущее и прошлое параллельно, а не обязательно нуждаются в результатах от «прошлого», чтобы вычислить «будущее».

Это означает, что мы можем использовать нашу чисто Applicative Either для сбора ошибок, игнорируя Right s, если какие-либо Left существуют в цепочке

 > Right (+1) <*> Left [1] <*> Left [2] > Left [1,2] 

Итак, давайте перевернем эту интуицию на голове. Что мы не можем делать с чисто аппликативным? Ну, так как его работа зависит от изучения будущего до запуска прошлого, мы должны уметь определять структуру будущего, не завися от ценностей в прошлом. Другими словами, мы не можем писать

 ifA :: Applicative f => f Bool -> fa -> fa -> fa 

которая удовлетворяет следующим уравнениям

 ifA (pure True) te == t ifA (pure False) te == e 

в то время как мы можем написать ifM

 ifM :: Monad m => m Bool -> ma -> ma -> ma ifM mbool th el = do bool <- mbool if bool then th else el 

такой, что

 ifM (return True) te == t ifM (return False) te == e 

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

Just 1 описывает «вычисление», чей «результат» равен 1. Nothing описывает вычисление, которое не дает результатов.

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

Вот что это значит. В монадической цепи

 return 42 >>= (\x -> if x == 1 then return (x+1) else return (x-1) >>= (\y -> return (1/y) )) 

if выбирает, какие вычисления строить.

В случае соискателя в

 pure (1/) <*> ( pure (+(-1)) <*> pure 1 ) 

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

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

С помощью монад сами функции сами выстраивают вычисления по своему выбору.

Вот мой прием @J. Пример Абрахамсона относительно того, почему ifA не может использовать значение внутри, например (pure True) . По существу, все еще сводится к отсутствию функции join от Monad in Applicative , которая объединяет две разные точки зрения, приведенные в typeclassopedia, чтобы объяснить разницу между Monad и Applicative .

Таким образом, используя @J. Пример Абрахамсона чисто аппликативного Either :

 instance Monoid e => Applicative (Either e) where pure = Right Right f <*> Right a = Right (fa) -- neutral Left e <*> Right _ = Left e -- short-circuit Right _ <*> Left e = Left e -- short-circuit Left e1 <*> Left e2 = Left (e1 <> e2) -- combine! 

(который имеет аналогичный эффект короткого замыкания для Either Monad ), а функция ifA

 ifA :: Applicative f => f Bool -> fa -> fa -> fa 

Что, если мы попытаемся достичь упомянутых уравнений:

 ifA (pure True) te == t ifA (pure False) te == e 

?

Ну, как уже указывалось, в конечном итоге содержание (pure True) не может быть использовано более поздним вычислением. Но, с технической точки зрения, это неправильно. Мы можем использовать контент (pure True) так как Monad также является Functor с fmap . Мы можем сделать:

 ifA' bte = fmap b (\x -> if x then t else e) 

Проблема заключается в обратном типе ifA' , который является f (fa) . В Applicative нет способа свертывания двух вложенных Applicative S в один. Но эта коллапсирующая функция – это именно то, что происходит в Monad . Так,

 ifA = join . ifA' 

будет удовлетворять уравнениям для ifA , если мы сможем реализовать join соответствующим образом. Здесь отсутствует какая-то Applicative функция. Другими словами, мы можем каким-то образом использовать результат из предыдущего результата в Applicative . Но это в Applicative структуре будет включать увеличение типа возвращаемого значения к вложенному аппликативному значению, которое у нас нет для возврата к одноуровневому аппликативному значению. Это будет серьезной проблемой, потому что, например, мы не можем надлежащим образом составлять функции с использованием Applicative S. Использование join исправляет проблему, но сама вставка join способствует Applicative к Monad .

Ключ разницы можно наблюдать в типе ap vs type =<< .

 ap :: m (a->b) -> (m a->mb) =<< :: (a->mb) -> (m a->mb) 

В обоих случаях существует ma , но только во втором случае ma может решить, применяется ли функция (a->mb) . В свою очередь, функция (a->mb) может «решить», будет ли применена функция, связанная далее, - создавая такую mb , которая не «содержит» b (например, [] , Nothing или Left ).

В Applicative нет возможности для функций «внутри» m (a->b) делать такие «решения» - они всегда вызывают значение типа b .

 f 1 = Nothing -- here f "decides" to produce Nothing fx = Just x Just 1 >>= f >>= g -- g doesn't get applied, because f decided so. 

В Applicative это невозможно, поэтому не может показать пример. Ближайшим является:

 f 1 = 0 fx = x g <$> f <$> Just 1 -- oh well, this will produce Just 0, but can't stop g -- from getting applied 

Но следующее описание выглядит неопределенным для меня, и я не мог понять, что именно подразумевается под «результатом» монадического вычисления / действия.

Ну, эта неопределенность несколько преднамеренная, потому что то, что «результат» является монадическим вычислением, зависит от каждого типа. Лучший ответ немного тавтологичен: «результат» (или результат , поскольку может быть больше одного) – это любое значение (-ы) реализации экземпляра (>>=) :: Monad m => ma -> (a -> mb) -> mb вызывает аргумент функции с.

Итак, если я ставлю значение в Maybe , что делает монаду, то каков результат этого «вычисления»?

Maybe монада выглядит так:

 instance Monad Maybe where return = Just Nothing >>= _ = Nothing Just a >>= k = ka 

Единственное, что здесь квалифицируется как «результат», это a во втором уравнении для >>= , потому что это единственное, что когда-либо получает «питание» ко второму аргументу >>= .

Другие ответы ifM разницу ifA и ifM , поэтому я подумал, что выделил еще одну значительную разницу: составления аппликаций, монады – нет . С Monad s, если вы хотите сделать Monad который объединяет эффекты двух существующих, вы должны переписать один из них в качестве монадного трансформатора. Напротив, если у вас есть две Applicatives вы можете легко сделать более сложную из них, как показано ниже. (Код копируется из transformers .)

 -- | The composition of two functors. newtype Compose fga = Compose { getCompose :: f (ga) } -- | The composition of two functors is also a functor. instance (Functor f, Functor g) => Functor (Compose fg) where fmap f (Compose x) = Compose (fmap (fmap f) x) -- | The composition of two applicatives is also an applicative. instance (Applicative f, Applicative g) => Applicative (Compose fg) where pure x = Compose (pure (pure x)) Compose f <*> Compose x = Compose ((<*>) <$> f <*> x) -- | The product of two functors. data Product fga = Pair (fa) (ga) -- | The product of two functors is also a functor. instance (Functor f, Functor g) => Functor (Product fg) where fmap f (Pair xy) = Pair (fmap fx) (fmap fy) -- | The product of two applicatives is also an applicative. instance (Applicative f, Applicative g) => Applicative (Product fg) where pure x = Pair (pure x) (pure x) Pair fg <*> Pair xy = Pair (f <*> x) (g <*> y) -- | The sum of a functor @[email protected] with the 'Identity' functor data Lift fa = Pure a | Other (fa) -- | The sum of two functors is always a functor. instance (Functor f) => Functor (Lift f) where fmap f (Pure x) = Pure (fx) fmap f (Other y) = Other (fmap fy) -- | The sum of any applicative with 'Identity' is also an applicative instance (Applicative f) => Applicative (Lift f) where pure = Pure Pure f <*> Pure x = Pure (fx) Pure f <*> Other y = Other (f <$> y) Other f <*> Pure x = Other (($ x) <$> f) Other f <*> Other y = Other (f <*> y) 

Теперь, если добавить в Constant функтор / аппликативный:

 newtype Constant ab = Constant { getConstant :: a } instance Functor (Constant a) where fmap f (Constant x) = Constant x instance (Monoid a) => Applicative (Constant a) where pure _ = Constant mempty Constant x <*> Constant y = Constant (x `mappend` y) 

… мы можем собрать «аппликативный Either » из других ответов из Lift и Constant :

 type Error ea = Lift (Constant e) a 
Давайте будем гением компьютера.