使用 foldl 和没有样板的 Reader monad 递归遍历 AST

Question

我正在穿越an AST using simple pattern matching and the Reader monad。

在我项目的其他地方，我从树中的特殊节点定义了 a walk function for traversing the AST, which at its heart uses foldl to reduce the results of visiting each node in the tree into a single monoidal result (for example, to produce a "symbol table"。

我的问题是：是否可以结合这两种方法并使用像我的 walk 函数这样的函数：

walk :: Monoid a => (Node -> a) -> a -> Node -> a
walk f acc n = foldl (walk f) (acc <> f n) children
  where
    children = case n of
      Blockquote b           -> b
      DocBlock d             -> d
      FunctionDeclaration {} -> functionBody n
      List l                 -> l
      ListItem i             -> i
      Paragraph p            -> p
      Unit u                 -> u
      _                      -> [] -- no Node children

和 Reader - 就像下面代码中的遍历（为简洁起见省略了一些位） - 同时？

markdown :: Node -> String
markdown n = runReader (node n) state
  where state = State (getSymbols n) (getPluginName n)

node :: Node -> Env
node n = case n of
  Blockquote b            -> blockquote b >>= appendNewline >>= appendNewline
  DocBlock d              -> nodes d
  FunctionDeclaration {}  -> nodes $ functionBody n
  Paragraph p             -> nodes p >>= appendNewline >>= appendNewline
  Link l                  -> link l
  List ls                 -> nodes ls >>= appendNewline
  ListItem l              -> fmap ("- " ++) (nodes l) >>= appendNewline
  Unit u                  -> nodes u

我在这里的使用动机是我的 walk 函数已经编码了如何为每个模式获取 children 以及如何执行 AST 的 in-order 遍历的知识.我真的不想为每次遍历都重新实现它，所以在更多地方使用 walk 会很好，包括我需要使用 Reader 的地方（可能稍后， State，可能在堆栈中）。

这些东西能结合起来吗？

Answer 1

一种狭隘的方法

泛型编程大放异彩的时刻！这个问题，即在没有样板的情况下折叠递归数据类型的问题，是 uniplate/biplate library. That design now lives on in its most modern form in Control.Lens.Plated c/o lens 包的动机。要利用它：

打开 DeriveDataTypeable 并将 deriving (Data) 添加到您的 Node、ArgumentList、Argument.
您可以立即利用 Data.Data.Lens 中的 uniplate。这是一个遍历，一个对象 - 当传递给正确的镜头助手时 - 将为您提供给定 Node 内类型 Node 的所有值。基本上它运行递归 walk 函数的一步。

一个例子：

λ> Blockquote [BreakTag, Blockquote [BreakTag]] ^.. uniplate
[BreakTag,Blockquote [BreakTag]]
λ> Blockquote [BreakTag, Blockquote [BreakTag]] ^.. uniplate . uniplate
[BreakTag]
λ> Blockquote [BreakTag, Blockquote [BreakTag]] ^.. uniplate . uniplate . uniplate
[]

但是等等，还有更多。如果说 uniplate 是泛型的一小步，那么 cosmosOf uniplate 就是程序员的一大步。 cosmosOf 重复使用 uniplate 从给定的 Node.
中检索子代、孙代、曾孙代等
```
λ> Blockquote [BreakTag, Blockquote [BreakTag]] ^..  cosmosOf uniplate
[ Blockquote [BreakTag,Blockquote [BreakTag]]
, BreakTag
, Blockquote [BreakTag]
, BreakTag]
```
在这两个示例中，我们都利用了 lens 遍历（和折叠）的组合方式。镜头的层次结构以及为什么它们组合得如此好超出了这个小文本框的范围，但足以说明它们非常有用。
使用 Control.Lens.Fold 中的 foldlOf 助手来实现您的 walk 功能：
```
walk' :: Monoid a => (Node -> a) -> a -> Node -> a
walk' f acc n =
  foldlOf (cosmosOf uniplate . to f) (<>) acc n
```
还不错。 to f 从你的 f 中创建了一个 getter，它由宇宙褶皱组成，可以到达所有后代； getter 中的每个值都折叠并累积到我们的幺半群中。

至于 node，您必须构建自定义折叠。 cosmosOf uniplate 在这里效果不佳，因为有时您会短路递归（例如，在 Blockquote 的情况下）。您必须编写 cosmosOf foo 并从 lens helpers 零碎地构建 foo；请注意，您仍然可以使用 uniplate 来解除自定义折叠中的大多数情况。这是相当多的代码，而且已经很晚了，所以我将把它留作 reader 的练习。我 90% 确定这是可能的。

至于 reader monad，您可以使用 foldlMOf 或注意 type Env = Reader State String 与 State -> String 同构并注意 State -> String 有一个Monoid 个实例，因为 Monoid String 存在。这一切都意味着你应该能够像我们上面所做的那样用非单值foldlOf实现node——我们真正想做的就是最后连接一堆幺半群值。

这个解决方案并不完美：它需要未来的代码 readers 来了解关于镜头的一些知识以及 traversals/folds/getters 如何与 Data.Data 凝胶以及为什么这些功能都上面有有趣的 Of 后缀。但是你必须承认 Plated 有一种漂亮的简洁性和强大的功能，它抽象掉了折叠自定义数据类型的无聊递归部分，所以你只需要在数据结构的叶子上进行模式匹配（比如 BreakTag in node) 和边缘情况（如 Blockquote in node）。

Answer 2

您的 walk 函数看起来非常像 Foldable class，它是 Traversable 的超 class（dfeuer 还在一条评论）。在你的位置我会看看 mono-traversable package.

但我有预感，您的 Node 类型实际上不会像当前制定的那样成为一个好的 MonoTraversable 实例。非正式地，原因是这些概念之间没有很好的区分：

AST 的结构：哪些节点是哪个节点的子节点。
AST的内容：每个节点的"attributes"。

考虑 Functor 和 Traversable class 的一种非常非正式的方式是，它们对值的 "content" 进行操作而不改变 "structure"（但 beware of taking that analogy too literally）。我考虑过为您的 Node 类型编写一个 MonoTraversable 实例，但经过一番思考后很快就放弃了：

{-# LANGUAGE TypeFamilies #-}

import Data.MonoTraversable

-- Here is the root of the problem.  The type function 
-- `Element` is supposed to pick out which pieces of a 
-- `Node` are its "content" as opposed to its "structure,"
-- but with `Node` as formulated there isn't a distinction!
type instance Element Node = Node

鉴于此，otraverse 方法具有以下主要类型：

otraverse :: Applicative f => (Element mono -> f (Element mono)) -> mono -> f mono

...当 mono := Node:

时将以这种特殊类型结束

otraverse :: Applicative f => (Node -> f Node) -> Node -> f Node

...而且我担心有人会尝试调用 otraverse 并使用丢弃根节点的子节点的函数，例如，当有人尝试 otraverse (return Separator) 时它有多邪恶？

我还没有确定这些实例是否非法，所以我可能在这里担心什么，值得检查我是否错了。不过按照我的设计感觉肯定是"smells bad"

那怎么办？我会考虑重新制定 Node 类型，将其分为两种类型：

一种 Content 类型，表示在 AST 从左到右的每一步中可见的信息，但不表示 Content 嵌套的方式；
定义树的可能形状的 Structure 类型——Content 的嵌套方式。

一旦完成，您就可以像这样重新表述您的 walk 函数：

walk :: Monoid a => (Content -> a) -> a -> Structure -> a

注意这个函数的第二个参数（初始acc :: Monoid a => a值）是多余的，这两个函数看起来可以相互定义：

walk' :: Monoid a => (Content -> a) -> Structure -> a
walk' f = walk f mempty

walk :: Monoid a => (Content -> a) -> a -> Structure -> a
walk f acc tree = acc <> walk' f tree

然后我的 walk' 签名看起来像是 mono-traversable:

中的 ofoldMap 方法

ofoldMap :: Monoid m => (Element mono -> m) -> mono -> m

然后很自然地会问你是否可以为你重新格式化的类型实现 MonoTraversable 并获得我上面提到的签名的 otraverse 操作，它专门用于 f := Reader r， mono := Structure 和 Element mono := Content 将是：

otraverse :: (Content -> Reader r Content) -> Structure -> Reader r Structure

使用 foldl 和没有样板的 Reader monad 递归遍历 AST

Recursively walking an AST using foldl and the Reader monad without boilerplate

haskell

monads

fold

parsec

reader-monad

一种狭隘的方法