我怎樣才能得到這個函數是尾遞歸？

我是still試圖實現2-3根手指樹，我取得了很好的進展（repository）。在做一些基準測試時，我發現當樹很大時，我的基本toList結果爲StackOverflowException。起初，我看到一個簡單的修復，並使其成爲尾遞歸。我怎樣才能得到這個函數是尾遞歸？

不幸的是，事實證明，toList是不是罪魁禍首，但viewr是：

/// Return both the right-most element and the remaining tree (lazily). 
let rec viewr<'a> : FingerTree<'a> -> View<'a> = function 
    | Empty -> Nil 
    | Single x -> View(x, lazyval Empty) 
    | Deep(prefix, deeper, One x) -> 
     let rest = lazy (
      match viewr deeper.Value with 
      | Nil -> 
       prefix |> Digit.promote 
      | View (node, lazyRest) -> 
       let suffix = node |> Node.toList |> Digit.ofList 
       Deep(prefix, lazyRest, suffix) 
     ) 
     View(x, rest) 
    | Deep(prefix, deeper, Digit.SplitLast(shorter, x)) -> 
     View(x, lazy Deep(prefix, deeper, shorter)) 
    | _ -> failwith Messages.patternMatchImpossible

尋找唯一的遞歸調用，很明顯，這是不是尾遞歸。不知何故，我希望這個問題不存在，因爲這個電話是在一個Lazy包裹，恕我直言，類似於延續。

我聽過並讀過延續，但到目前爲止從未（必須）使用（d）他們。我想我真的需要。我一直在盯着代碼很長一段時間，把函數參數放在這裏和那裏，叫他們其他的地方... 我完全失去了！

這怎麼辦？

更新：調用代碼看起來是這樣的：

/// Convert a tree to a list (left to right). 
let toList tree = 
    let rec toList acc tree = 
     match viewr tree with 
     | Nil -> acc 
     | View(head, Lazy tail) -> tail |> toList (head::acc) 
    toList [] tree

更新2：導致崩潰是這個代碼。

let tree = seq {1..200000} |> ConcatDeque.ofSeq 
let back = tree |> ConcatDeque.toList

樹得到建好，我檢查，它只有12層深。第2行的呼叫觸發了溢出。

更新3：kvb是正確的，那pipe issue我跑進前有事情做與此有關。重新測試調試/發佈的交叉產品以及使用/不使用管道時，它的工作情況除一種情況外：管道運營商的調試模式崩潰。 32位和64位的行爲是一樣的。

我很確定發佈問題時我運行的是發佈模式，但今天它正在運行。也許還有一些其他因素...對此抱歉。

雖然碰撞是解決了，我要離開這個問題打開了理論上的意義。畢竟，我們在這裏學習，不是嗎？

所以讓我適應的問題：
從看代碼，viewr絕對不是尾遞歸。爲什麼它不會總是爆炸，以及如何使用延續重寫它？

來源

2016-11-09 primfaktor

這有幫助嗎？ http://blog.ploeh.dk/2015/12/22/tail-recurse –

懶惰的確意味着根本沒有遞歸調用 - 問題在於這個函數和它的調用者之間的交互。你還可以提供調用代碼嗎？ – kvb

@kvb：完成。如果您需要查看更多信息，則整個回購在開始時會鏈接。 – primfaktor

調用viewr決不會導致立即遞歸調用viewr（遞歸調用是由lazy保護，不被強迫的調用viewr的剩餘部分內），所以沒有必要讓它尾遞歸防止無限制地增長。也就是說，對viewr的調用會創建一個新的堆棧幀，然後在viewr的工作完成時立即彈出;調用者然後可以強制延遲值，從而產生一個嵌套viewr調用的新堆棧幀，然後再次立即彈出，等等，因此重複此過程不會導致堆棧溢出。

來源

2016-11-10 15:50:26 kvb

我怎樣才能得到這個函數是尾遞歸？

回答

相關問題