Haskell 中的循环列表和无限列表有什么区别？

参考@dfeuer对此问题的回答：在 Haskell 中构造循环列表的最便宜的方法 https://stackoverflow.com/questions/25374736/least-expensive-way-to-construct-cyclic-list-in-haskell，它说使用循环列表会“击败”垃圾收集器，因为它必须保留您从分配的循环列表中消耗的所有内容，直到您删除对列表中任何 cons 单元的引用为止。

显然，在 Haskell 中，循环列表和无限列表是两个不同的东西。这个博客（https://unspecified.wordpress.com/2010/03/30/a-doubly-linked-list-in-haskell/ https://unspecified.wordpress.com/2010/03/30/a-doubly-linked-list-in-haskell/）说如果你实施cycle如下：

cycle xs = xs ++ cycle xs

它是一个无限列表，而不是循环列表。要使其循环，您必须像这样实现它（如 Prelude 源代码中所示）：

cycle xs = xs' where xs' = xs ++ xs'

这两种实现方式到底有什么区别？为什么如果您在循环列表中的某处保留一个 cons 单元，那么垃圾收集器也必须在分配之前保留所有内容？

差异完全在于内存表示。从语言语义的角度来看，它们是无法区分的——你无法编写一个函数来区分它们，所以你的两个版本cycle被视为同一函数的两种实现（它们是参数到结果的完全相同的映射）。事实上，我不知道语言定义是否保证其中一个是循环的，另一个是无限的。

但无论如何，让我们展示一下 ASCII 艺术。循环列表：

   +----+----+                 +----+----+
   | x0 |   ----->   ...   --->| xn |    |
   +----+----+                 +----+-|--+
     ^                                |
     |                                |
     +--------------------------------+

无限列表：

   +----+----+
   | x0 |   ----->  thunk that produces infinite list
   +----+----+

循环列表的问题是，列表中的每个 cons 单元格都有一条通向所有其他单元格的路径和它本身。这意味着从垃圾收集器的角度来看，如果其中一个 cons cell 是可访问的，那么所有 cons cell 都是可访问的。另一方面，在普通的无限列表中，没有任何循环，因此从给定的 cons 单元只能到达其后继单元。

请注意，无限列表表示比循环表示更强大，因为循环表示仅适用于在一定数量的元素之后重复的列表。例如，所有素数的列表可以表示为无限列表，但不能表示为循环列表。

另请注意，这种区别可以概括为两种不同的实现方式fix功能：

fix, fix' :: (a -> a) -> a
fix  f = let result = f result in result
fix' f = f (fix' f)

-- Circular version of cycle:
cycle  xs = fix (xs++)

-- Infinite list version of cycle:
cycle' xs = fix' (xs++)

GHC 库适合我fix定义。 GHC 编译代码的方式意味着创建的 thunk 是为result用来both作为应用的结果和论证f。即，thunk 在被迫时将调用目标代码f以 thunk 本身作为参数，并用结果替换 thunk 的内容。