免费monad的应用实例

Question

当我试图找到一个可以逐步执行/允许线程处理的haskell monad时，我发现了这个免费的monad。

data Free f a = Return a | Roll (f (Free f a))

用它的单一实例

instance (Functor f) => Monad (Free f) where
  return = Return
  Return x    >>= f = f x
  Roll action >>= f = Roll $ fmap (>>= f) action

及其函子实例

instance (Functor f) => Functor (Free f) where
  fmap f (Return x) = Return (f x)
  fmap f (Roll   x) = Roll $ fmap (fmap f) x

我知道每个monad都是一个具有pure = return和(<*>) = ap的应用函子。对我来说，应用函子在概念上比单子更难。为了更好地理解应用函子，我喜欢在不诉诸ap的情况下拥有应用实例。

<*>的第一行很简单：

instance (Applicative f) => Applicative (Free f) where
  pure = Return
  Return f <*> x = fmap f x -- follows immediately from pure f <*> x = f <$> x
--Roll   f <*> x = Roll $ (fmap ((fmap f) <*>)) x -- wrong, does not type-check

如何用Roll f <*> x和fmap及<*>定义基本术语

Answer 1

这样行吗？

instance (Functor f) => Applicative (Free f) where
  pure = Return
  Return f  <*> as  = fmap f as
  Roll faf  <*> as  = Roll (fmap (<*> as) faf)

我们的计划是只在产生函数的树的叶子上进行操作，因此对于Return，我们将函数应用于参数操作产生的所有参数值。对于Roll，我们只对所有的子动作做我们打算做的对整个动作的操作。

关键的是，我们到达Return时所做的事情在我们开始之前就已经设置好了。我们不会根据我们在树上的位置而改变我们的计划。这就是Applicative的特点:计算的结构是固定的，所以值依赖于值，而操作不依赖于值。