Ответ 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 )