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

在 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>

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

对非 Haskeller 的解释：

The :运算符是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 from g:

Prelude> g !! 0
4

但是当我这样做时：

Prelude> let f = f !! 10 : f

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

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

首先，记住缺点（(:)列表构造函数）有效。它由两件事组成：一个元素和对列表尾部的引用（这要么是另一个缺点，要么[]).

你应该知道，当你说[1, 2, 3]，这只是一个捷径(1:(2:(3:[]))) or 1:2:3:[]。如果将每个 cons 对可视化为带有两个插槽的盒子，则此表达式如下所示：

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

One loop

当你说g = 4 : g，你并没有真正构建一个“无限”列表，你正在构建一个circular list: g被定义为一个 cons，其尾部引用简单地指向g itself:

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

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

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

两个循环

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

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

至关重要的是，这个子表达式also回指f，就像尾巴一样：

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

所以，当你要求f !! n, (!!)将首先绕顶部循环运行n次，然后返回该元素，就像g。然而，不是逃避循环，(f !! 10)只需重新进入，该过程就会重复进行：围绕顶部循环 10 次，然后围绕底部循环一次，然后返回。