f# - 为什么这个 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。序列不是尾递归的，因此序列的每个级别在迭代时最终都作为堆栈帧。