19

我想我对 free monad 是什么有一个粗略的了解，但我希望有一种更好的方式来可视化它。

自由岩浆只是二叉树是有道理的，因为这就像你可以做到的那样“一般”而不会丢失任何信息。

同样，自由幺半群只是列表是有道理的，因为操作的顺序并不重要。现在“二叉树”中存在冗余，因此如果有意义的话，您可以将其展平。

出于类似的原因，自由组看起来像分形是有道理的：https ://en.wikipedia.org/wiki/Cayley_graph#/media/File:Cayley_graph_of_F2.svg 为了获得其他组，我们只需识别不同的元素该组的“相同”，我们得到其他组。

我应该如何可视化免费的单子？现在，我只是认为它是你能想象到的最通用的抽象语法树。本质上是这样吗？还是我过于简单化了？

同样，从自由单子到列表或其他单子，我们会失去什么？我们确定什么是“相同的”？

我感谢所有阐明这一点的评论。谢谢！

4

2 回答 2

15

现在，我只是认为 [the free monad] 是你能想象到的最通用的抽象语法树。本质上是这样吗？还是我过于简单化了？

你过于简单化了：

  1. “Free monad”是“the free monad over a specific functor ”或Free f a数据类型的缩写，实际上对于f.
  2. 没有一种通用结构是所有自由单子都有的。它们的结构分解为：
    • Free自己贡献了什么
    • 不同选择的贡献是什么f

但是，让我们采取不同的方法。我首先通过研究密切相关的操作 monad来学习自由 monad，它具有更统一、更易于可视化的结构。我强烈建议您从链接本身进行研究。

定义操作 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 的“指令”类型，通常是 GADT。例如（取自链接）：

data StackInstruction a where
    Pop  :: StackInstruction Int
    Push :: Int -> StackInstruction ()

因此Program，在操作单子中，非正式地，我将其可视化为指令的“动态列表”，其中任何指令的执行产生的结果都用作函数的输入，该函数决定了“指令清单”是。构造函数将Bind指令与“尾选择器”函数配对。

许多自由单子也可以用类似的术语来可视化——你可以说为给定的自由单子选择的函子用作它的“指令集”。但是对于自由单子，“指令”的“尾巴”或“孩子”由Functor自身管理。举一个简单的例子（取自Gabriel González 关于该主题的热门博客文章）：

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

而在操作单子中，用于生成“尾巴”的函数属于Program类型（在Bind构造函数中），而在自由单子中，尾巴属于“指令”/Functor类型。这允许自由 monad 的“指令”（现在正在分解的类比）有一个“尾巴”（如Outputor 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 称为“语法树”的人的反对意见——它们的实际使用要求节点的“子节点”不透明地隐藏在函数中。您通常无法完全检查这棵“树”！

所以真的，当你开始着手时，如何可视化一个自由单子完全取决于Functor你用来参数化它的结构。有些看起来像列表，有些看起来像树，还有一些看起来像“不透明树”，具有作为节点的功能。（有人曾经用类似“函数是一个树节点，其子节点与可能的参数一样多”这样的行来回应我的反对意见。）

于 2015-12-02T23:02:29.297 回答
2

你可能听说过

Monad 是一类内函子中的幺半群

你已经提到过幺半群只是列表。所以你来了。

稍微扩展一下：

data Free f a = Pure a
              | Free (f (Free f a))

这不是一个普通的列表a，而是一个包含 tail 的列表f。如果您编写多个嵌套绑定的值结构，您会看到它：

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在上面的示例中是 sum 类型：

data Sum a = Inl a | Inr a
  deriving Functor

那么列表实际上是一棵树，因为在每个构造函数中我们可以向左或向右分支。

你可能听说过

Applicative 是一类内函子中的幺半群

...类别只是不同。在Roman Cheplyaka 的博客文章中有不同的免费应用编码的很好的可视化。

所以免费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上面的monadApplicative (FreeA f a)相反。Free

还有免费的Functor

data Coyoneda f a = Coyoneda :: (b -> a) -> f b -> Coyoneda f a

这使得任何* -> *类型Functor。将其与Applicative上面的免费进行比较。在应用情况下，我们有一个长度为n的f a值的异构列表和一个组合它们的 n 元函数。Coyoneda 是上述的一元特例。

我们可以结合Coyoneda并Free制作Operational免费的单子。正如其他答案所提到的，这棵树很难想象成树，因为其中涉及到功能。OTOH，您可以将这些延续想象为图片中不同的神奇箭头:)

于 2015-12-03T00:23:35.170 回答