f# - 将大量函数组合在一起时堆栈溢出

Question

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

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正在执行，没有办法解决。

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

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

至于你做的例子 - 我认为它失败了，因为你在 FSI 或类似的东西中运行它。我刚才已经验证过了:

如果你正常编译它，它工作正常。

如果关闭优化，它会因堆栈溢出而失败。

如果替换 id使用一些非尾递归函数(例如 fun x -> x+1 )，它也会失败。