F# 中编写函数时堆栈溢出

Question

基本上，我的问题是我正在尝试组合大量函数，因此我正在创建一个深层次的组合函数链。这是我的代码：

let rec fn (f : (State -> State option) -> (State -> State option)) (n : int) acc =
    match n with 
    | 0 -> acc 
    | _ -> fn f (n - 1) (f << acc)

然后我打电话给它：

let foo = fn id 10000000 id bottom

所以，它会进行一千万次迭代，并且应该结合很多功能。 我确信

fn

是尾递归的（至少，我希望如此），但是执行会出现堆栈溢出，我不明白为什么。

此时，问题应该是深度结合。所以我希望得到建议、提示，一切。

Answer 1

我认为如果你将

foo

分成两个步骤，问题就会变得更加清晰：

let foo = fn id 10000000 id   // create huge chain of functions (this works)
let bar = foo bottom          // execute huge chain of functions (this goes boom!)

所以

fn

确实是尾递归并且它成功执行，创建了一个链式调用的巨型函数（我称之为

bar

）。但是，

bar

不是尾递归，因此当您使用

bottom

调用它时，它会耗尽堆栈。

换句话说，

bar

就是

id << id << id << ... id << id

，是一个调用时会溢出栈的函数。