11

Control.Monad.Free实现一个免费的单子为：

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行时遇到了很多麻烦，尤其是在描述什么是 free monad的上下文中。有人可以描述一下它是如何工作的以及为什么它会成为Free f a一个免费的单子吗？

4

3 回答 3

14

在这一点上，你只是在制作Free一个函子而不是一个单子。当然，要成为 monad，它也必须是 functor！

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

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

现在让我们看看我们正在构建的结构。对于这种Pure情况，我们只有一个 type 的值a。对于这种Wrap情况，我们在函子中包装了另一个值。 Free f af

让我们暂时忽略构造函数。也就是说，如果我们将Wrap (f (Pure a))其视为f a. 这意味着我们正在构建的结构只是f——一个函子——重复应用了几次。这种类型的值看起来像：f (f (f (f (f a)))). 为了使其更具体，让fbe[]得到：[[[[[a]]]]]. Wrap通过重复使用构造函数，我们可以拥有任意多的 this 级别；当我们使用Pure.

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

因此，我们所做的就是获取该Pure值并反复对其应用函子。

给定这种重复应用函子的结构，我们如何在它上面映射一个函数？对于这种Pure情况——在我们把它包装f进去之前——这很简单：我们只是应用这个函数。但是，如果我们已经将我们的值f至少包装了一次，我们必须映射到外层，然后递归地映射到所有内层。换句话说，我们必须Free在函子上映射 monad 上的映射f。

这正是第二种情况go正在做的事情。go本身只是fmap为了Free f a。<$>是fmap为f。所以我们所做的是fmap goover f，这使得整个事情都是递归的。

由于这个映射函数是递归的，它可以处理任意数量的级别。所以我们可以将一个函数映射到[[a]]or[[[[a]]]]或其他上。这就是为什么我们需要fmap go当 gofmap本身时 - 重要的区别在于第一个fmap适用于单层并且f递归go适用于整个 Free f a构造。

我希望这能澄清一点。

于 2013-04-13T17:36:44.770 回答
7

说实话，我通常只是发现不阅读这些简单函数中的代码，而是阅读类型然后自己编写函数更容易。把它想象成一个谜题。您正在尝试构建这个：

mapFree :: Functor f => (a -> b) -> Free f a -> Free f b

那么我们该怎么做呢？好吧，让我们Pure先来看看构造函数：

mapFree f (Pure a) = ...
-- I like to write comments like these while using Haskell, then usually delete 
-- them by the end:
--
-- f :: a -> b
-- a :: a

有了其中的两种类型的注释，并且知道 的类型Pure，您应该立即看到解决方案：

mapFree f (Pure a) = Pure (f a)

现在是第二种情况：

mapFree f (Free fa) = ...
-- f  :: a -> b
-- fa :: Functor f => f (Free f a)

好吧，既然f是 a Functor，我们实际上可以mapFree用来应用于mapFree f的内部组件f (Free f a)。所以我们得到：

mapFree f (Free fa) = Free (fmap (mapFree f) fa)

现在，使用这个定义作为Functor f => Functor (Free f)实例，我们得到：

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

通过一些工作，您可以验证我们刚刚得出的定义与您正在困惑的定义相同。（正如其他人所提到的，(<$>)（在 中定义Control.Applicative）只是 . 的同义词fmap。）您可能仍然不理解它，但您设法编写了它，对于这些抽象类型来说，这通常已经足够好了。

不过，就理解它而言，对我有帮助的是：将Freemonad 视为一种类似列表的结构，带有Pureas[]和Freeas (:)。从类型的定义你应该看到：Pure是基本情况，Free是递归情况。实例正在做的fmap是将映射的函数“推”到这个结构的底部，到它所在的位置Pure。

于 2013-04-13T21:45:54.290 回答
1

由于我自己很困惑，所以我回答了一个问题......这是否是一个正确的替代（依赖于 Tikhon 的 Wrap 澄清）？ 

...
fmap g = go where
  go (Pure a)  = Pure (g a)
  go (Wrap fa) = Wrap (go <$> fa)

Substituting "fmap g" for "go", and "fmap" for "<$>" (since "<$>" is infix, 
 we flip "go" and "<$>"):

fmap g (Pure a)  = Pure (g a)
fmap g (Wrap fa) = Wrap (fmap (fmap g) fa)

Substituting "f (Free f a)" for "fa" in the last line (from the first data 
 declaration):

fmap g (Wrap fa) = Wrap ( fmap (fmap g) (f (Free f a)) )

                 = Wrap ( f ( fmap g (Free f a) ) )

                 = wrap ( f (Pure (g a) ) ) --if Free f a is Pure
                 or
                 = Wrap ( f ( fmap g (Wrap fa') ) ) --if Free f a is Wrap

The last line includes the recursion "fmap g (Wrap fa')", which would continue 
 unless Pure is encountered.
于 2013-04-13T19:56:52.430 回答