.net - F# Seq 的一个实现问题

Question

我最近正在研究 F# 源代码。

在 Seq.fs 中:

// Binding. 
//
// We use a type defintion to apply a local dynamic optimization. 
// We automatically right-associate binding, i.e. push the continuations to the right.
// That is, bindG (bindG G1 cont1) cont2 --> bindG G1 (cont1 o cont2)
// This makes constructs such as the following linear rather than quadratic:
//
//  let rec rwalk n = { if n > 0 then 
//                         yield! rwalk (n-1)
//                         yield n }

看到上面的代码后，我测试了两个代码:

let rec rwalk n = seq { if n > 0 then 
                         yield n
                         yield! rwalk (n-1)
                      }

和

let rec rwalk n = seq { if n > 0 then 
                         yield! rwalk (n-1)
                         yield n 
                      }

我发现第一个非常快，而第二个非常慢。如果 n = 10000，在我的机器上生成这个序列需要 3 秒，因此是二次时间。

二次时间是合理的，例如
seq { yield! {1; 2; ...; n-1}; yield n }翻译成

Seq.append {1; 2; ...; n-1} {n}

我猜这个附加操作应该需要线性时间。而在第一个代码中，追加操作是这样的: seq { yield n; yield! {n-1; n-2; ...; 1} } ，这花费恒定的时间。

代码中的注释说它是 linear (也许这个线性不是线性时间)。也许这个 linear涉及使用序列的自定义实现而不是 Moand/F# 计算表达式(如 F# 规范中所述，但规范没有提及这样做的原因......)。

谁能澄清这里的模糊性？非常感谢!

(p.s.因为这是一个语言设计和优化问题，所以我还附上了Haskell标签，看看那里的人有没有见解。)

Answer 1

当yield!出现在 非尾随仓 ，它本质上与以下内容相同:

for v in <expr> do yield v

这个问题(以及为什么是二次方的原因)是对于递归调用，这会创建一个带有嵌套 for 的迭代器链。循环。您需要遍历 <expr> 生成的整个序列对于每个元素，所以如果迭代是线性的，你会得到一个二次时间(因为线性迭代发生在每个元素上)。

假设 rwalk函数生成 [ 9; 2; 3; 7 ] .在第一次迭代中，递归生成的序列有 4 个元素，因此您将迭代 4 个元素并添加 1。在递归调用中，您将迭代 3 个元素并添加 1，等等。使用图表，您可以看看它是如何二次的:

x
x x 
x x x
x x x x

此外，每个递归调用都会创建一个新的对象实例 ( IEnumerator)，因此也会产生一些内存成本(尽管只是线性的)。

在 尾随位置 ，F# 编译器/库进行优化。它“替换”了当前的 IEnumerable与递归调用返回的那个，所以它不需要迭代它来生成所有元素 - 它只是被返回(这也消除了内存成本)。

有关的。 在 C# 语言设计中讨论了相同的问题，并且有一个 interesting paper about it (他们的 yield! 的名称是 yield foreach )。