2

f# との戦い - 戦いは木の領域にあります - 特にノードの数を数えるためです。これは、私が最終的に F# でコーディングしたいプログラムが多方向ツリーに関係しているため、非常に興味深いものです。

99 f# シリーズの問題 61 では、バイナリ ツリーの葉の数を数えます。解決策（以下に示す）はノードをカウントしますが、私の問題は理解できません

  • 二重再帰がどのように機能するか 左ループ (fun lacc -> 右ループ..)

  • cont (branchF x lacc racc)つまり、cont は「abc」関数という印象でしたが、これは 2 つのパラメーターしか取りません...

  • loop t idID はユニット型です - これがどのように暗示されているのかわかりません

基本的にこれ、またはツリーを流れる順序を理解していません（デバッグとステップスルーは役に立ちません）。より簡単な例、先読みの推奨事項などがある場合は、それらを教えてください。

ご協力ありがとうございます。問題のソリューション コードは以下のとおりです。

乾杯

td

type 'a Tree = Empty | Branch of 'a * 'a Tree * 'a Tree

let foldTree branchF emptyV t =
    let rec loop t cont =
        match t with
        | Empty ->
            cont emptyV
        | Branch (x, left, right) ->
            loop left  (fun lacc -> 
                loop right (fun racc ->
                    cont (branchF x lacc racc)))
    loop t id

let counLeaves tree =
    foldTree (fun abc lc rc ->
        if lc + rc = 0 then 1
        else 1 + lc + rc) 0 tree

let Tree1 = Branch ('x', Branch ('x', Empty, Empty),Branch ('x', Empty, Branch ('x', Empty, Branch ('x', Empty, Empty))))


let result = counLeaves Tree1
4

1 に答える 1

7

名前が示すように、カスタムタイプfoldTreeに対して fold 関数を定義します。Tree

a を定義する単純な方法は次のようにfoldTreeなります。

let rec foldTreeNaive accFun init = function
    | Empty -> init
    | Branch (x, left, right) ->
        let lacc = foldTreeNaive accFun init left
        let racc = foldTreeNaive accFun init right
        accFun x lacc racc

この関数の問題は、アキュムレータ関数が呼び出される前にノードの再帰呼び出しが完了する必要があるため、折り畳まれているツリーが深い場合、非常に深い再帰呼び出しが行われる可能性があることです。たとえば、次の場合、スタック オーバーフロー例外が発生します。

let unbalanced = [1..100000] |> List.fold (fun t i -> Branch(i, t, Empty)) Empty
let nodeCount = foldTreeNaive (fun _ lc rc -> lc + rc + 1) 0 unbalanced

このようなスタック オーバーフローを回避する通常の方法は、関数の末尾を再帰的にすることですが、この場合、リストを折りたたむときに必要な呼び出しの代わりに 2 つの再帰呼び出しを行う必要があるため、これは不可能に思えます。

foldTreelocalloop関数を使用して定義されます。この関数は、継続渡しスタイルを使用して定義されているという点で興味深いものです。CPS では、各関数は追加の「継続」関数を受け取り、計算結果が渡され、次に何が起こるかを決定します。loopは末尾再帰的であるため、 のオーバーフローの問題を回避することに注意してくださいfoldTreeNaive。

loop関数のタイプは次のとおりです。

Tree<'a> -> ('b -> 'c) -> 'c

ここで、'a はツリー内のノードの型、'b はアキュムレータの型、'c は継続関数の結果です。

リーフ ノードの場合、関数に渡された空のアキュムレータ値が継続に渡されfoldTreeます。

この場合、空でないツリーをBranch折り畳むと、折り畳みの結果は左右のサブツリーの結果に依存します。これは再帰的に行われ、最初に左のサブツリーを折り畳み、次に右のサブツリーを折り畳みます。左のサブツリーに対する再帰呼び出しの場合loop、結果を受け取るために新しい継続を構築する必要があります。これは、

(fun lacc -> 
    loop right (fun racc ->
        cont (branchF x lacc racc))

関数。この継続が行うことは、右のサブツリーに対して再帰呼び出しを行い、さらに別の継続を渡してその折り畳みの結果を受け取ることです。その継続が呼び出されると、左右のサブツリーの結果が および で利用可能にlaccなりraccます。この時点で、現在のノードの値と左右のサブツリーの結果を使用して、ノードの累積関数を呼び出すことができます。この関数の結果は、 に渡された元の継続に渡されloopます。

関数は、次の行の関数によってloop呼び出されます。foldTree

loop t id

ここでidは、ツリーのルート ノードの折り畳みの結果を受け取る継続です。これは必要な値なので、id引数を変更せずにそのまま返します。

また、二分木の折り畳みに関するこの説明も役に立つかもしれません。

于 2013-02-27T09:34:51.387 に答える