haskell - 时髦的 haskell 惰性列表隐式递归

Question

在 Haskell 中，由于懒惰，您可以构建无限列表:

Prelude> let g = 4 : g
Prelude> g !! 0
4
Prelude> take 10 g
[4,4,4,4,4,4,4,4,4,4]

现在，当我尝试构建这样的列表时到底发生了什么？

Prelude> let f = f !! 10 : f
Prelude> f !! 0
Interrupted.
Prelude> take 10 f
[Interrupted.
Prelude>

Interrupted.等待几秒钟后我按下了 CTRL+C。似乎进入了无限循环，但为什么会这样呢？

---

对非 Haskeller 的解释:

:运算符是 prepend :

Prelude> 4 : [1, 2, 3]
[4,1,2,3]

这一行:

Prelude> let g = 4 : g

表示“让 g 成为通过在列表 4 中添加 g 构建的列表”。当您请求第一个元素时，将返回 4，因为它已经存在。当您请求第二个元素时，它会查找 4 之后的元素。该元素将是列表 g 的第一个元素。 ，我们刚刚计算出 (4)，所以 4被返回。下一个元素是 g 的第二个元素，我们刚刚计算过，等等...

!!只是索引到列表中，所以这意味着获取索引 0 处的元素来自g :

Prelude> g !! 0
4

但是当我这样做时:

Prelude> let f = f !! 10 : f

有些东西被破坏了，因为要计算 f 的第一个元素你需要第 11 个元素，但它还不存在？不过，我希望出现异常，而不是无限循环......

Answer 1

在这种情况下，一张图片可以讲述一千个单词。

首先，记住 cons((:) 列表构造函数)是如何工作的。它由两部分组成:一个元素和对列表尾部的引用(这要么是另一个缺点，要么是 [] )。

正如您应该知道的，当您说 [1, 2, 3] 时，它只是 (1:(2:(3:[]))) 的快捷方式或1:2:3:[] 。如果将每个缺点对可视化为带有两个插槽的盒子，则此表达式如下所示:

┌───┬──┐  ┌───┬──┐  ┌───┬──┐  ┌────┐
│ 1 │ ─┼─>│ 2 │ ─┼─>│ 3 │ ─┼─>│ [] │
└───┴──┘  └───┴──┘  └───┴──┘  └────┘

一个循环

当你说g = 4 : g时，您并不是真正构建一个“无限”列表，而是构建一个循环列表:g被定义为一个 cons，其尾部引用简单地指向 g 本身:

┌──────────┐
│ ┌───┬──┐ │
└>│ 4 │ ─┼─┘
  └───┴──┘

这实际上与懒惰无关，一切都与自引用无关:例如，您可以使用像 '#1=(4 . #1#) 这样的语法在(热切的)Common Lisp 中做同样的事情。 (其中 #1 类似于 g )。

无论你说g !! 0 ，或g !! 1000000000000 , g永不增长:(!!)只需就地围绕循环运行，按照您指定的次数运行，直到它耗尽自身并返回元素 4 .

两个循环

当你说f = (f !! 10) : f时，同样的事情发生了——除了现在，元素槽包含与 4 不同的表达式。 :

┌──────────┐
│ ┌───┬──┐ │
└>│ ╷ │ ─┼─┘
  └─┼─┴──┘
    │
    │ ┌───────────┐
    └>│ (f !! 10) │
      └───────────┘

至关重要的是，这个子表达式还引用 f ，就像尾部一样:

 ┌──────────┐
 │ ┌───┬──┐ │
┌┴>│ ╷ │ ─┼─┘
│  └─┼─┴──┘
│    │
│    │ ┌───────────┐
│    └>│ (f !! 10) │
│      └──┼────────┘
└─────────┘

所以，当你请求f !! n时, (!!)将首先绕顶部循环运行 n次，然后返回该元素，就像 g 那样。然而， (f !! 10) 并没有逃避循环，只需重新输入，该过程就会重复进行:围绕顶部循环 10 次，然后围绕底部循环一次，然后返回。