haskell - 使用 Foldl 和 Reader monad 递归地遍历 AST，无需样板

Question

我正在遍历an AST使用simple pattern matching和 the Reader monad .

在我的项目的其他地方，我定义了 a walk function用于遍历 AST，其核心使用 foldl 将访问树中每个节点的结果减少为单个幺半群结果(例如，来自树中特殊节点的 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 函数已经编码了如何获取每个模式的子级以及如何执行 AST 的有序遍历的知识。我真的不想为每次遍历都重新实现它，因此最好在更多地方使用 walk ，包括我需要使用 Reader 的地方(并且可能稍后，状态，可能在堆栈中)。

这些东西可以有效地结合起来吗？

Answer 1

透镜方法

泛型编程大放异彩的时刻!这个问题，即在没有样板的情况下折叠递归数据类型的问题，就是 uniplate/biplate library 的动机。 。该设计现在以其最现代的形式继续存在于Control.Lens.Plated中。 c/o lens 包。要利用它:

• 打开 DeriveDataTypeable 并将 deriving (Data) 添加到您的 Node、ArgumentList、参数。

• 您立即可以利用 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 的每个值都被折叠并累积到我们的幺半群中。

对于节点，您必须构建一个自定义折叠。 cosmosOf uniplate 在这里效果不太好，因为有时您会短路递归(例如在 Blockquote 情况下)。您必须编写 cosmosOf foo 并从 lens helpers 中逐步构建 foo ;请注意，您仍然可以使用 uniplate 来释放自定义折叠中的大多数案例。这是相当大的代码，而且已经很晚了，所以我将其作为练习留给读者。我 90% 确信这是可能的。

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

这个解决方案并不完美:它要求 future 的代码阅读者了解有关lens的大量知识，以及遍历/折叠/ getter 如何与Data.Data结合在一起，以及为什么这些函数都有有趣的地方它们上面有一些 Of 后缀。但您必须承认，Plated 有一种美丽的简洁性和强大功能，它抽象了折叠自定义数据类型的无聊递归部分，因此您只需在数据结构的叶子上进行模式匹配(例如node 中的 BreakTag)和边缘情况(例如 node 中的 Blockquote)。