haskell - Haskell 可以评估列表中的随机索引而不是垃圾收集吗？

Question

据我了解，Haskell 仅在某些内容超出范围时进行垃圾收集，因此顶级绑定(bind)只会被评估一次，并且永远不会超出范围。因此，如果我在 GHCI 中运行此代码，前 50 个元素将被评估并保存。

let xs = map f [0..]
take 50 xs

我的问题是当我执行以下代码片段时会发生什么:xs !! 99 。垃圾收集器节省了什么？是吗

1. 保留索引 0 - 49 的结果，thunk 保留索引 50 - 98 的结果，thunk 保留索引 99 的结果，thunk 保留索引 100+ 的结果
2. 保留索引 0 - 49 的结果，对索引 50+ 进行 thunk
3. 保留索引 0 - 99 的结果，对索引 100+ 进行 thunk

Answer 1

Haskell 列表是由 (:)(“cons”)单元格组成并以 [](“nil”)值终止的链接列表。我会像这样绘制这样的单元格

 [x] -> (tail - remainder of list)
  |
  v
(head - a value)

因此，在考虑评估内容时，需要考虑两点。第一个是spine，即cons单元的结构，第二个是列表包含的值。让我们分别使用 2 和 4，而不是 50 和 99。

ghci> take 2 xs
[0,1]

打印此列表会强制计算前两个 cons 单元以及其中的值。所以你的列表看起来像这样:

[x] -> [x] -> (thunk)
 |      |
 v      v
 0      1

现在，当我们

ghci> xs !! 4
3

我们没有要求第二个或第三个值，但我们需要评估这些 cons 单元格以获得第四个元素。因此，我们将脊柱一直强制到第 4 个元素，但我们只评估了第 4 个值，因此列表现在如下所示:

[x] -> [x] -> [x] -> [x] -> [x] -> (thunk)
 |      |      |      |      |
 v      v      v      v      v
 0      1   (thunk) (thunk)  4

这张图片中的任何内容都不会被垃圾收集。然而，有时这些重击可能会占用大量空间或引用较大的内容，将它们评估为简单值将允许释放这些资源。请参阅this answer对这些微妙之处进行小讨论。