撰写Monads v.Applicative Functors

Question

该Typeclassopedia的单子变形金刚节介绍:

不幸的是,monad并不像applicative functor那样组合(如果你不需要Monad提供的全部功能,那么使用Applicative的另一个原因)

纵观类型的>>=和<*>,上面的语句,我不清楚.

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

请解释一下"monad不像compative functors那样好."

我看了这个答案,但你能举个例子来帮我理解吗？

Answer 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)

关于为什么monad不能和应用程序组合的简短答案是,虽然第一个实例可以写入,但第二个实例不能.我们试试吧!

我们可以热身了 Functor

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

在这里,我们看到,由于我们fmap的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)

在这一点上可能很清楚问题是什么 - 我们只知道如何连接s或s的连续层,但在这里我们看到它们交织在一起.你会发现我们需要一个交换属性fg

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

那么这一切的结果是什么？Applicatives ^ 始终 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 )