8

マルチウェイ ツリーに適用するために、Brian's Fold をバイナリ ツリー ( http://lorgonblog.wordpress.com/2008/04/06/catamorphisms-part-two/ ) に適用しようとしています。

Brian のブログからの要約:

データ構造：

type Tree<'a> =  
    | Node of (*data*)'a * (*left*)Tree<'a> * (*right*)Tree<'a>  
    | Leaf 

let tree7 = Node(4, Node(2, Node(1, Leaf, Leaf), Node(3, Leaf, Leaf)),  
                    Node(6, Node(5, Leaf, Leaf), Node(7, Leaf, Leaf)))

二分木折り関数

let FoldTree nodeF leafV tree =   
    let rec Loop t cont =   
        match t with   
        | Node(x,left,right) -> Loop left  (fun lacc ->    
                                Loop right (fun racc ->   
                                cont (nodeF x lacc racc)))   
        | Leaf -> cont leafV   
    Loop tree (fun x -> x)

例

let SumNodes = FoldTree (fun x l r -> x + l + r) 0 tree7
let Tree6to0 = FoldTree (fun x l r -> Node((if x=6 then 0 else x), l, r)) Leaf tree7

マルチウェイ ツリー バージョン [(完全に) 動作していません] :

データ構造

type MultiTree = | MNode of int * list<MultiTree>

let Mtree7 = MNode(4, [MNode(2, [MNode(1,[]); MNode(3, [])]);  
                    MNode(6, [MNode(5, []); MNode(7, [])])])

折り機能

let MFoldTree nodeF leafV tree = 
    let rec Loop  tree cont =   
        match tree with   
        | MNode(x,sub)::tail -> Loop (sub@tail) (fun acc -> cont(nodeF x acc))
        | [] -> cont leafV
    Loop  [tree] (fun x -> x)

例 1 28 を返します - 動作しているようです

let MSumNodes = MFoldTree (fun x acc -> x + acc) 0 Mtree7

例 2

実行されません

let MTree6to0 = MFoldTree (fun x acc -> MNode((if x=6 then 0 else x), [acc])) Mtree7

最初はどこかにMFoldTree必要だと思っていましたが、代わりにオペレーターと連携するようになりました。map.something@

2 番目の例に関するヘルプや、MFoldTree関数で行ったことの修正は素晴らしいことです。

乾杯

デュシオド

4

2 に答える 2

9

秘訣は、フォールドする追加の関数を 1 つ渡す必要があることです。

Brian のバージョンでは、fold 関数nodeFは、ノード内の値と、左右のサブツリーから生成された 2 つの値を使用して呼び出されるだけです。

これは、多方向ツリーには十分ではありません。ここではnodeF、ノードの値と、サブツリーのすべての値を集計することによって生成された結果で呼び出される関数が必要です。combineFただし、ノードの複数のサブツリーから生成された値を組み合わせる関数も必要です。

折り畳み関数は良い出発点です-プロセスへの再帰呼び出しをもう1つ追加するだけですtail:

let MFoldTree nodeF combineF leafV tree = 
    let rec Loop trees cont =   
        match trees with   
        | MNode(x,sub)::tail -> 
            // First, process the sub-trees of the current node and get 
            // a single value called 'accSub' representing (aggregated)
            // folding of the sub-trees.
            Loop sub (fun accSub -> 
              // Now we can call 'nodeF' on the current value & folded sub-tree
              let resNode = nodeF x accSub
              // But now we also need to fold all remaining trees that were
              // passed to us in the parameter 'trees'..
              Loop tail (fun accTail ->
                // This produces a value 'accTail' and now we need to combine the
                // result from the tail with the one for the first node 
                // (which is where we need 'combineF')
                cont(combineF resNode accTail) ))
        | [] -> cont leafV
    Loop  [tree] (fun x -> x)

+両方の関数に演算子を使用するだけなので、合計は簡単です。

let MSumNodes = MFoldTree (+) (+) 0 Mtree7

ツリーのフィルタリングはよりトリッキーです。このnodeF関数は、ノード内の要素と子ノードのリスト(集約の結果) を取得し、単一のノードを生成します。このcombineF関数は、最初のノード (MultiTree値) から結果を取得し、残りのノードから生成された子のリストを取得します。空のツリーから生成される初期値は空のリストです:

let MTree6to0 = 
  MFoldTree (fun x children -> MNode((if x=6 then 0 else x), children)) 
            (fun head tail -> head::tail) [] Mtree7
于 2013-06-01T18:45:43.700 に答える
5

別の解決策は

let rec mfold f a (MNode(x,s)) = f (List.fold (fun a t -> mfold f a t) a s) x

実際、tree を直系の構造体として (折りたたむために) 扱うことができます。

使用事例

> mfold (+) 0 Mtree7;;
val it : int = 28

フィルターは通常の折りたたみと同じです (通常の折りたたみmfoldであるため):

> mfold (fun a x -> if x = 6 then a else x + a) 0 Mtree7;;
val it : int = 22

その関数はジェネリックである可能性があります（List.fold、Array.fold、...がジェネリックである可能性があるため）。

「しかし、2番目の意図は、たとえば値6を持っていたノードが値0になるように変更されたツリー全体を返すことです」

しかし、それはfold計算ではなく、map!

あなたは簡単に行うことができます（再び直系構造体として扱います）

let rec mmap f (MNode(x,s)) = MNode(f x, List.map (mmap f) s)

使用事例

> mmap (fun x -> if x=6 then 0 else x) Mtree7;;
val it : MultiTree =
  MNode
    (4,
     [MNode (2,[MNode (1,[]); MNode (3,[])]);
      MNode (0,[MNode (5,[]); MNode (7,[])])])

Seq繰り返しますが、可能なリスト コンテナー ( 、List、 、...)ごとに実行することをお勧めしますArray。これにより、ユーザーはコンテキストで最適な戦略を選択できます。

ノート：

  • 私は F# が初めてなので、間違っていたらすみません。
  • スタック サイズは問題ではありません。スタック レベルはツリーの深さと同じです。
于 2013-06-01T22:18:53.633 に答える