什么是自由单子？

这是一个更简单的答案：Monad 是在 monadic 上下文被 join :: m (m a) -> m a 折叠时“计算”的东西（回想一下，>>= 可以定义为 x >>= y = join (fmap y x)）。这就是 Monads 通过连续的计算链携带上下文的方式：因为在系列中的每一点，来自前一个调用的上下文与下一个调用折叠。

一个自由的 monad 满足所有的 Monad 定律，但不做任何折叠（即计算）。它只是建立了一系列嵌套的上下文。创建这种自由单子值的用户负责对这些嵌套上下文执行某些操作，以便可以将此类组合的含义推迟到创建单子值之后。

---

Edward Kmett 的回答显然很棒。但是，它有点技术性。这是一个可能更容易理解的解释。

自由单子只是将函子变成单子的一般方法。也就是说，给定任何函子 f Free f 是一个单子。这不会很有用，除非你得到一对功能

liftFree :: Functor f => f a -> Free f a
foldFree :: Functor f => (f r -> r) -> Free f r -> 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]

好吧，给定任何类型 t 我们知道 [t] 是一个幺半群

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

所以列表是集合上的“自由幺半群”（或在 Haskell 类型中）。

好的，所以免费的单子是相同的想法。我们取一个函子，并返回一个单子。事实上，由于 monad 可以被看作是内函子范畴中的 monoid，所以列表的定义

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)

---

免费的 foo 恰好是满足所有“foo”法则的最简单的东西。也就是说，它完全满足成为 foo 所必需的法律，仅此而已。

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

给定函子 F : D -> C 和 G : C -> D，我们说 F -| G，F 左邻接 G，或者 G 右邻接 F，只要 forall a, b: F a -> b 是同构的到 a -> G b，其中箭头来自相应的类别。

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

自由的 Monoid

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

以一个由某个载体集 T 定义的幺半群、一个将一对元素混合在一起的二元函数 f :: T → T → T 和一个 unit :: T，这样你就有一个结合律和一个恒等律：{4 }。

您可以从幺半群的类别中创建一个函子 U（其中箭头是幺半群同态，也就是说，它们确保它们将 unit 映射到另一个幺半群上的 unit，并且您可以在映射到其他幺半群而不改变含义）到集合的类别（其中箭头只是函数箭头），它“忘记”了操作和unit，只给你载体集合。

然后，您可以定义一个函子 F，从集合类别回到与该函子相伴的幺半群类别。该函子是将集合 a 映射到幺半群 [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 是自由的，我们需要证明它与 U 是一个遗忘函子，也就是说，正如我们上面提到的，我们需要证明

F a → b 与 a → U b 同构

现在，请记住 F 的目标在幺半群的类别 Mon 中，其中箭头是幺半群同态，所以我们需要 a 来证明来自 [a] → b 的幺半群同态可以由来自 a → b 的函数精确描述.

在 Haskell 中，我们称这部分存在于 Set（呃，Hask，我们假装为 Set 的 Haskell 类型的类别），只是 foldMap，当从 Data.Foldable 专门化为 Lists 时，它具有类型Monoid m => (a → m) → [a] → m。

这是一个附加的后果。值得注意的是，如果你忘记了然后用 free 建立，然后又忘记了，就像你忘记了一次一样，我们可以用它来建立 monadic join。由于 UFUF ~ U(FUF) ~ UF，我们可以通过定义我们的附加的同构，将恒等幺半群同态从 [a] 传递到 [a]，得到来自 [a] → [a] 的列表同构是一个函数a -> [a] 类型的，这只是列表的返回。

您可以通过以下术语描述列表来更直接地组合所有这些：

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

自由单子

那么什么是自由单子呢？

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

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

知道某物是自由单子 Free f，告诉您从 Free f -> m 给出单子同态与从 f -> m 给出自然变换（函子同态）是同一件事（同构）。记住 F a -> b 必须与 a -> U b 同构，F 才能与 U 相邻。U 在这里将单子映射到函子。

F 至少与我在 hackage 的 free 包中使用的 Free 类型同构。

我们也可以更紧密地类比上面的自由列表代码，通过定义

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

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

Cofree Comonads

假设它存在，我们可以通过查看一个健忘函子的右伴随物来构造类似的东西。 cofree 函子与遗忘函子简单地/右伴随/，并且通过对称性，知道某物是 cofree 共单子与知道从 w -> Cofree f 给出共单子同态与从 {2 给出自然变换是一样的}。

---

Free Monad（数据结构）之于 Monad（类）就像 List（数据结构）之于 Monoid（类）：这是一个简单的实现，您可以在之后决定如何组合内容。

您可能知道 Monad 是什么，并且每个 Monad 都需要 fmap + join + return 或 bind + return 的特定（遵守 Monad 法则）实现。

让我们假设您有一个 Functor（fmap 的实现），但其余部分取决于运行时所做的值和选择，这意味着您希望能够使用 Monad 属性但希望选择 Monad 函数然后。

这可以使用 Free Monad（数据结构）来完成，它以这样的方式包装 Functor（类型），以便 join 是这些仿函数的堆叠而不是归约。

您要使用的实际 return 和 join 现在可以作为归约函数 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。一个自由的 monad 存储一个仿函数列表而不是一个值列表。从技术上讲，您可以使用不同的数据类型实现自由 monad，但任何实现都应该与上述实现同构。

每当您需要抽象语法树时，您都可以使用免费的 monad。自由单子的基本函子是语法树每一步的形状。

My post，有人已经链接了，给出了几个如何使用免费 monad 构建抽象语法树的示例

---

我认为一个简单的具体例子会有所帮助。假设我们有一个函子

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-节点有一个子节点，Two- 和 Two'- 节点有两个子节点，Three-节点有三个并且还用 Int 标记。

Free F 是一个单子。 return 将 x 映射到只是具有值 x 的叶子的树。 t >>= f 查看每一片叶子并用树木代替它们。当叶子的值为 y 时，它将用树 f y 替换该叶子。

图表使这一点更清楚，但我没有轻松绘制图表的设施！

---

试图在此处的超简单答案和完整答案之间提供“桥梁”答案。

所以“自由单子”从任何“函子”中构建了一个“单子”，所以让我们按顺序来看看。

函子详解

有些东西是类型级别的形容词，这意味着它们采用诸如“整数”之类的类型名词并给您返回不同的类型名词，例如“整数列表”或“带有整数的字符串对”，甚至是“用整数创建字符串的函数”整数。”为了表示任意形容词，让我使用替代词“蓝色”。

但随后我们注意到其中一些形容词在它们修饰的名词中是输入式或输出式的模式。例如，“用 __ 制作字符串的函数”是输入式的，“将字符串变成 __ 的函数”是输出式的。这里的规则涉及我有一个函数 X → Y，一些形容词“蓝色”是输出的，或者一个函子，如果我可以使用这样的函数将蓝色 X 转换为蓝色 Y。想想“消防软管喷洒 Xs”和然后你拧上这个 X → Y 函数，现在你的消防水带喷 Ys。或者如果它是相反的，它是输入或逆变的，真空吸尘器吸着 Ys，当我把它拧上时，我得到一个吸尘器吸着 Xs。有些东西既不是输出也不是输入。事实证明两者都是幻影：它们与它们所描述的名词完全无关，因为您可以定义一个函数“coerce”，它接受一个蓝色 X 并生成一个蓝色 Y，但 * 不知道X 或 Y 类型的详细信息”，甚至不需要它们之间的函数。

所以“__ 的列表”是输出的，你可以将 X → Y 映射到 X 的列表上以获得 Y 的列表。类似地，“一对字符串和一个__”是输出的。同时，“从 __ 到自身的函数”既不是输出也不是输入，而“一个字符串和一个正好为零的 __s 列表”可能是“幻像”情况。

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

单子

一个 monad 是一个函子，它同时是

普遍适用，给定任何 X，我可以构造一个蓝色 X，可以重复而不会改变太多含义。所以从某种意义上说，蓝蓝 X 与蓝 X 是一样的。

所以这意味着有一个规范函数将任何蓝蓝 __ 折叠成一个蓝色 __。 （而且我们当然会添加法律以使一切正常：如果其中一层蓝色来自通用应用程序，那么我们只想删除该通用应用程序；此外，如果我们将蓝-蓝-蓝 X 扁平化为blue X，无论我们先折叠前两个蓝色还是先折叠后两个蓝色，都应该没有区别。）

第一个例子是“一个可以为空的__”。因此，如果我给你一个可为空的可为空的 int，从某种意义上说，我给你的不仅仅是一个可为空的 int。或者“一个整数列表的列表”，如果要点只是包含 0 个或多个整数，那么“一个整数列表”就可以正常工作，正确的折叠是将所有列表连接到一个超级列表中。

Monads 在 Haskell 中变得很大，因为 Haskell 需要一种在现实世界中做事的方法，而不会违反它的数学纯世界，那里什么都没有发生。解决方案是添加一种淡化的元编程形式，我们在其中引入了“产生__的程序”的形容词。那么如何获取当前日期呢？好吧，Haskell 不能在没有 unsafePerformIO 的情况下直接执行此操作，但它可以让您描述和编写生成当前日期的程序。在这个愿景中，您应该描述一个不产生任何内容的程序，称为“Main.main”，并且编译器应该接受您的描述并将该程序作为二进制可执行文件交给您，以便您随时运行。

无论如何，“一个产生一个产生一个 int 的程序的程序”并没有比“一个产生一个 int 的程序”买多少，所以这结果是一个 monad。

免费单子

与函子不同，单子不是唯一的单子。给定函子不仅有一个 monad 实例。例如“一对 int 和一个 __”，你用这个 int 做什么？你可以加它，你可以乘它。如果将其设为可为空的 int，则可以保留最小的非空值或最大的非空值，或者最左边的非空值或最右边的非空值。

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

它是通用的，因为 blue⁰ X 只是一个 X。而一个 free blue free blue X 是一个 bluem bluen X，它只是一个 bluem+n X。它实现了“collapse”，因此根本不实现 collapse，在内部，blues 是任意嵌套。

这也意味着您可以将您选择的 monad 推迟到以后的日期，稍后您可以定义一个函数，将蓝蓝 X 简化为蓝色 X 并将所有这些折叠为 blue0,1 X，然后从 X 中提取另一个函数to blue X 始终为您提供 blue1 X。

---