如何让这个函数是尾递归的？

Question

我仍在尝试实现2-3个手指树，并取得了良好的进展（存储库）。在做一些基准测试时，我发现当树非常大时，我非常基本的toList会导致堆栈溢出异常。起初，我看到了一个简单的修复方法，并将其设置为尾部递归。

不幸的是，事实证明，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

寻找唯一的递归调用很明显，这不是尾部递归。不知何故，我希望这个问题不会存在，因为这个调用被包装在一个类似于连续的延迟中。

我听说并读过连续体，但到目前为止，我从未使用过连续体。我想我真的需要。我已经盯着代码看了很长一段时间，到处放函数参数，在其他地方调用它们……我完全迷路了！

如何做到这一点？

更新：调用代码如下所示：

/// 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是对的，我之前遇到的管道问题与此有关。重新测试调试/发布和有/无管道的交叉乘积，它在所有情况下都有效，只有一种情况除外：管道操作员的调试模式崩溃。32位与64位的行为相同。

我很确定我在发布问题时运行的是发布模式，但今天它起作用了。也许还有其他因素…抱歉。

虽然崩溃已经解决了，但出于理论兴趣，我将这个问题留给大家。毕竟，我们是来学习的，不是吗？

因此，让我修改这个问题：
从代码来看，viewr肯定不是尾部递归的。为什么它不总是爆炸，如何用连续体重写它？




Answer 1

调用viewr从来不会导致立即递归调用viewr（递归调用受lazy保护，并且在调用viewr的其余部分中不会强制），因此不需要使其尾部递归以防止堆栈无约束增长。也就是说，对viewr的调用创建了一个新的堆栈帧，当viewr的工作完成时，该堆栈帧立即弹出；然后，调用方可以强制延迟值，为嵌套的viewr调用生成新的堆栈帧，然后立即再次弹出，等等，因此重复此过程不会导致堆栈溢出。