F＃尾遞歸樹的路徑列表

Question

我想實現一個遞歸函數，它需要一棵樹並列出它所有的路徑。

我當前的實現不工作：

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不返回元素，但名單，因此錯誤。

這可能是固定設置，如：

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) 

現在，我被困在此使用列表（前）而不是設置（後下）解決了一下，就任何建議我怎麼會解決這個使用尾遞歸？

Answer 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 [] [] 

至於尾遞歸的話，你可以看到，在上面的函數兩個遞歸調用一個在尾部位置。然而，仍然有一個非尾部位置的呼叫。

下面是樹形處理函數的一條經驗法則：不能很容易使它們完全尾遞歸。原因很簡單：如果你天真地做到這一點，至少兩個遞歸中的一個（到左子樹或右子樹）必須處於非尾部位置。做到這一點的唯一方法是用列表模擬調用堆棧。這意味着，除非使用列表而不是系統提供的調用堆棧，否則將具有與非尾遞歸版本相同的運行時複雜性，因此它可能會變慢。

這裏是反正什麼樣子：

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] [] 

的代碼看起來並不太壞，但它需要兩倍只要非尾遞歸一個越來越做更多的撥款，因爲我們使用一個列表來完成堆棧的工作！

> #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 =() 

結論：「做它尾遞歸它會更快！當需要進行多次遞歸調用時，不應該遵循極端情況，因爲它要求以更慢的方式更改代碼。