haskell - 什么是自由单子？

Question

我已经看到Free Monad这个词时不时出现了一段时间，但每个 人似乎只是在使用/讨论它们而没有解释它们是什么。那么：什么是自由单子？（我想说我熟悉 monad 和 Haskell 基础知识，但对范畴论只有非常粗略的了解。）

Answer 1

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

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

Answer 2

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)

Answer 3

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

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

给定函子F : D -> C, 和G : C -> D, 与 ,左邻接F -| G，或右邻接，只要 a, b:同构于，其中箭头来自适当的类别。FGGFF a -> ba -> G b

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

自由的 Monoid

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

取一个由一些载体集合定义的幺半群，T一个将一对元素混合在一起的二元函数f :: T → T → T，和一个unit :: T，这样你就有一个结合律和一个恒等律：f(unit,x) = x = f(x,unit)。

您可以U从幺半群（其中箭头是幺半群同态，即它们确保它们映射unit到unit另一个幺半群，并且您可以在映射到另一个幺半群之前或之后组合而不改变含义）到类别的集合（其中箭头只是功能箭头）“忘记”操作 和unit，而只是为您提供载体集合。

然后，您可以定义一个函子F，从集合类别回到与该函子相伴的幺半群类别。该函子是将一个集合映射a到幺半群[a]、 whereunit = []和的函子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 来证明一个幺半群同态 from[a] → b可以用函数 from 精确描述a → b。

在 Haskell 中，我们称其存在于Set（呃，Hask我们假装是 Set 的 Haskell 类型的类别）中的一侧，只是foldMap，当特化 fromData.Foldable到 Lists 时，它具有 type Monoid m => (a → m) → [a] → m。

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

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

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

自由单子

那么什么是Free Monad呢？

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

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

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

F 至少与Free我free在 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

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

Answer 4

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

---

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

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

这可以使用 Free Monad（数据结构）来完成，它以这样的方式包装 Functor（类型），因此join与其说是归约，不如说是这些 functor 的堆叠。

现在可以将真实的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)

Answer 5

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。自由单子的基本函子是语法树每一步的形状。

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

Answer 6

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

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

与明显的fmap。然后Free F a是树的类型，其叶子具有类型，a其节点用One、Two和标记。 -nodes 有一个子节点，-nodes 有两个子节点，-nodes 有三个子节点，并且还标有.Two'ThreeOneTwoTwo'ThreeInt

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

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

Answer 7

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

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

函子详解

有些东西是类型级别的形容词，这意味着它们接受一个类型名词，比如“整数”，然后给你一个不同的类型名词，比如“整数列表”或“带有整数的字符串对”，甚至是“用整数制作字符串的函数”。整数。” 为了表示任意形容词，让我使用替代词“蓝色”。

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

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

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

单子

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

1. 普遍适用，给定任何X，我可以构造一个蓝色X，
2. 可以重复而不会改变太多意思。所以blue -blue X在某种意义上与蓝色X相同。

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

第一个例子是“一个可以为空的__”。因此，如果我给你一个可为空的可为空的 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。自由蓝色自由蓝色X是蓝色^m blue ⁿ X，它只是蓝色^{m + n} X。它实现了“折叠”，因此根本不实现折叠，内部蓝调是任意嵌套的。

这也意味着您可以将您选择的 monad 推迟到以后的日期，稍后您可以定义一个函数，将蓝色-blue X减少为蓝色X并将所有这些折叠为蓝色^0,1 X，然后从X到蓝色X始终为您提供蓝色¹ X。