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

这是展平二叉查找树的一种方法。它的问题是当它构建的大函数最终应用于[]时，堆栈溢出。我想知道是否有合理的方法修复这段代码片段而不完全改变它的工作方式。例如，如果构建一个自定义作曲家来构建一个函数树，然后使用一个显式堆栈来评估它们（因为问题已经是将一棵树展平了），那么这将无济于事。将多个函数组合在一起时溢出堆栈

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

来源

2017-09-15 jeremiah

你正在编译优化吗？什么是你的运行时间？操作系统？ –

我没有使用优化功能，因为我不想要一个有时能够运行，有时不能运行的解决方案。然而，我正在生成尾巴呼叫。我在Windows下使用.net。我知道在Mono下，tail-calls没有正确实现，但这不是问题。 – jeremiah

你的树压扁功能不是尾递归。

函数的组成不是尾递归。这是很容易通过展开你的三联组成看：

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），它也会失败。

来源

2017-09-16 00:28:51

非常感谢。我认为这个人为的例子与非平凡的例子的原因完全相同，只是优化器在某些情况下可以有所作为。答案的关键部分是“没有办法解决这个问题”。我认为这可能是正确的，因为使用尾递归通常是一种痛苦，尽管我们都意味着没有简单的方法。除了最终解决方案不如替代方案之外，没有什么可以阻止使用嵌套延续。如果没有人提供一些令人惊讶的见解，我会接受你的答案。再次感谢 – jeremiah

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

回答

相关问题