自由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行时遇到了很多麻烦,特别是在描述自由monad是什么的情况下.有些人可以描述一下这是如何工作的以及为什么它会成为Free f a一个免费的monad？

Answer 1

在这一点上,你只是制作Free一个仿函数而不是一个monad.当然,要成为一个monad,它也必须是一个仿函数!

我认为如果我们重命名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- 一个仿函数 - 重复应用了很多次.此类型的值类似于: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在go fmap本身时 - 重要的区别在于第一层fmap适用于单层f并且go递归地适用于整个 Free f a结构.

我希望这可以解决一些问题.

Answer 2

要告诉你实话,我通常只是觉得它更容易不阅读代码在这些简单的功能,而是阅读类型,然后写函数自己.把它想象成一个谜题.你正试图构建这个:

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是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 as []和Freeas (:).从类型的定义中你应该看到:Pure是基本情况,并且Free是递归的情况.什么fmap情况下做的是"推"的映射功能,这种结构的底部,到了那里的Pure生活.