可视化自由 Monad
Visualizing the Free Monad
我想我对免费的 monad 是什么有一个大概的了解，但我想有一个更好的方式来形象化它。
自由岩浆只是二叉树是有道理的，因为在不丢失任何信息的情况下，你可以做到 "general"。
同样，自由幺半群只是列表是有道理的，因为操作顺序无关紧要。 "binary tree" 中现在有一个冗余，因此您可以将其展平，如果这有意义的话。
出于类似的原因，自由团体看起来有点像分形是有道理的：https://en.wikipedia.org/wiki/Cayley_graph#/media/File:Cayley_graph_of_F2.svg
要获得其他组，我们只需将组的不同元素标识为 "same"，然后我们获得其他组。
我应该如何可视化免费的 monad？现在，我只是把它想象成你能想象到的最通用的抽象语法树。本质上是这样吗？还是我过于简单化了？
另外，类似地，从自由 monad 到列表或其他 monad，我们会失去什么？我们要确定什么是 "same"?
我感谢所有对此有所启发的评论。谢谢！
Right now, I just think of [the free monad] as the most general abstract syntax tree that you can imagine. Is that essentially it? Or am I oversimplifying it?
你把它简单化了：
- "Free monad" 是 "the free monad over a specific functor" 或
Free f a 数据类型的缩写，实际上是 f.[=59= 的每个选择的不同自由 monad ]
- 没有一种通用结构是所有自由 monad 都具有的。它们的结构分为：
Free 自己的贡献f
但让我们换一种方式。我通过首先研究密切相关的 operational monad 来学习自由单子，它具有更统一的 easier-to-visualize 结构。我强烈建议您从 link 本身学习。
定义操作 monad 的最简单方法是这样的：
{-# LANGUAGE GADTs #-}
data Program instr a where
Return :: a -> Program instr a
Bind :: instr x -- an "instruction" with result type `x`
-> (x -> Program instr a) -- function that computes rest of program
-> Program instr a -- a program with result type `a`
...其中 instr 类型参数表示 monad 的 "instruction" 类型，通常是 GADT。例如（取自link）：
data StackInstruction a where
Pop :: StackInstruction Int
Push :: Int -> StackInstruction ()
所以操作 monad 中的 Program，非正式地，我将其可视化为 "dynamic list" 指令，其中执行任何指令产生的结果用作决定 "instruction list" 的 "tail" 是什么的函数。 Bind 构造函数将指令与 "tail chooser" 函数配对。
许多自由单子也可以用类似的术语来形象化——你可以说为给定的自由单子选择的仿函数作为它的 "instruction set." 但是对于自由单子 "tails" 或 [= "instruction" 中的 74=] 由 Functor 本身管理。所以一个简单的例子（取自Gabriel González's popular blog entry on the topic）：
data Free f r = Free (f (Free f r)) | Pure r
-- The `next` parameter represents the "tails" of the computation.
data Toy b next =
Output b next
| Bell next
| Done
instance Functor (Toy b) where
fmap f (Output b next) = Output b (f next)
fmap f (Bell next) = Bell (f next)
fmap _ Done = Done
虽然在操作 monad 中，用于生成 "tail" 的函数属于 Program 类型（在 Bind 构造函数中），但在自由 monad 中，尾部属于 "instruction"/Functor类型。这允许自由 monad 的 "instructions"（一个现在正在分解的类比）有单个 "tail"（如 Output 或 Bell），零尾（如 Done) 或多个尾巴，如果你愿意的话。或者，在另一种常见模式中，next 参数可以是嵌入式函数的结果类型：
data Terminal a next =
PutStrLn String next
| GetLine (String -> next) -- can't access the next "instruction" unless
-- you supply a `String`.
instance Functor Terminal where
fmap f (PutStrLn str next) = PutStrLn str (f next)
fmap f (GetLine g) = GetLine (fmap f g)
顺便说一句，这是我长期以来对那些将自由或可操作的 monad 称为 "syntax trees" 的人的反对意见——它们的实际使用要求不透明地隐藏节点的 "children"在一个函数里面。您通常无法完全检查此 "tree"!
所以真的，当你深入研究它时，如何可视化一个自由的 monad 完全取决于你用来参数化它的 Functor 的结构。有的像列表，有的像树，有的像"opaque trees"，功能是节点。 （有人曾经用 "a function is a tree node with as many children as there are possible arguments." 之类的行回应我上面的反对意见）
你可能听说过
Monad is a monoid in a category of endofunctors
你已经提到幺半群只是列表。所以你来了。
稍微扩展一下：
data Free f a = Pure a
| Free (f (Free f a))
这不是普通的a列表，而是f中包含tail的列表。如果您编写多个嵌套绑定的值结构，您会看到它：
pure x >>= f >>= g >>= h :: Free m a
可能会导致
Free $ m1 $ Free $ m2 $ Free $ m3 $ Pure x
where m1, m2, m3 :: a -> m a -- Some underlying functor "constructors"
如果上面例子中的m是求和类型：
data Sum a = Inl a | Inr a
deriving Functor
然后列表实际上是一棵树，因为在每个构造函数中我们都可以向左或向右分支。
你可能听说过
Applicative is a monoid in a category of endofunctors
...只是类别不同而已。 Roman Cheplyaka's blog post.
中有不同的免费应用编码的漂亮可视化
所以免费Applicative也是一个列表。我将其想象为 f a 值的异构列表和单一函数：
x :: FreeA f a
x = FreeA g [ s, t, u, v]
where g :: b -> c -> d -> e -> a
s :: f b
t :: f c
u :: f d
v :: f e
在这种情况下，尾巴本身没有包裹在 f 中，而是单独包裹每个元素。这可能有助于也可能不会帮助理解 Applicative 和 Monad 之间的区别。
请注意，f 不需要 Functor 即可生成 Applicative (FreeA f a)，这与上面的 Free monad 相反。
还有免费的Functor
data Coyoneda f a = Coyoneda :: (b -> a) -> f b -> Coyoneda f a
这使得任何 * -> * 类型成为 Functor。将其与上面的免费 Applicative 进行比较。
在应用案例中，我们有一个长度为 n 的 f a 值的异构列表和一个将它们组合在一起的 n-ary 函数。
Coyoneda 是上面的 1 进制特例。
我们可以组合 Coyoneda 和 Free 来制作 Operational 自由 monad。正如其他答案所提到的那样，由于涉及功能，很难将其想象成树。 OTOH，您可以将这些延续想象成图片中不同的神奇箭头:)
我想我对免费的 monad 是什么有一个大概的了解，但我想有一个更好的方式来形象化它。
自由岩浆只是二叉树是有道理的，因为在不丢失任何信息的情况下，你可以做到 "general"。
同样，自由幺半群只是列表是有道理的，因为操作顺序无关紧要。 "binary tree" 中现在有一个冗余，因此您可以将其展平，如果这有意义的话。
出于类似的原因，自由团体看起来有点像分形是有道理的：https://en.wikipedia.org/wiki/Cayley_graph#/media/File:Cayley_graph_of_F2.svg 要获得其他组，我们只需将组的不同元素标识为 "same"，然后我们获得其他组。
我应该如何可视化免费的 monad？现在，我只是把它想象成你能想象到的最通用的抽象语法树。本质上是这样吗？还是我过于简单化了？
另外，类似地，从自由 monad 到列表或其他 monad，我们会失去什么？我们要确定什么是 "same"?
我感谢所有对此有所启发的评论。谢谢！
Right now, I just think of [the free monad] as the most general abstract syntax tree that you can imagine. Is that essentially it? Or am I oversimplifying it?
你把它简单化了：
- "Free monad" 是 "the free monad over a specific functor" 或
Free f a数据类型的缩写，实际上是f.[=59= 的每个选择的不同自由 monad ] - 没有一种通用结构是所有自由 monad 都具有的。它们的结构分为：
Free自己的贡献f的不同选择贡献了什么
但让我们换一种方式。我通过首先研究密切相关的 operational monad 来学习自由单子，它具有更统一的 easier-to-visualize 结构。我强烈建议您从 link 本身学习。
定义操作 monad 的最简单方法是这样的：
{-# LANGUAGE GADTs #-}
data Program instr a where
Return :: a -> Program instr a
Bind :: instr x -- an "instruction" with result type `x`
-> (x -> Program instr a) -- function that computes rest of program
-> Program instr a -- a program with result type `a`
...其中 instr 类型参数表示 monad 的 "instruction" 类型，通常是 GADT。例如（取自link）：
data StackInstruction a where
Pop :: StackInstruction Int
Push :: Int -> StackInstruction ()
所以操作 monad 中的 Program，非正式地，我将其可视化为 "dynamic list" 指令，其中执行任何指令产生的结果用作决定 "instruction list" 的 "tail" 是什么的函数。 Bind 构造函数将指令与 "tail chooser" 函数配对。
许多自由单子也可以用类似的术语来形象化——你可以说为给定的自由单子选择的仿函数作为它的 "instruction set." 但是对于自由单子 "tails" 或 [= "instruction" 中的 74=] 由 Functor 本身管理。所以一个简单的例子（取自Gabriel González's popular blog entry on the topic）：
data Free f r = Free (f (Free f r)) | Pure r
-- The `next` parameter represents the "tails" of the computation.
data Toy b next =
Output b next
| Bell next
| Done
instance Functor (Toy b) where
fmap f (Output b next) = Output b (f next)
fmap f (Bell next) = Bell (f next)
fmap _ Done = Done
虽然在操作 monad 中，用于生成 "tail" 的函数属于 Program 类型（在 Bind 构造函数中），但在自由 monad 中，尾部属于 "instruction"/Functor类型。这允许自由 monad 的 "instructions"（一个现在正在分解的类比）有单个 "tail"（如 Output 或 Bell），零尾（如 Done) 或多个尾巴，如果你愿意的话。或者，在另一种常见模式中，next 参数可以是嵌入式函数的结果类型：
data Terminal a next =
PutStrLn String next
| GetLine (String -> next) -- can't access the next "instruction" unless
-- you supply a `String`.
instance Functor Terminal where
fmap f (PutStrLn str next) = PutStrLn str (f next)
fmap f (GetLine g) = GetLine (fmap f g)
顺便说一句，这是我长期以来对那些将自由或可操作的 monad 称为 "syntax trees" 的人的反对意见——它们的实际使用要求不透明地隐藏节点的 "children"在一个函数里面。您通常无法完全检查此 "tree"!
所以真的，当你深入研究它时，如何可视化一个自由的 monad 完全取决于你用来参数化它的 Functor 的结构。有的像列表，有的像树，有的像"opaque trees"，功能是节点。 （有人曾经用 "a function is a tree node with as many children as there are possible arguments." 之类的行回应我上面的反对意见）
你可能听说过
Monad is a monoid in a category of endofunctors
你已经提到幺半群只是列表。所以你来了。
稍微扩展一下：
data Free f a = Pure a
| Free (f (Free f a))
这不是普通的a列表，而是f中包含tail的列表。如果您编写多个嵌套绑定的值结构，您会看到它：
pure x >>= f >>= g >>= h :: Free m a
可能会导致
Free $ m1 $ Free $ m2 $ Free $ m3 $ Pure x
where m1, m2, m3 :: a -> m a -- Some underlying functor "constructors"
如果上面例子中的m是求和类型：
data Sum a = Inl a | Inr a
deriving Functor
然后列表实际上是一棵树，因为在每个构造函数中我们都可以向左或向右分支。
你可能听说过
Applicative is a monoid in a category of endofunctors
...只是类别不同而已。 Roman Cheplyaka's blog post.
中有不同的免费应用编码的漂亮可视化所以免费Applicative也是一个列表。我将其想象为 f a 值的异构列表和单一函数：
x :: FreeA f a
x = FreeA g [ s, t, u, v]
where g :: b -> c -> d -> e -> a
s :: f b
t :: f c
u :: f d
v :: f e
在这种情况下，尾巴本身没有包裹在 f 中，而是单独包裹每个元素。这可能有助于也可能不会帮助理解 Applicative 和 Monad 之间的区别。
请注意，f 不需要 Functor 即可生成 Applicative (FreeA f a)，这与上面的 Free monad 相反。
还有免费的Functor
data Coyoneda f a = Coyoneda :: (b -> a) -> f b -> Coyoneda f a
这使得任何 * -> * 类型成为 Functor。将其与上面的免费 Applicative 进行比较。
在应用案例中，我们有一个长度为 n 的 f a 值的异构列表和一个将它们组合在一起的 n-ary 函数。
Coyoneda 是上面的 1 进制特例。
我们可以组合 Coyoneda 和 Free 来制作 Operational 自由 monad。正如其他答案所提到的那样，由于涉及功能，很难将其想象成树。 OTOH，您可以将这些延续想象成图片中不同的神奇箭头:)