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

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

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

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

The Free Monoid

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

以一个由载体集T定义的单类为例，它是一个将一对元素组合在一起的二进制函数f :: T → T → T和unit :: T，这样你就有了结合律和恒等律:f(unit,x) = x = f(x,unit)。

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

然后，你可以定义一个函子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的目标是在单类的Mon类别中，其中箭头是单类同态，所以我们需要a来证明来自[a] → b的单类同态可以被来自a → b的函数精确描述。

在Haskell中，我们将这个位于Set(呃，Hask，我们假定为Set的Haskell类型类别)中的一侧称为foldMap，当从Data.Foldable特殊化到Lists时，它的类型为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)

The Free Monad

那么免费的单子是什么?

我们做和之前一样的事情，我们从一个忘记的函子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)

< em > Cofree Comonads < / em >

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

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

自由单子只是将函子转换为单子的一种通用方法。也就是说，给定任何函子f 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)，它基本上说它有一个操作(你可以想到加法)和一些恒等式(比如零)。

所以

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)

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 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有三个子节点，并且标记为Free F a1。

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

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

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

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

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

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

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

函子的细节

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

但随后我们注意到一个规律，其中一些形容词在它们修饰的名词中是input-ish或output-ish。例如，“从__生成字符串的函数”是输入型，“将字符串转换为__的函数”是输出型。这里的规则涉及到我有一个函数X→Y，一些形容词“blue”是输出的，或者一个函子，如果我可以使用这样一个函数将一个蓝色的X转换为一个蓝色的Y。想象“一个消防水龙带喷Xs”，然后你拧上这个X→Y函数，现在你的消防水龙带喷Ys。或者它是inputtish或output-ish1，如果它是相反的，一个吸尘器吸Ys，当我拧上这个，我得到一个真空吸Xs。有些东西既不能输出也不能输入。output-ish4的东西实际上是output-ish5:它们与它们所描述的名词完全没有关系，在这种意义上，你可以定义一个函数“coerce”，它接受一个蓝色的X并生成一个蓝色的Y，但*不知道X或Y类型的细节，“甚至不需要在它们之间设置一个函数。”

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

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

单体

单孢体是一个函子，它同时是两个函子

1. 普遍适用，给定任意X，我可以构造一个蓝色的X，
2. 可以在不改变意思的情况下重复。因此，蓝色的-blue X在某种意义上与蓝色X相同。

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

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

Monads在Haskell中变得很大，因为Haskell需要一种方法来在现实世界中做事情，而不违反它的数学纯世界，在那里什么都不会发生。解决方案是添加某种稀释形式的元编程，其中我们引入了一个形容词，即“产生__的程序”。如何获取当前日期呢?好吧，Haskell不能在没有unsafePerformIO的情况下直接做到这一点，但它会让你描述和组合产生当前日期的程序。在这个远景中，您应该描述一个不产生任何名为“Main”的程序。Main "编译器会根据你的描述，把这个程序作为二进制可执行文件交给你，让你随时可以运行。

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

的自由单体

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

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

它是通用的，因为蓝色的⁰X只是一个X。free blue X是一个blue^{< em > < / em >} blue^{< em > n < / em >} X也就是一个blue^{< em > < / em > + n < em > < / em >} X。它实现了“崩溃”，因此根本不实现崩溃，内部蓝色是任意嵌套的。

这也意味着你可以将你要选择的monad推迟到以后的日期，以后你可以定义一个函数，它将__abc0 -蓝色的X简化为蓝色的X，并将所有这些分解为蓝色的__abc3 X，然后另一个从X到蓝色的X的函数将自始至终给出蓝色的__abc7 X。