haskell - 为什么在 Prelude 中如此定义重复？

Question

这个问题已经有答案了:

Why recursive `let` make space effcient? (3 个回答)

已关闭 10 年前。

重复is defined如下:

repeat :: a -> [a]
repeat x = xs where xs = x:xs

有什么原因不使用以下内容吗？

repeat :: a -> [a]
repeat x = x : repeat x

(显然，许多 Prelude 函数有许多等效的定义，但我后面的描述感觉更明显。我想知道是否存在性能或风格方面的原因。)

Answer 1

这是出于性能和空间复杂性的原因。

第一个版本的代码使用显式共享；它基本上看起来像内存中的单元素循环链表(代码中的xs是一个以x为值的列表节点，它的尾部指向完全相同的列表节点)。当您评估列表中越来越多的元素时，它只会重复使用相同的节点。

相比之下，第二个版本创建的列表在计算时实际上在内存中增长，因为 repeat x 的不同调用始终会重新计算(而不是内存)。在生成的列表末尾总会有另一个未评估的重击。