haskell - 为什么前奏曲中的“迭代”不打结？

Question

为什么不iterate定义为

iterate :: (a -> a) -> a -> [a]
iterate f x = xs where xs = x : map f xs

在前奏曲中？

Answer 1

像这样打结似乎不会增加分享。

对比：

cycle xs = let x = xs ++ x in x

在这里打个结有在内存中创建循环链表的效果。 x是它自己的尾巴。有真正的收获。

您建议的实施不会增加幼稚实施的共享。首先它没有办法这样做 -iterate (+1) 0无论如何都没有共享结构。

Answer 2

在您的版本中没有打结，它只是在生成的列表上保留一个指针，以便在那里找到下一次迭代的输入值。这意味着在生成下一个单元格之前，每个列表单元格都不能被 gc-ed。

相比之下，Prelude 的版本为此使用iterate' 调用框架，并且由于它只需要一次，一个好的编译器可以重用该框架并改变其中的值，以实现更优化的整体操作（并且列表的单元格彼此独立在这种情况下）。

Answer 3

为了清楚起见，我在下面包含的 Prelude 定义没有调用 map 所需的开销。

iterate f x =  x : iterate f (f x)

只是为了好玩，我做了一个小程序来测试你iterate和前奏曲的对比——只是为了减少到正常的形式take 100000000 $ iterate (+1) 0（这是一个Ints 列表）。我只进行了 5 次测试，但您的版本在 Prelude为7.833(max 7.873min ) 时运行了(max min )。我怀疑时差是被调用的开销。7.6677.5197.5917.477map

第二个原因很简单：可读性。