2

識別された共用体にフォールドを実装しようとしています。DUはExprと呼ばれ、プログラム式を表し、多くの場合再帰的です。Exprsに対する操作の結果を再帰的に累積するフォールドを書き込もうとしています。以下は、折り目を書くための私の試みです。

let rec foldProceduralExpr (folder : 's -> Expr list -> 's) (state : 's) (expr : Expr) : 's =
    let children =
        match expr with
        | Series s -> s.SerExprs
        | Lambda l -> [l.LamBody; l.LamPre; l.LamPost]
        | Attempt a -> a.AttemptBody :: List.map (fun ab -> ab.ABBody) a.AttemptBranches
        | Let l -> l.LetBody :: List.concat (List.map (fun lb -> match lb with LetVariable (_, expr) -> [expr] | LetFunction (_, _, body, _, pre, post, _) -> [body; pre; post]) l.LetBindings)
        | Case c -> c.CaseTarget :: List.concat (List.map (fun branch -> [branch.TBBody; branch.TBTest]) c.CaseBranches)
        | Condition c -> List.concat (List.map (fun branch -> [branch.TBBody; branch.TBTest]) c.CondBranches)
        | List l -> l.ListElements
        | Array a -> Array.toList a.ArrElements
        | Composite c -> LunTrie.toValueList (LunTrie.map (fun _ mem -> mem.MemExpr) c.CompMembers)
        | _ -> []
    let listFolder = fun state expr -> foldProceduralExpr folder state expr
    let listFolded = List.fold listFolder state children
    folder state (expr :: listFolded)

問題は、コードが機能しないことです。これは、最後の行でエラーが発生the construct causes code to be less generic than indicated by the type annotations. The type variable 's has been constrained to be type 'Expr list'するため、既知です。listFoldedこれは、の定義foldProceduralExprがほぼ間違いなく間違っているためです。

今、私はコードとその結果としてタイプエラーを修正したいのですが、どうすればいいのかわかりません。私が欠けているのは、非リストまたは再帰的なデータ構造のフォールドがどのように機能するかを理解していることだと思います。私は最近、トライのフォールドをOCamlからF＃に変換しましたが、そのフォールドがどのように機能するかを理解するのに多くの問題がありました。

質問1：平手打ちを理解できるこのコードの目に見える修正はありますか？

質問2：これらのタイプの折り目を書く方法を理解するために必要な背景を得るためのリソースはありますか？

さらに詳しい情報が必要な場合はお知らせください。DUは大きすぎて複雑すぎて質問を明確にできないため、ここには含めませんでした。うまくいけば、それはあなたの典型的なLispスタイルのASTデータ構造です。

フォローアップの質問：それが機能したら、その折り目で地図を書きたいと思います。それは典型的な地図のように見えるでしょうか、それともそれを理解するために余分な頭脳の力が必要でしょうか？

編集：トーマスの助けに関して、私は最後の3行を-に変えました

let exprs = expr :: children
let listFolder = fun state expr -> foldProceduralExpr folder state expr
let listFolded = List.fold listFolder state exprs
folder listFolded exprs

これがまだ理にかなっていることを願っています。

編集：これが私の最終的な解決策です。それは子供を得るよりも一般化されています-

let rec foldRdu (getChildren : 't -> 't list) (folder : 's -> 't -> 't list -> 's) (state : 's) (parent : 't) : 's =
    let children = getChildren parent
    let listFolder = fun state child -> foldRdu getChildren folder state child
    let listFolded = List.fold listFolder state children
    folder listFolded parent children

ExprリストとExprリストをフォールド値として使用する理由は、後で使用するために親子関係の構造を保持したいからです。これは、私が思うに、非常にドメイン固有のフォールドです。

4

2 に答える 2

4

最初の質問は、どのようなフォールドを実装したいのかということです。ツリーのような構造にはいくつかのオプションがあります。n-aryツリー（つまり、任意の数の子）があるとすると、次のことができます。

  1. 折り畳み関数Exprは、葉のノードにのみ適用してください
  2. リーフにフォールディング関数を適用してから、すべての内部ノードに適用します（再帰呼び出し後）
  3. ツリーを処理している間、次にリーフにフォールディング関数を内部ノードに適用します

あなたの例では、あなたのフォルダ関数が取るので、Expr list私には少し混乱します-子のリストではなく現在のものを与えることができると思いますがExpr、子でそれを呼び出すこともオプションです。

最初に再帰呼び出しを行ってから、現在の式でフォルダーを呼び出しているので、オプション2を実装したいと思います。フォールディングの最初の2行を理解できます。

// This defines a function that recursively folds the a given 
// expression and produces a new state of type 's
let listFolder = fun state expr -> foldProceduralExpr folder state expr 
// Here, you fold all children recursively starting with 'state' and 
// obtaining a result 'listFolded' of type 's
let listFolded = List.fold listFolder state children

ただし、最後の行はおそらく間違っています。

// From the previous line, 'listFolded' is of type 's, but 
// here you use it as if it was a list:
folder state (expr :: listFolded)

listFoldedに渡される状態として、おそらく使用したいと思いますfolder。フォルダは式のリストを受け取るchildrenので、2番目の引数として指定できます（またはfolder、1つだけを取得してからExpr、それだけを指定するように変更できますexpr。これは、IMHOの方が理にかなっています）。とにかく、これで動作するはずなので、実行して何が起こっているかを確認できます。

folder listFolded children
于 2012-09-05T19:27:23.417 に答える
2

私はかつて、大規模な識別された共用体とその変換を含むコードを維持するための実用的なアプローチについての記事を書きました。

http://t0yv0.blogspot.com/2011/09/transforming-large-unions-in-f.html

実際には、フォールドはあまりにも多くを想定していることがわかります。フォールドで表現できない変換が頻繁にあります。また、変換がどのように行われるか（ボトムアップまたはトップダウン）、およびどのノードがスキップまたは特別に処理されるかを制御する必要があります。この記事では、これを簡単なtransform関数で行う方法を示しています。また、からほんの数行でフォールドを導き出しますtransform。

問題を解決する方法に直接答えることはできませんが、そのようなコードを構造化する別の方法に光を当てる可能性があります。

于 2012-09-09T12:22:24.040 に答える