Композиция Monads v. Аппликативные функторы

Typeclassopedia Раздел Monad Transformers объясняет:

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

Глядя на типы >>= и <*>, приведенное выше утверждение мне не ясно.

(<*>) :: Applicative f => f (a -> b) -> f a -> f b
(>>=) :: Monad m => m a -> (a -> m b) -> m b

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

Я прочитал этот ответ, но не могли бы вы привести пример, чтобы помочь мне понять?

Ответ 1

Существует несколько понятий, по которым типы * -> * могут "составляться". Более важным является то, что вы можете составить их "последовательно".

newtype Compose f g x = Compose { getCompose :: f (g x) }

Здесь вы можете видеть, что Compose имеет вид (* -> *) -> (* -> *) -> (* -> *), как и любой хороший состав функторов.

Итак, вопрос: существуют ли законопослушные экземпляры, подобные следующим?

instance (Applicative f, Applicative g) => Applicative (Compose f g)
instance (Monad f,       Monad g)       => Monad       (Compose f g)

И короткий ответ о том, почему монады не составляют, а также аппликаторы, заключается в том, что, хотя первый экземпляр можно записать, второй не может. Попробуйте!

Мы можем прогреться с Functor

instance (Functor f,     Functor g)     => Functor     (Compose f g) where
  fmap f (Compose fgx) = Compose (fmap (fmap f) fgx)

Здесь мы видим, что, поскольку мы можем fmap an fmap -ed f, мы можем передать его через слои f и g, как нам нужно. Аналогичную игру играют с pure

instance (Applicative f, Applicative g) => Applicative (Compose f g) where
  pure a = Compose (pure (pure a))

а (<*>) кажется сложным, если вы внимательно посмотрите на тот же трюк, который мы использовали с fmap и pure.

  Compose fgf <*> Compose fgx = Compose ((<*>) <$> fgf <*> fgx)

Во всех случаях мы можем подталкивать операторы, которым нам нужно "через" слои f и g точно так, как мы могли бы надеяться.

Но теперь взглянем на Monad. Вместо того, чтобы пытаться определить Monad через (>>=), я собираюсь вместо этого работать через join. Для реализации Monad нам нужно реализовать

join :: Compose f g (Compose f g x) -> Compose f g x

используя

join_f :: f (f x) -> f x  -- and
join_g :: g (g x) -> g x

или, если мы отменим шум newtype, нам нужно

join :: f (g (f (g x))) -> f (g x)

В этот момент может быть ясно, в чем проблема: мы знаем, как присоединяться к последовательным слоям f или g s, но здесь мы видим, что они переплетаются. Вы обнаружите, что нам нужно свойство коммутации

class Commute f g where
  commute :: g (f x) -> f (g x)

и теперь мы можем реализовать

instance (Monad f, Monad g, Commute f g) => Monad (Compose f g)

с (агностиком newtype) join, определенным как

join :: f (g (f (g x))) -> f (g x)
join fgfgx = fgx where
  ffggx :: f (f (g (g x)))
  ffggx = fmap commute fgfgx
  fggx :: f (g (g x))
  fggx = join_f ffggx
  fgx :: f (g x)
  fgx = fmap join_g fggx

Итак, что это за результат? Applicative всегда Compose, но Monad Compose только тогда, когда их слои Commute.

Когда мы можем Commute слои? Вот несколько примеров

instance Commute ((->) x) ((->) y) where
  commute = flip

instance Commute ((,) x) ((,) y) where
  commute (y, (x, a)) = (x, (y, a))

instance Commute ((->) x) ((,) y) where
  commute (y, xa) = \x -> (y, xa x)

-- instance Commute ((,) x) ((->) y) does not exist; try to write yourself!
--
-- OR:
-- It turns out that you need to somehow "travel back in time" to make it
-- work...
-- 
-- instance Commute ((,) x) ((->) y) where
--   commute yxa = ( ..., \y -> let (x, a) = yxa y in a )