可视化免费Monad

我想我已经大致了解了免费monad是什么,但我想有一个更好的方式来形象化它.

有意义的是,自由岩浆只是二叉树,因为它可以像你一样"一般"而不会丢失任何信息.

同样,有意义的是,免费幺半群只是列表,因为操作顺序无关紧要.现在在"二叉树"中存在冗余,因此如果有意义的话,您可以将其展平.

有意义的是,自由群体看起来像分形,出于类似的原因:https://en.wikipedia.org/wiki/Cayley_graph#/media/File: Cayley_graph_of_F2.svg 并且为了得到其他群体,我们只是识别不同的元素该群体是"相同的",我们得到其他群体.

我应该如何形象化免费的monad？现在,我只是把它想象成你能想象的最通用的抽象语法树.这本质上是吗？还是我过度简化了？

同样,从免费monad到列表或其他monad,我们会失去什么？我们认为什么是"相同"？

我感谢所有能够阐明这一点的评论.谢谢!

现在,我只想到[免费monad]作为你能想象的最通用的抽象语法树.这本质上是吗？还是我过度简化了？

你过分简单了:

"免费monad"是" 特定仿函数的免费monad "或Free f a数据类型的缩写,实际上是每种选择的不同免费monad f.

所有免费单子都没有一个通用结构.他们的结构分解为:

什么是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`

...其中instrtype参数表示monad的"指令"类型,通常是GADT.例如(取自链接):

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

因此Program,在操作monad中,非正式地,我将其可视化为指令的"动态列表",其中由任何指令的执行产生的结果被用作函数的输入,该函数决定"尾部"的"尾部".指令表"是.的Bind构造对带"尾巴选择器"功能的指令.

许多免费的monad也可以用类似的术语表示 - 你可以说为给定的免费monad选择的仿函数作为它的"指令集".但是对于免费的monad,"指令"的"尾巴"或"孩子"由它Functor自己管理.这是一个简单的例子(摘自GabrielGonzá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

在操作monad中,用于生成"tail"的函数属于Program类型(在Bind构造函数中),在free monads中,tails属于"指令"/ Functor类型.这允许免费monad的"指令"(现在正在分解的类比)具有单个"尾部"(如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称为"语法树"的人的反对 - 实际使用它们要求节点的"子节点"不透明地隐藏在函数内.你一般不能完全检查这个"树"!

所以,实际上,当你了解它时,如何可视化一个免费的monad完全归结为Functor你用来参数化它的结构.有些看起来像列表,有些看起来像树,有些看起来像"不透明的树",功能作为节点.(有人曾经用一句话来回应我的反对意见,例如"函数是一个树节点,子节点和可能的参数一样多.")