haskell中循环列表和无限列表之间有什么区别？

Question

引用@dfeuer对这个问题的回答:在Haskell中构造循环列表的最便宜的方法,它说使用循环列表"击败"垃圾收集器,因为它必须保留你从循环列表中分配的所有内容,直到你删除引用列表中的任何缺点单元格.

显然在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单元中只有其后继者是可达的.

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

还要注意,这种区别可以概括为实现该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也用作应用程序的参数.即,thunk,当被强制时,将以thunk本身作为其参数调用目标代码,并用结果替换thunk的内容.ff

Answer 2

循环列表和无限列表在操作上是不同的,但不是语义上的.

循环列表实际上是内存中的一个循环 - 想象一个单个链表,其中指针跟随一个循环 - 因此占用了恒定的空间.因为可以从任何其他单元格到达列表中的每个单元格,所以保持任何一个单元格将导致整个列表被保留.

当您评估更多内容时,无限列表将占用越来越多的空间.如果不再需要,早期的元素将被垃圾收集,因此处理它的程序仍然可以在恒定的空间中运行,尽管垃圾收集开销会更高.如果需要列表中的早期元素,例如因为您保持对列表头部的引用,那么列表将在您评估时消耗线性空间,并最终耗尽可用内存.

造成这种差异的原因在于,如果没有优化,像GHC这样的典型Haskell实现将为一个值分配一次内存,就像xs'在第二个定义中一样cycle,但是会像cycle xs在第一个定义中一样为函数调用重复分配内存.

原则上,优化可能会将一个定义转换为另一个定义,但由于性能特征的差别很大,因此在实践中不太可能发生这种情况,因为编译器通常会非常保守地使程序更糟糕.在某些情况下,由于已经提到的垃圾收集属性,循环变体会更糟.