3

我正在使用简单的模式匹配和monad遍历AST。Reader

在我的项目的其他地方，我定义了一个用于遍历 AST 的walk函数，它的核心是用于将访问树中每个节点的结果减少为单个monoidalfoldl结果（例如，从特殊的树中的节点）。

我的问题是：是否可以结合这两种方法并使用像我的函数这样的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，可能在堆栈中）。

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

4

2 回答 2

5

一个镜头的方法

通用编程大放异彩的时刻！这个问题，即在没有样板的情况下折叠递归数据类型的问题，是单板/双板库的动机。该设计现在以最现代的形式在Control.Lens.Platedc/olens包装中继续存在。要利用它：

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

  • 您可以立即利用uniplatefrom 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遍历（和折叠）的方式。镜头的层次结构以及它们为何如此出色的构图超出了这个小文本框的范围，但只要说它们超级有用就足够了。

  • 使用foldlOfhelperControl.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，它与宇宙褶皱组成以到达所有后代；来自这个 getter 的每个值都被折叠并累积到我们的幺半群中。

至于node，你必须建立一个自定义折叠。cosmosOf uniplate在这里不能很好地工作，因为有时你会短路递归（例如在这种Blockquote情况下）。您将不得不编写cosmosOf foo和构建foo镜头助手；请注意，您仍然可以使用uniplate来解除自定义折叠中的大多数情况。这是相当多的代码，而且已经很晚了，所以我将把它作为练习留给读者。我有 90% 的把握这是可能的。

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

这个解决方案并不完美：它需要未来的代码阅读者了解一些关于镜头的知识，以及遍历/折叠/吸气剂如何融合Data.Data以及为什么这些函数都有有趣的小Of后缀。但是您必须承认，有一种简洁和强大的功能Plated可以抽象出折叠自定义数据类型的无聊递归部分，因此您只需在数据结构的叶子（如BreakTagin node）和边缘情况（如Blockquotein node）。

于 2016-04-05T07:15:54.797 回答
3

您的walk函数看起来非常像Foldable类，它是超类Traversable（dfeuer 也在评论中指出）。在你的位置上，我会看看mono-traversable包裹。

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

  1. AST的结构：哪些节点是哪些节点的子节点。
  2. AST的内容：每个节点的“属性”。

Functor考虑and类的一种非常非正式的方式Traversable是，它们对值的“内容”进行操作而不改变“结构”（但要注意不要过于字面地理解这个类比）。我考虑为您的类型编写一个MonoTraversable实例，Node但经过一番思考后迅速退出：

{-# 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)？

我还没有确定这些情况是否非法，所以我可能在这里什么都不担心，如果我错了，值得检查一下。但根据我的设计感觉，它肯定“闻起来很糟糕”。

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

  1. 一种Content类型，表示在 AST 从左到右的每一步中可见的信息，但不表示Contents 如何嵌套；
  2. 一种Structure定义树的可能形状的类型——s 如何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'签名看起来就像是ofoldMap来自以下的方法mono-traversable：

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
于 2016-04-06T22:54:29.243 回答