functional-programming - Okasaki 的纯函数式数据结构中的 Streams 章节

Question

在他关于流的介绍性章节中，Okasaki 提供了 2 种drop关于流的实现。

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

Answer 1

如果我不得不猜测，我会说这一定是因为第二个版本没有像第一个版本那样利用懒惰，但似乎不管上下文如何，如果你强制任何一点结果，然后你强制整个计算。例如，假设我想做：

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

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

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

take另一方面，

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

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