我怎样才能得到这个函数是尾递归？

我是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

我怎样才能得到这个函数是尾递归？

回答

相关问题