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<$>fmapf。所以我们所做的是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 回答