什么是免费单子？

我已经看到“ Free Monad”这个术语偶尔会出现一段时间，但是似乎每个人似乎都会使用/讨论它们，而没有给出它们的解释。那么，什么是免费的单子呢？（我会说我熟悉单子和Haskell的基础知识，但对类别理论只有非常粗略的了解。）

爱德华·科梅特的答案显然很棒。但是，这有点技术性。这是一个可能更容易理解的解释。

自由单体只是将函数转化为单子的一般方法。也就是说，给定任何函数f Free f是一个monad。除非你有一对function，否则这不会很有用

 liftFree :: Functor f => fa -> Free fa foldFree :: Functor f => (fr -> r) -> Free fr -> r

第一个让你“进入”你的monad，第二个给你一个“走出去”的方法。

更一般地说，如果X是一个带有一些额外东西P的Y，那么一个“自由X”就是从Y到X得到一些额外的东西的一种方式。

例子：幺半群（X）是一个具有额外结构（P）的集合（Y），基本上说它有一个操作（你可以想到加法）和一些身份（如零）。

所以

 class Monoid m where mempty :: m mappend :: m -> m -> m

现在，我们都知道名单

 data [a] = [] | a : [a]

好吧，给定任何types我们知道[t]是一个monoid

 instance Monoid [t] where mempty = [] mappend = (++)

所以列表是“自由幺半群”的集合（或Haskelltypes）。

好吧，免费的monads是一样的想法。我们采取一个函数，并给一个monad。事实上，monad可以被看作是单一类的内在函子，就是列表的定义

 data [a] = [] | a : [a]

看起来很像自由monads的定义

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

而Monad实例与列表的Monoid实例有相似之处

 --it needs to be a functor instance Functor f => Functor (Free f) where fmap f (Pure a) = Pure (fa) fmap f (Roll x) = Roll (fmap (fmap f) x) --this is the same thing as (++) basically concatFree :: Functor f => Free f (Free fa) -> Free fa concatFree (Pure x) = x concatFree (Roll y) = Roll (fmap concatFree y) instance Functor f => Monad (Free f) where return = Pure -- just like [] x >>= f = concatFree (fmap fx) --this is the standard concatMap definition of bind

现在，我们得到了我们的两个操作

 -- this is essentially the same as \x -> [x] liftFree :: Functor f => fa -> Free fa liftFree x = Roll (fmap Pure x) -- this is essentially the same as folding a list foldFree :: Functor f => (fr -> r) -> Free fr -> r foldFree _ (Pure a) = a foldFree f (Roll x) = f (fmap (foldFree f) x)

这里有一个更简单的答案：Monad是当单元上下文被join :: m (ma) -> ma （回忆>>=可以被定义为(join .) . flip fmap ）时“计算”的东西。这就是Monad如何通过顺序的计算链来进行上下文的操作：因为在系列中的每一个点上，来自前一个调用的上下文都与下一个调用崩溃了。

一个免费的monad满足所有的Monad定律，但是不会做任何崩溃（即计算）。它只是build立一个嵌套的上下文系列。创build这种自由一元值的用户负责对这些嵌套的上下文进行操作，以便这种构成的含义可以推迟到一元值创build之后。

免费的foo恰好是满足所有'foo'定律的最简单的东西。也就是说，它完全符合必要的法律，而不是任何额外的东西。

一个健忘的函数是一个“忘记”结构的一部分，因为它从一个类别到另一个。

给定函子F : D -> C ， G : C -> D ，我们说F -| G F -| G ， F是与G相邻的，或者G是与F只要a，b： F a -> b同构于a -> G b ，其中箭头来自适当的类别。

forms上，一个免费的函数是一个健忘的函数。

自由Monoid

让我们从一个更简单的例子开始，这个自由的monoid。

以一个载体组T定义的monoid为一个二元函数，将一对元素混合在一起f :: T → T → T和一个unit :: T ，这样就可以得到一个关联律和一个同一性定律： f(unit,x) = x = f(x,unit) 。

你可以从monoids类别（其中箭头是幺半群同态，也就是说，他们确保他们在另一个monoid上映射unit到unit ，并且可以在映射到另一个monoid之前或之后构成一个函子U而不改变意义）到“忘记”操作和unit的集合（箭头只是function箭头）的类别，并且只给你载体集合。

然后，你可以定义一个仿函数F从这个类的集合返回到这个仿函数的左边。该函子是将一个集映射到monoid [a]的函数，其中unit = []和mappend = (++) 。

所以要回顾一下我们的例子，在伪Haskell中：

 U : Mon → Set -- is our forgetful functor U (a,mappend,mempty) = a F : Set → Mon -- is our free functor F a = ([a],(++),[])

那么为了显示F是自由的，需要certificate它是留给U一个健忘的函子，就像我们上面提到的那样，我们需要certificate

F a → b同构于a → U b

现在，记住F的目标是monique类Mon ，其中箭头是幺半群同态，所以我们需要一个certificate从[a] → b的幺半群同态可以由a → b的函数精确描述。

在Haskell中，我们称这个生存在Set （er， Hask ，我们假设的Haskelltypes为Set）的foldMap ，只是当从Data.Foldable到Lists专门化的types为Monoid m => (a → m) → [a] → m 。

由此产生的后果是后果。值得注意的是，如果你忘记了那么免费build立，那么再次忘记它，就像你忘记了一次，我们可以用它来build立一元连接。由于UFUF U(FUF) ，我们可以通过定义我们的连接的同构从[a]到[a]传递同态幺半群同态，从[a] → [a]得到列表同构是函数typesa -> [a] ，这只是返回列表。