haskell - ボイラープレートなしで foldl と Reader モナドを使用して AST を再帰的に歩く

Question

単純なパターンマッチングとmonadを使用して ASTをトラバースしています。Reader

私のプロジェクトの他の場所で、AST をトラバースするためのwalk関数foldlを定義しました。これは、ツリー内の各ノードを訪問した結果を単一のモノイド結果に減らすために使用されます (たとえば、特別なオブジェクトから「シンボルテーブル」を生成するため)。ツリー内のノード)。

私の質問は、これら2つのアプローチを組み合わせて、私の関数のような関数を使用することは可能ですか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、おそらくスタック内で)。

これらをうまく組み合わせることができるでしょうか。

score 5 · Accepted Answer

レンズのようなアプローチ

汎用プログラミングが輝く瞬間です! まさにこの問題、定型文なしで再帰的なデータ型を折り畳む問題が、ユニプレート/バイプレートライブラリの動機です。そのデザインは現在Control.Lens.Plated、lensパッケージ内で最もモダンな形で生き続けています。それを利用するには：

オンにして、、、にDeriveDataTypeable追加deriving (Data)します。NodeArgumentListArgument
すぐにuniplatefromを利用できますData.Data.Lens。これはトラバーサルであり、適切なレンズヘルパーに渡されるとNode、指定された内の type のすべての値を生成するオブジェクトですNode。基本的に、再帰walk関数の 1 ステップを実行します。

例：

λ> 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ケース)。lens ヘルパーから少しずつ作成cosmosOf fooして構築する必要があります。カスタムフォールドでほとんどのケースを排出するために引き続き使用できることに注意してください。これは非常に大きなコードであり、非常に遅くなっているので、読者の演習として残します。私はそれが可能であると90％確信しています。foouniplate

reader モナドに関しては、存在するためインスタンスを持つand と同型であるfoldlMOfnote を使用するか、noteのいずれかを使用できます。これはすべて、上で行ったように、非モナディックで実装できるはずであることを意味します。実際にやりたいことは、最終的に一連のモノイド値を連結することだけです。type Env = Reader State StringState -> StringState -> StringMonoidMonoid StringnodefoldlOf

このソリューションは完璧ではありません。将来のコードリーダーは、lens と、トラバーサル/フォールド/ゲッターがどのようにゲル化するか、Data.Dataおよびこれらの関数すべてに面白い小さなOf接尾辞が付いている理由について、十分な知識を持っている必要があります。しかし、カスタムデータ型の折り畳みの退屈な再帰部分を抽象化することには、美しい種類の簡潔さと力があることを認めなければならないPlatedため、データ構造のリーフ ( のようBreakTagにnode) とエッジケース (のようBlockquoteに) でパターンマッチするだけで済みます。 node）。

score 3 · Accepted Answer

あなたの関数は、のスーパークラスであるクラスwalkに非常によく似ています（dfeuerもコメントで指摘しています）。あなたの立場では、パッケージを見てみたいと思います。FoldableTraversablemono-traversable

しかし、あなたのNodeタイプは、現在定式化されているように実際には良いMonoTraversableインスタンスにはならないだろうという予感があります. その理由は、非公式に言えば、これらの概念が適切に分離されていないためです。

ASTの構造: どのノードがどのノードの子であるか。
ASTの内容: 各ノードの「属性」。

Functorクラスとクラスを非公式に考える 1 つの方法は、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型を少し再構成して、2 つの型に分割することを検討します。

ContentAST の左から右へのウォークの各ステップで表示される情報を表現する型Content。
Structureツリーの可能な形状 ( がどのようにContentネストされるか) を定義する型。

walkそれが完了したら、次のように関数を再定式化できます。

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

この関数の 2 番目の引数 (初期acc :: Monoid a => a値) は不要であることに注意してください。これら 2 つの関数は相互定義可能に見えます。

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'のように見えます：ofoldMapmono-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

haskell - ボイラープレートなしで foldl と Reader モナドを使用して AST を再帰的に歩く

2 に答える 2

レンズのようなアプローチ

Related

Reference