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

Question

引用@dfeuer对此问题的回答:Least expensive way to construct cyclic list in Haskell ，它说使用循环列表会“击败”垃圾收集器，因为它必须保留您从分配的循环列表中消耗的所有内容，直到您删除对列表中任何 cons 单元格的引用为止。

显然，在 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 单元，那么垃圾收集器也必须在分配之前保留所有内容？

Answer 1

差异完全在于内存表示。从语言语义的角度来看，它们是无法区分的 - 您无法编写可以区分它们的函数，因此您的两个版本的 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 编译代码的方式意味着为 result 创建的 thunk 既用作 f 应用程序的结果和参数。即，当强制时，thunk 将以 thunk 本身作为参数调用 f 的目标代码，并用结果替换 thunk 的内容。