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)

试图在这里的超简单答案和完整答案之间提供一个“桥梁”答案。

所以“free monads”从任何“functor”中构建一个“monad”，让我们按顺序来看。

函子的细节

有些东西是类型级形容词，这意味着它们接受一个类型名词，比如“整数”，然后返回一个不同的类型名词，比如“整数列表”或“带整数的字符串对”，甚至是“用整数组成字符串的函数”。为了表示任意一个形容词，让我用“blue”来代替。

But then we notice a pattern that some of these adjectives are input-ish or output-ish in the noun they modify. For example “functions making strings out of __” is input-ish, “functions turning strings into __” is output-ish. The rule here involves me having a function X → Y, some adjective “blue” is outputtish, or a functor, if I can use such a function to transform a blue X into a blue Y. Think of “a firehose spraying Xs” and then you screw on this X → Y function and now your firehose sprays Ys. Or it is inputtish or a contravariant if it is the opposite, a vacuum cleaner sucking up Ys and when I screw this on I get a vacuum sucking up Xs. Some things are neither outputtish nor inputtish. Things that are both it turns out are phantom: they have absolutely nothing to do with the nouns that they describe, in the sense that you can define a function “coerce” which takes a blue X and makes a blue Y, but *without knowing the details of the types X or Y,” not even requiring a function between them.

所以" lists of __ "是输出的，你可以将X→Y映射到X的列表上得到Y的列表。类似地，" a pair of a string and a __ "是输出的。同时，“从__到自身的函数”既不是输出的也不是输入的”，而“一个字符串和一个恰好0个__s的列表”可能是“幻影”情况。

这就是编程中函数子的全部内容，它们只是可映射的东西。如果某物是函子，那么它是唯一的函子，最多只有一种方法将一个函数映射到一个数据结构上。

单体

单子是一个函子，它同时是两者

普遍适用，给定任意X，我可以构造一个蓝色的X， 可以在不改变意思的情况下重复。所以蓝色的X在某种程度上和蓝色的X是一样的。

这意味着有一个规范函数将任何蓝色的__折叠为蓝色的__。(当然，我们会添加一些定律让一切变得理智:如果其中一层蓝色来自通用应用，那么我们就想擦掉这个通用应用;此外，如果我们将一个蓝色-蓝色-蓝色X压扁为一个蓝色X，那么我们是先折叠前两个蓝色还是先折叠后两个蓝色应该没有区别。)

第一个例子是“可空__”。所以如果我给你一个可为空的int，在某种意义上，我给你的只是一个可为空的int。或者“整型数组列表的列表”，如果目的是要有0个或多个整型数组，那么“整型数组列表”就可以了，正确的折叠是将所有列表连接到一个超级列表中。

Monads became big in Haskell because Haskell needed an approach to do things in the real world without violating its mathematically pure world where nothing really happens. The solution was to add is sort of watered down form of metaprogramming where we introduce an adjective of “a program which produces a __.” So how do I fetch the current date? Well, Haskell can't do it directly without unsafePerformIO but it will let you describe and compose the program which produces the current date. In this vision, you are supposed to describe a program which produces nothing called “Main.main,” and the compiler is supposed to take your description and hand you this program as a binary executable for you to run whenever you want.

不管怎样，"一个程序生成一个产生int型的程序"并不比"一个程序生成int型"更有价值所以这是一个单子。

的自由单体

与函子不同，单子不是唯一的单子。对于一个给定的函子，不只有一个单子实例。例如“一对int和__”，你用这个int做什么?你可以相加，也可以相乘。如果你让它成为一个可空的int，你可以保留最小的非空值或者最大的非空值，或者最左边的非空值或者最右边的非空值。

给定函子的自由单子是“最无聊”的结构，它只是“一个自由的蓝色X对于任何n = 0,1,2，…都是一个蓝色X”。

它是通用的，因为一个蓝色⁰X只是一个X，而一个自由的蓝色X是一个蓝色X，它只是一个蓝色+n X。它实现了“崩溃”，因此根本不实现崩溃，在内部蓝色是任意嵌套的。

这也意味着你可以将你选择的单子推迟到以后的日期，以后你可以定义一个函数，它将蓝-蓝X缩减为蓝X，并将所有这些缩减为blue0,1 X，然后从X到蓝X的另一个函数将始终提供blue1 X。

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)

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

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得到一个自然变换。