haskell - 自由单子(monad)的推导

Question

Control.Monad.Free实现一个免费的单子(monad)为:

data Free f a = Pure a | Free (f (Free f a))

instance Functor f => Functor (Free f) where
  fmap f = go where
    go (Pure a)  = Pure (f a)
    go (Free fa) = Free (go <$> fa)

我在理解第二个 go 时遇到了很多麻烦行，尤其是在描述 what a free monad is 的上下文中.有人可以描述一下它是如何工作的以及它为什么会产生 Free f a一个免费的单子(monad)？

Answer 1

此时，您只是在制作 Free仿函数而不是单子(monad)。当然，要成为 monad，它也必须是 functor!

我认为如果我们重命名 Free 会更容易考虑。构造函数以避免混淆:

data Free f a = Pure a | Wrap (f (Free f a))

现在让我们看看我们正在构建的结构。对于 Pure在这种情况下，我们只有 a 类型的值.对于 Wrap情况下，我们还有一个 Free f a包裹在 f 中的值仿函数。

让我们暂时忽略构造函数。也就是说，如果我们有 Wrap (f (Pure a))让我们把它想象成 f a .这意味着我们正在构建的结构只是 f --a functor--重复应用了几次。此类型的值类似于: f (f (f (f (f a)))) .为了更具体，让 f是 []获取: [[[[[a]]]]] .通过使用 Wrap，我们可以拥有任意多的级别。重复构造函数；当我们使用 Pure 时一切都结束了.

将构造函数放回， [[a]]看起来像: Wrap [Wrap [Pure a]] .

所以我们所做的就是使用 Pure值并反复对其应用仿函数。

给定这种重复应用仿函数的结构，我们如何在它上面映射一个函数？对于 Pure案例——在我们将其包裹在 f 中之前--这很简单:我们只是应用函数。但是如果我们已经将我们的值包裹在 f至少有一次，我们必须映射外层，然后递归地映射所有内层。换句话说，我们必须在 Free 上映射映射。仿函数上的 monad f .

这正是 go 的第二种情况。是在做。 go本身只是 fmap对于 Free f a . <$>是 fmap对于 f .所以我们要做的是 fmap go超过 f ，这使得整个事情递归。

由于这个映射函数是递归的，它可以处理任意数量的级别。所以我们可以在 [[a]] 上映射一个函数或 [[[[a]]]]管他呢。这就是为什么我们需要 fmap go什么时候去是 fmap本身——重要的区别是第一个 fmap适用于 f 的单层和 go递归地为整个 Free f a 工作 build 。

我希望这能澄清一点。