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#规范中所述,但是规范没有提到这样做的原因......).

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

(ps因为这是一个语言设计和优化问题,我还附上了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

此外,每个递归调用都会创建一个新的object(IEnumerator)实例,因此也会有一些内存成本(尽管只是线性的).

在尾部调用位置,F#compiler/librar进行优化.它将当前IEnumerable与递归调用返回的当前"替换" ,因此它不需要迭代它以生成所有元素 - 它只是返回(这也消除了内存成本).

有关.在C#lanaugage设计中已经讨论过同样的问题,并且有一篇有趣的论文(他们的名字yield!是yield foreach).