scala - 组合函数导致 StackOverflow

Question

Functional Programming in Scala列出了以下示例，说明组合函数如何导致 StackOverflowError。

scala> val f = (x: Int) => x
f: Int => Int = <function1>

scala> val g = List.fill(100000)(f).foldLeft(f)(_ compose _)
g: Int => Int = <function1>

scala> g(42)
java.lang.StackOverflowError

正如书中所解释的，g 是一个复合函数，它有 100,000 个函数，每个函数调用下一个。

既然foldLeft是尾递归的，为什么会出现这个StackOverflowError呢？如果有的话，尾递归和 StackOverflow 有什么关系？

当(展开时)foldLeft 的第二个参数 (B, A) => B，((acc, elem) => acc。 compose(elem))，不是每个折叠步骤都只会组合 2 个函数吗？

Answer 1

Since foldLeft is tail-recursive, why does this StackOverflowError occur? How, if at all, are tail-recursion and StackOverflow's related?

When (as it's expanded) the second argument (B, A) => B of foldLeft, ((acc, elem) => acc.compose(elem)), doesn't each fold step result in composing only 2 functions?

请注意折叠本身(即 val g = ... 行)不会溢出堆栈。但是，g 最终被有效地定义为 f(f(...(x))) 因此您需要 100000 个堆栈帧来计算 g(42 ) 这显然会溢出。