什么是免费monad？
本文翻译自：What are free monads?
I've seen the term Free Monad pop up every now and then for some time, but everyone just seems to use/discuss them without giving an explanation of what they are. 我见过的长期无单子弹出每一个 现在 和 随后一段时间，但每个人似乎只是使用/讨论这些问题没有给予它们是什么解释。 So: what are free monads? 所以：什么是免费的monads？ (I'd say I'm familiar with monads and the Haskell basics, but have only a very rough knowledge of category theory.) （我会说我熟悉monad和Haskell的基础知识，但对类别理论只有非常粗略的了解。）
#1楼
参考：https://stackoom.com/question/u1W9/什么是免费monad
#2楼
A free foo happens to be the simplest thing that satisfies all of the 'foo' laws. 一个免费的foo恰好是满足所有'foo'定律的最简单的东西。 That is to say it satisfies exactly the laws necessary to be a foo and nothing extra. 也就是说它完全满足成为foo所必需的法则，而不是额外的。
A forgetful functor is one that "forgets" part of the structure as it goes from one category to another. 一个健忘的仿函数是一个“忘记”结构的一部分，因为它从一个类别到另一个类别。
Given functors F : D -> C , and G : C -> D , we say F -| G 假设F : D -> C和G : C -> D ，我们说F -| G F -| G , F is left adjoint to G , or G is right adjoint to F whenever forall a, b: F a -> b is isomorphic to a -> G b , where the arrows come from the appropriate categories. F -| G ， F与G伴随，或者G与F伴随F ，b： F a -> b与a -> G b同构，其中箭头来自适当的类别。
Formally, a free functor is left adjoint to a forgetful functor. 正式地，一个*的仿函数与一个健忘的仿函数相伴。
The Free Monoid *幺半群
Let us start with a simpler example, the free monoid. 让我们从一个更简单的例子开始，即免费的幺半群。
Take a monoid, which is defined by some carrier set T , a binary function to mash a pair of elements together f :: T → T → T , and a unit :: T , such that you have an associative law, and an identity law: f(unit,x) = x = f(x,unit) . 取一个monoid，由一些载体集T定义，一个二元函数将一对元素混合在一起f :: T → T → T ，和一个unit :: T ，这样你就有了一个关联定律和一个单一的定律： f(unit,x) = x = f(x,unit) 。
You can make a functor U from the category of monoids (where arrows are monoid homomorphisms, that is, they ensure they map unit to unit on the other monoid, and that you can compose before or after mapping to the other monoid without changing meaning) to the category of sets (where arrows are just function arrows) that 'forgets' about the operation and unit , and just gives you the carrier set. 你可以从monoids类别中创建一个函子U （其中箭头是monoid同态，也就是说，它们确保它们将unit映射到另一个monoid上的unit ，并且你可以在映射到另一个monoid之前或之后组合而不改变含义）对于操作和unit “忘记”的集合类别（箭头只是功能箭头），只给你载体集。
Then, you can define a functor F from the category of sets back to the category of monoids that is left adjoint to this functor. 然后，您可以将一个仿函数F从集合的类别定义回与该仿函数相伴的monoids类别。 That functor is the functor that maps a set a to the monoid [a] , where unit = [] , and mappend = (++) . 该仿函数是将集合a映射到monoid [a]的函子，其中unit = [] ， mappend = (++) 。
So to review our example so far, in pseudo-Haskell: 那么到目前为止，回顾我们的例子，在伪Haskell中：
U : Mon → Set -- is our forgetful functor
U (a,mappend,mempty) = a
F : Set → Mon -- is our free functor
F a = ([a],(++),[])
Then to show F is free, need to demonstrate that it is left adjoint to U , a forgetful functor, that is, as we mentioned above, we need to show that 然后为了表明F是免费的，需要证明它与U ，一个健忘的仿函数相伴，也就是说，正如我们上面提到的，我们需要证明
F a → b is isomorphic to a → U b F a → b与a → U b同构
now, remember the target of F is in the category Mon of monoids, where arrows are monoid homomorphisms, so we need a to show that a monoid homomorphism from [a] → b can be described precisely by a function from a → b . 现在，记住F的目标是幺半群的类别Mon ，其中箭头是幺半群同态，所以我们需要一个来证明来自[a] → b的幺半群同态可以用a → b的函数精确描述。
In Haskell, we call the side of this that lives in Set (er, Hask , the category of Haskell types that we pretend is Set), just foldMap , which when specialized from Data.Foldable to Lists has type Monoid m => (a → m) → [a] → m . 在Haskell中，我们称之为Set （er， Hask ，我们假装设置的Haskell类型的类别），只是foldMap ，当从Data.Foldable到Lists专用时，类型为Monoid m => (a → m) → [a] → m 。
There are consequences that follow from this being an adjunction. 这是一个附带的后果。 Notably that if you forget then build up with free, then forget again, its just like you forgot once, and we can use this to build up the monadic join. 值得注意的是，如果你忘记然后*积累，那么再次忘记，它就像你忘了一次，我们可以用它来建立monadic连接。 since UFUF ~ U(FUF) ~ UF , and we can pass in the identity monoid homomorphism from [a] to [a] through the isomorphism that defines our adjunction,get that a list isomorphism from [a] → [a] is a function of type a -> [a] , and this is just return for lists. 因为UFUF ~ U(FUF) ~ UF ，我们可以通过定义我们的adjunction的同构，从[a]到[a]传递同一性的monoid同态，从[a] → [a]获得一个列表同构类型a -> [a]函数，这只是列表的返回。
You can compose all of this more directly by describing a list in these terms with: 您可以通过使用以下术语描述列表来直接撰写所有这些内容：
newtype List a = List (forall b. Monoid b => (a -> b) -> b)
The Free Monad 免费Monad
So what is a Free Monad ? 什么是免费Monad ？
Well, we do the same thing we did before, we start with a forgetful functor U from the category of monads where arrows are monad homomorphisms to a category of endofunctors where the arrows are natural transformations, and we look for a functor that is left adjoint to that. 好吧，我们做了我们之前做过的同样的事情，我们从一个健忘的仿函数U开始，从monad类别中箭头是monad homomorphisms到一类endofunctors，其中箭头是自然变换，我们寻找一个左边伴随的仿函数那个。
So, how does this relate to the notion of a free monad as it is usually used? 那么，这与通常使用的免费monad的概念有什么关系呢？
Knowing that something is a free monad, Free f , tells you that giving a monad homomorphism from Free f -> m , is the same thing (isomorphic to) as giving a natural transformation (a functor homomorphism) from f -> m . 知道了什么是一个免费的单子， Free f ，告诉你，从给定的单子同态Free f -> m ，是同样的事情（同构）为给从自然转化（仿函数同态） f -> m 。 Remember F a -> b must be isomorphic to a -> U b for F to be left adjoint to U. U here mapped monads to functors. 记住F a -> b必须与a -> U b同构，以便F与U同伴。这里将monad映射到仿函数。
F is at least isomorphic to the Free type I use in my free package on hackage. F至少与我在hackage上的free软件包中使用的Free类型同构。
We could also construct it in tighter analogy to the code above for the free list, by defining 我们还可以通过定义来构建它，以类似于上面的代码为*列表
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 Comonads
We can construct something similar, by looking at the right adjoint to a forgetful functor assuming it exists. 我们可以构造类似的东西，通过查看正确的伴随假定它存在的健忘函子。 A cofree functor is simply /right adjoint/ to a forgetful functor, and by symmetry, knowing something is a cofree comonad is the same as knowing that giving a comonad homomorphism from w -> Cofree f is the same thing as giving a natural transformation from w -> f . 一个cofree仿函数简单/正确伴随/一个健忘的仿函数，并且通过对称性，知道一些cofree comonad就像知道从w -> Cofree f给出一个comonad homomorphism一样，就像给出一个自然变换一样w -> f 。
#3楼
Edward Kmett's answer is obviously great. Edward Kmett的回答显然很棒。 But, it is a bit technical. 但是，它有点技术性。 Here is a perhaps more accessible explanation. 这是一个可能更容易理解的解释。
Free monads are just a general way of turning functors into monads. 免费monad只是将仿函数转换为monad的一般方法。 That is, given any functor f Free f is a monad. 也就是说，给定任何仿函数f Free f是monad。 This would not be very useful, except you get a pair of functions 除非你得到一对函数，否则这不会很有用
liftFree :: Functor f => f a -> Free f a
foldFree :: Functor f => (f r -> r) -> Free f r -> r
the first of these lets you "get into" your monad, and the second one gives you a way to "get out" of it. 第一个让你“进入”你的monad，第二个给你一个“走出去”它的方法。
More generally, if X is a Y with some extra stuff P, then a "free X" is aa way of getting from a Y to an X without gaining anything extra. 更一般地说，如果X是带有一些额外东西P的Y，那么“*X”是从Y到X而不获得额外任何东西的一种方式。
Examples: a monoid (X) is a set (Y) with extra structure (P) that basically says it has an operation (you can think of addition) and some identity (like zero). 示例：monoid（X）是具有额外结构（P）的集合（Y），基本上表示它具有操作（您可以想到添加）和一些身份（如零）。
So 所以
class Monoid m where
mempty :: m
mappend :: m -> m -> m
Now, we all know lists 现在，我们都知道列表
data [a] = [] | a : [a]
Well, given any type t we know that [t] is a monoid 好吧，给任何类型的t我们知道， [t]是幺
instance Monoid [t] where
mempty = []
mappend = (++)
and so lists are the "free monoid" over sets (or in Haskell types). 所以列表是集合（或Haskell类型）中的“免费幺半群”。
Okay, so free monads are the same idea. 好吧，所以免费的monad是一样的想法。 We take a functor, and give back a monad. 我们带一个仿函数，然后给一个monad。 In fact, since monads can be seen as monoids in the category of endofunctors, the definition of a list 事实上，由于monads可以被视为endofunctors类别中的monoids，因此定义了一个列表
data [a] = [] | a : [a]
looks a lot like the definition of free monads 看起来很像免费monads的定义
data Free f a = Pure a | Roll (f (Free f a))
and the Monad instance has a similarity to the Monoid instance for lists 并且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
now, we get our two operations 现在，我们得到了两个操作
-- 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)
#4楼
A Haskell free monad is a list of functors. Haskell免费monad是一个仿函数列表。 Compare: 相比：
data List a = Nil | Cons a (List a )
data Free f r = Pure r | Free (f (Free f r))
Pure is analogous to Nil and Free is analogous to Cons . Pure类似于Nil ， Free类似于Cons 。 A free monad stores a list of functors instead of a list of values. 免费monad存储一个函子列表而不是值列表。 Technically, you could implement free monads using a different data type, but any implementation should be isomorphic to the above one. 从技术上讲，您可以使用不同的数据类型实现免费monad，但任何实现都应该与上面的实现同构。
You use free monads whenever you need an abstract syntax tree. 只要需要抽象语法树，就可以使用免费的monad。 The base functor of the free monad is the shape of each step of the syntax tree. free monad的基础仿函数是语法树每一步的形状。
My post , which somebody already linked, gives several examples of how to build abstract syntax trees with free monads 我的帖子 ，有人已经链接，提供了几个如何使用免费monad构建抽象语法树的示例
#5楼
Here's an even simpler answer: A Monad is something that "computes" when monadic context is collapsed by join :: m (ma) -> ma (recalling that >>= can be defined as x >>= y = join (fmap yx) ). 这里有一个更简单的答案：当monadic上下文被join :: m (ma) -> ma折叠时，Monad就是“计算”的东西（回想一下>>=可以定义为x >>= y = join (fmap yx) ）。 This is how Monads carry context through a sequential chain of computations: because at each point in the series, the context from the previous call is collapsed with the next. 这就是Monads如何通过顺序计算链传递上下文：因为在序列中的每个点，前一个调用的上下文与下一个调用一起折叠。
A free monad satisfies all the Monad laws, but does not do any collapsing (ie, computation). 一个免费的monad满足所有Monad定律，但不做任何崩溃（即计算）。 It just builds up a nested series of contexts. 它只是构建了一系列嵌套的上下文。 The user who creates such a free monadic value is responsible for doing something with those nested contexts, so that the meaning of such a composition can be deferred until after the monadic value has been created. 创建这样一个*monadic值的用户负责使用那些嵌套的上下文做某事，这样这个组合的含义可以推迟到创建monadic值之后。
#6楼
I think a simple concrete example will help. 我认为一个简单的具体例子会有所帮助。 Suppose we have a functor 假设我们有一个仿函数
data F a = One a | Two a a | Two' a a | Three Int a a a
with the obvious fmap . 用明显的fmap 。 Then Free F a is the type of trees whose leaves have type a and whose nodes are tagged with One , Two , Two' and Three . 然后Free F a是叶子类型为a且其节点标记为One ， Two ， Two'和Three的树的类型。 One -nodes have one child, Two - and Two' -nodes have two children and Three -nodes have three and are also tagged with an Int . One节点有一个子节点， Two节点和Two'节点有两个子节点， Three节点有三个节点，并且还用Int标记。
Free F is a monad. Free F是monad。 return maps x to the tree that is just a leaf with value x . return map x映射到只是值为x的叶子的树。 t >>= f looks at each of the leaves and replaces them with trees. t >>= f查看每个叶子并用树替换它们。 When the leaf has value y it replaces that leaf with the tree fy . 当叶子具有值y它用树fy替换该叶子。
A diagram makes this clearer, but I don't have the facilities for easily drawing one! 图表使这更清楚，但我没有轻松绘制一个的设施！