Free Monad(数据结构)之于Monad(类)，就像List(数据结构)之于Monoid(类):这是一个简单的实现，在那里你可以决定如何组合内容。

---

你可能知道什么是Monad，每个Monad都需要fmap + join + return或bind + return的特定实现(遵循Monad法)。

让我们假设你有一个Functor (fmap的实现)，但其余的取决于值和在运行时所做的选择，这意味着你想要能够使用Monad属性，但想要选择Monad功能之后。

这可以使用Free Monad(数据结构)来完成，它以这样一种方式包装Functor(类型)，以便连接是这些Functor的堆叠而不是约简。

你想要使用的实际返回和连接，现在可以作为约约函数foldFree的参数:

foldFree :: Functor f => (a -> b) -> (f b -> b) -> Free f a -> b
foldFree return join :: Monad m => Free m a -> m a

为了解释这些类型，我们可以将Functor f替换为Monad m，将b替换为(m.a):

foldFree :: Monad m => (a -> (m a)) -> (m (m a) -> (m a)) -> Free m a -> (m a)

Haskell free monad是一个函子列表。比较:

data List a   = Nil    | Cons  a (List a  )

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

Pure类似于Nil, Free类似于Cons。Free单子存储的是一个函子列表，而不是一个值列表。从技术上讲，你可以使用不同的数据类型来实现免费的单子，但是任何实现都应该与上面的同构。

只要需要抽象语法树，就可以使用免费的单子。自由单子的基函子是语法树中每一步的形状。

我的文章(已经有人链接了)给出了几个如何用免费单子构建抽象语法树的例子

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

自由单子只是将函子转换为单子的一种通用方法。也就是说，给定任意函子，自由f是一个单子。这不是很有用，除非你得到一对函数

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

第一个选项让你“进入”你的单子，第二个选项让你“退出”单子。

更一般地说，如果X是一个Y，加上一些额外的P，那么“自由X”是一种从Y到X而不获得任何额外东西的方法。

例如:一个单类(X)是一个带有额外结构(P)的集合(Y)，它基本上说它有一个操作(你可以想到加法)和一些恒等式(比如零)。

So

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

现在，我们都知道列表

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

对于任意类型的t，我们知道[t]是一个一元曲面

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

因此列表是集合(或Haskell类型)之上的“自由单类”。

免费单子也是一样的。我们取一个函子，然后返回一个单子。事实上，由于单子可以被视为内函子范畴内的单类，一个列表的定义

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

看起来很像免费单子的定义

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

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

--it needs to be a functor
instance Functor f => Functor (Free f) where
  fmap f (Pure a) = Pure (f a)
  fmap f (Roll x) = Roll (fmap (fmap f) x)

--this is the same thing as (++) basically
concatFree :: Functor f => Free f (Free f a) -> Free f a
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 f x)  --this is the standard concatMap definition of bind

现在，我们有了两个操作

-- this is essentially the same as \x -> [x]
liftFree :: Functor f => f a -> Free f a
liftFree x = Roll (fmap Pure x)

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

这里有一个更简单的答案:一个Monad是一些“计算”时，Monad上下文被join:: m (m A) -> m A(回忆>>=可以定义为x >>= y = join (fmap y x))。这就是Monads如何通过一个连续的计算链携带上下文:因为在系列中的每个点上，来自前一个调用的上下文与下一个调用一起折叠。

一个自由的单子满足所有的单子定律，但不做任何折叠(即计算)。它只是建立了一系列嵌套的上下文。创建这样一个自由单体值的用户负责对这些嵌套上下文做一些事情，这样组合的含义可以延迟到单体值创建之后。

我想举个简单具体的例子会有帮助。假设我们有一个函子

data F a = One a | Two a a | Two' a a | Three Int a a a

用明显的fmap。Free F a是这样一种树，其叶子类型为a，其节点标记为One, Two, Two'和Three。one -nodes有一个子节点，Two-和Two'-nodes有两个子节点，three -nodes有三个子节点，也被标记为Int。

Free F是一个单子。Return将x映射到树，它是一个值为x的叶子。t >>= f查看每个叶子并将它们替换为树。当叶结点的值为y时，它就会用树f y替换叶结点。

一个图表使这更清楚，但我没有工具来轻松地画一个!

free foo恰好是满足所有“foo”定律的最简单的东西。也就是说，它完全满足成为一种食物所必需的法则，没有别的。

健忘函子是从一个类别到另一个类别时“忘记”结构的一部分。

给定函子F: D -> C和G: C -> D，我们说F -| G, F左伴随于G，或者G右伴随于F当对于所有a, b: F a -> b同构于a -> G b，其中箭头来自适当的范畴。

形式上，一个自由函子与一个健忘函子左伴随。

自由单体

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

取一个由载波集T定义的单类，一个将一对元素混叠在一起的二进制函数f:: T→T→T，和一个单位::T，这样你就有一个结合律和一个恒等律:f(单位，x) = x = f(x，单位)。

你可以从monooid的范畴(其中箭头是monooid同态，也就是说，它们确保它们映射到另一个monooid上的单位到单位，并且你可以在映射到另一个monooid之前或之后组合而不改变意义)到集合的范畴(其中箭头只是函数箭头)，它“忘记”操作和单位，只给你载波集。

然后，你可以定义一个函子F从集合的范畴回到与这个函子左伴随的monooid范畴。该函子是将集合a映射到单类[a]的函子，其中unit = []， mappend =(++)。

回顾一下我们的例子，在pseudo-Haskell中:

U : Mon → Set -- is our forgetful functor
U (a,mappend,mempty) = a

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

然后为了证明F是自由的，我们需要证明它是左伴随U的，一个健忘的函子，也就是说，正如我们上面提到的，我们需要证明这一点

F a→b与a→U b同构

现在，记住F的目标是在monooid的范畴Mon中，其中箭头是monooid同态，所以我们需要a来证明一个来自[a]→b的monooid同态可以被来自a→b的函数精确描述。

在Haskell中，我们称这个位于Set中的一侧(呃，hasask，我们假装为Set的Haskell类型类别)为foldMap，当从Data特殊化时。可折叠列表类型为Monoid m => (a→m)→[a]→m。

这是一个附加词的后果。值得注意的是，如果你忘记了，然后用free来构建，然后再次忘记，就像你忘记了一次一样，我们可以用这个来构建单体连接。因为UFUF ~ U(FUF) ~ UF，我们可以通过定义我们的附加的同构传递从[a]到[a]的单位单同构，得到从[a]→[a]的列表同构是类型为a -> [a]的函数，这只是返回列表。

你可以更直接地用这些术语来描述一个列表:

newtype List a = List (forall b. Monoid b => (a -> b) -> b)

免费单子

那么什么是免费单子?

我们做和之前一样的事情，我们从一个忘记的函子U开始从单子的范畴开始，单子的箭头是单子同态，到内函子范畴开始，箭头是自然变换，我们寻找一个左伴随的函子。

那么，这与通常使用的自由单子的概念有什么关系呢?

知道某个东西是一个自由单子，自由f，告诉你从自由f -> m得到一个单子同态，和从f -> m得到一个自然变换(一个函子同态)是一样的(同构)记住f a -> b必须同构到a -> U b才能使f左伴U U这里把单子映射到函子。

F至少与我在hackage上的免费包中使用的免费类型同构。

我们还可以将其构造为与上面用于空闲列表的代码更紧密的类比，通过定义

class Algebra f x where
  phi :: f x -> x

newtype Free f a = Free (forall x. Algebra f x => (a -> x) -> x)

Cofree Comonads

我们可以构造类似的东西，通过观察一个健忘函子的右伴随，假设它存在。一个协自由函子就是一个易忘记的函子的右伴随，根据对称性，知道某物是一个协自由共通子就等于知道从w -> cofree f得到一个共通同态就等于从w -> f得到一个自然变换。