使用foldl和没有样板的Reader monad递归地行走AST

Question

我穿越了AST使用简单的模式匹配,并在Reader单子.

在我的项目的其他地方,我已经定义了一个walk遍历AST 的函数,该函数的核心用于foldl将访问树中每个节点的结果减少为单个幺半群结果(例如,从特殊结果生成"符号表")树中的节点).

我的问题是:是否可以将这两种方法结合起来并使用像我的函数这样的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(可能在以后State,可能在堆栈中).

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

Answer 1

一种透镜的方法

通用编程闪耀的时刻!这个问题,即在没有样板的情况下折叠递归数据类型的问题,是uniplate/biplate库的动机.该设计现在Control.Lens.Plated以lens包装中的最现代形式存在.要利用它:

• 打开DeriveDataTypeable并添加deriving (Data)到您的Node,ArgumentList,Argument.

• 马上你能利用的uniplate从Data.Data.Lens.这是一个遍历,一个对象 - 当传递给右镜头助手时 - 会产生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遍历(和折叠)的方式.镜头的层次结构以及它们如此构图的原因超出了这个小文本框的范围,但足以说它们非常有用.

• 使用foldlOf帮助程序Control.Lens.Fold来实现您的walk功能:

  walk' :: Monoid a => (Node -> a) -> a -> Node -> a
  walk' f acc n =
    foldlOf (cosmosOf uniplate . to f) (<>) acc n
  

  还不错.to f从你身上创造一个吸气剂f,它由宇宙褶皱组成,以达到所有的后代; 来自此吸气剂的每个值都折叠并累积到我们的幺半群中.

至于node,你必须建立一个自定义折叠.cosmosOf uniplate在这里不能很好地工作,因为有时你会使递归短路(例如在这种Blockquote情况下).你必须从镜头助手那里逐渐编写cosmosOf foo和制作foo零碎的东西; 请注意,您仍然可以使用它来释放自定义折叠中的大多数情况.这是相当多的代码而且它变得非常糟糕,所以我将它作为练习留给读者.我90%确定它是可能的.uniplate

至于读者monad,你可以使用foldlMOf或注意type Env = Reader State String同构,State -> String并注意State -> String有一个Monoid实例因为Monoid String存在.这就意味着你应该能够像上面那样node用非monadic 实现foldlOf- 我们真正想做的就是连接一堆monoidal值,最后.

这个解决方案并不完美:它需要未来的代码阅读器知道关于镜头的一些知识以及遍历/折叠/获取器是如何凝聚的,Data.Data以及为什么这些功能都具有有趣的小Of后缀.但是你必须承认,有一种美妙的简洁和强大的功能可以Plated抽象出折叠自定义数据类型的无聊递归部分,因此你只需要对数据结构(如BreakTagin node)和edge case(如Blockquotein )的叶子进行模式匹配.node).