为什么重复在Prelude中定义？

Question

重复定义如下:

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

是否有任何理由不使用以下内容？

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

(很显然,许多Prelude函数有许多等价的定义,但我后面的描述感觉更加明显.我想知道它是否存在性能或样式原因.)

Answer 1

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

代码的第一个版本使用显式共享; 它基本上看起来像内存中的单元素循环链表(xs代码中的列表节点具有xas值,其尾部指向同一个列表节点).当您评估列表中越来越多的元素时,它将重复占用同一个节点.

相反,第二个版本创建了一个列表,该列表在评估时实际在内存中增长,因为不同的调用repeat x总是被重新计算(而不是memoized).在生成的列表的末尾总会有另一个未评估的thunk.