functional-programming - Okasaki 的 Purely Functional Data Structure 中的 Streams 章节

Question

在关于流的介绍性章节中，Okasaki 为 drop 提供了 2 个实现。在溪流上。

他明确提到第二个更有效(并且两者具有相同的语义)，但我似乎无法弄清楚为什么一个比另一个更有效。任何见解将不胜感激。

Answer 1

如果我不得不猜测，我会说这一定是因为第二个版本没有像第一个版本那样使用那么多的懒惰，但似乎无论上下文如何，如果您强行使用结果，然后你强制整个计算。例如，假设我想做:

val x = hd ($drop(10, l))

对于第一个版本，我们需要遍历所有 10 次迭代，然后才能得到 cons 单元格(假设流有 10 个以上的元素)。这与在第二个版本中执行的计算量相同，但是，我们不必处理在每次迭代中创建 thunk 并强制执行它的开销。

某些编译器(例如 GHC)实际上会执行称为严格性分析的操作，您可以在其中尝试确定是否要强制执行特定术语，如果是，则无需创建 thunk 并强制执行，更多详细信息可以找到 here

对于 take另一方面，

val x = hd ($take(10, l))

在完全惰性版本下，我们只需要评估take的第一次迭代。 , 直到我们可以停止，而第二个版本的模拟将评估所有 10 次迭代。在这个例子中，懒惰给你一些节省。