2

ツリーを取り、それが持っているすべてのパスをリストする再帰関数を実装しようとしています。

私の現在の実装は機能しません:

let rec pathToList tree acc =
    match tree with
    | Leaf -> acc
    | Node(leftTree, x, rightTree) ->
        let newPath = x::acc
        pathToList leftTree newPath :: (pathToList rightTree newPath)

...pathToList leftTree newPath要素ではなくリストを返すため、エラーになります。

これは、次のように set で修正できます。

let rec pathToList2 t acc =
    match t with
    | Leaf -> Set.singleton acc
    | Node(leftTree, x, rightTree) ->
        let newPath = x::acc
        Set.union (pathToList2 leftTree newPath) (pathToList2 rightTree newPath)

さて、セット（後で）ではなくリスト（前者）を使用してこれを解決することに少し行き詰まっています。末尾再帰を使用してそれを解決する方法について何か提案はありますか？

4

1 に答える 1

2

頼らずにこれを解決するに@は (最初のリストの長さが直線的であるため非効率的です)、2 つのアキュムレータが必要になります。ノード)、およびこれまでに見つけたすべてのパスに 1 つ (見つけたパスを追加できるようにするため)。

let rec pathToListRec tree pathToParent pathsFound =
    match tree with
    | Leaf -> pathsFound
    | Node (left, x, right) ->
        let pathToHere = x :: pathToParent

        // Add the paths to nodes in the right subtree
        let pathsFound' = pathToListRec right pathToHere pathsFound

        // Add the path to the current node
        let pathsFound'' = pathToHere :: pathsFound'

        // Add the paths to nodes in the left subtree, and return
        pathToListRec left pathToHere pathsFound''

let pathToList1 tree = pathToListRec tree [] []

末尾再帰に関する限り、上記の関数の 2 つの再帰呼び出しの 1 つが末尾位置にあることがわかります。ただし、テール位置ではないコールがまだあります。

ツリー処理関数の経験則は次のとおりです。完全に末尾再帰にするのは簡単ではありません。理由は簡単です: 単純に行うと、2 つの再帰 (左のサブツリーまたは右のサブツリーへのダウン) の少なくとも 1 つが必然的に末尾以外の位置になります。これを行う唯一の方法は、リストを使用してコール スタックをシミュレートすることです。これは、システム提供の呼び出しスタックの代わりにリストを使用していることを除けば、非末尾再帰バージョンと同じランタイムの複雑さを持つことを意味するため、おそらく遅くなるでしょう。

とにかく、それがどのように見えるかは次のとおりです。

let rec pathToListRec stack acc =
    match stack with
    | [] -> acc
    | (pathToParent, tree) :: restStack ->
        match tree with
        | Leaf -> pathToListRec restStack acc
        | Node (left, x, right) ->
            let pathToHere = x :: pathToParent

            // Push both subtrees to the stack
            let newStack = (pathToHere, left) :: (pathToHere, right) :: restStack

            // Add the current path to the result, and keep processing the stack
            pathToListRec newStack (pathToHere :: acc)

// The initial stack just contains the initial tree
let pathToList2 tree = pathToListRec [[], tree] []

コードはそれほど悪くはありませんが、スタックの仕事をするためにリストを使用しているため、非末尾再帰コードの 2 倍以上の時間がかかり、より多くの割り当てを行います!

> #time;;
--> Timing now on
> for i = 0 to 100000000 do ignore (pathToList1 t);;
Real: 00:00:09.002, CPU: 00:00:09.016, GC gen0: 3815, gen1: 1, gen2: 0
val it : unit = ()
> for i = 0 to 100000000 do ignore (pathToList2 t);;
Real: 00:00:21.882, CPU: 00:00:21.871, GC gen0: 12208, gen1: 3, gen2: 1
val it : unit = ()

結論：「末尾再帰にすれば速くなる！」というルール。いくつかの再帰呼び出しを行う必要がある場合は、コードをさらに遅くするようにコードを変更する必要があるため、極端には従わないでください。

于 2013-11-10T20:20:12.183 に答える