将许多函数组合在一起时堆栈溢出

Question

这是一种展平二叉搜索树的方法。它的问题是当它构建的大函数最终应用到 [] 时堆栈溢出。我想知道是否有一种合理的方法可以在不完全改变其工作方式的情况下修复此代码片段。例如，构建一个构建函数树的自定义作曲器，然后使用显式堆栈对其求值（因为问题已经是压平树），这无助于取得进展。

let flatten_k t =

    let rec f t (k:(list<'a>->list<'a>)->list<'a>) =
        match t with
        | Leaf -> 
            k (fun xs -> xs)

        | Bin (l,x,r) ->
            f l (fun fl -> f r (fun fr -> k (fl << (fun xs -> x::xs) << fr)))

    f t (fun g -> g [])

考虑一个简化的实例可能会更好，尽管可能更难以令人信服地证明对其进行修复（因为它几乎什么都没有，尽管至少它表明函数组合确实溢出了堆栈):

let test_composition () =
   let mutable f = id
   for i=0 to 1000000 do
       f <- id << f // >> works fine for me
   printf "Functions return %d" (f 123)

同样，这个问题不是关于如何压扁一棵树的。我可以按如下方式或以任何数量的纯命令方式轻松地做到这一点。我想知道基于累积大函数的方法是否可以解决这个特定问题。非常感谢。

 let flatten t =

    let rec f t acc cont =
        match t with
        | Leaf ->
            cont acc

        | Bin (l, x, r) ->
            f r acc (fun rs -> f l (x::rs) cont)

    f t [] id

Answer 1

你的树展平函数不是尾递归的。

函数的组合不是尾递归。展开你的三重构图很容易看出这一点：

original:              fl << cons << fr
unfold compositions:   fun a -> fl (cons (fr a))
unfold nested calls:   fun a ->
                          let x = fr a
                          let y = cons x
                          fl y

如您所见，此函数首先调用 fr，然后对其结果执行一些重要的操作。最后一次调用 fl 是尾递归的，但前两次不是。在执行 fr 和 cons 时，需要将 return 地址保存在堆栈中，没有办法解决这个问题。

这不是尾递归。尾递归通过将最后一次调用的结果向上传递给调用者来工作。将此结果作为参数传递给另一个函数 - 这是完全不同的事情。

至于如何修复它 - 如果您坚持使用函数组合，则无法解决。如果您不坚持 - 那么您已经有了解决方案。

就您设计的示例而言 - 我认为它失败了，因为您运行它在 FSI 或类似的地方。我刚才已经验证过了：

如果你正常编译，就没问题。
如果关闭优化，它将因堆栈溢出而失败。
如果您将 id 替换为某些非尾递归函数（例如 fun x -> x+1），它也会失败。

将许多函数组合在一起时堆栈溢出

Overflowing stack when composing lots of functions together

f#

stack-overflow

tail-recursion

continuations