为什么这个F#表达式堆栈溢出

Question

let ints = [1..40000]

// create [{1};{2};.....{40000}]
let a1 = ints |> List.map Seq.singleton 

// tail recursively append all the inner list
let a2 = a1 |> List.fold Seq.append Seq.empty

// tail recursively loop through them
let a3 = a2 |> Seq.forall (fun x -> true) // stack overflow...why?

我问的理由是担心我会有递归附加的代码,我需要确保它不会爆炸....所以我运行这个例子以便确定将要发生的事情

在调试和作为应用程序运行.

Answer 1

首先要注意的是，导致SO异常的函数是：

let a2 = a1 |> List.fold Seq.append Seq.empty

但在评估下一行之前你不会看到 SO，因为序列是惰性评估的。

由于您使用的是 Seq.append，因此添加到序列中的每个新项目都会创建一个包含前一个序列的新序列。您可以直接构造类似的序列，如下所示：

> seq {
    yield! seq { 
                   yield! seq { 
                                  yield 1
                              }
                   yield 2
               }
    yield 3
}

val it : seq<int> = seq [1; 2; 3]

请注意，要到达第一项 (1)，您必须进入序列的深度 3。在您的情况下，深度为 40000。序列不是尾递归的，因此序列的每个级别在迭代时最终都会成为堆栈帧。