在组合大量功能时溢出堆栈

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正在执行,周围没有办法.

这不是尾递归.尾递归的工作原理是将最后一次调用的结果传递给调用者.将此结果传递给另一个函数作为参数 - 这是完全不同的事情.

至于如何解决它 - 如果你坚持使用功能组合你就不能.如果你不坚持 - 那么你已经有了解决方案.

至于你人为的例子 - 我认为它失败了,因为你在FSI或类似的东西中运行它.我刚刚验证了它:

• 如果你正常编译它,它工作正常.
• 如果关闭优化,则会因堆栈溢出而失败.
• 如果id用一些非尾递归函数替换(例如fun x -> x+1),它也会失败.