haskell - 为什么我对自引用惰性序列的直觉是错误的？

Question

在 Haskell 中，我可以在 GHCI 中编写一个自引用序列，如下所示:

λ> let x = 1:map (+1) x
λ> take 5 x

产生:

[1,2,3,4,5]

但是我对惰性评估的直觉表明这应该在扩展期间发生

let x = 1:map (+1) x
1:2:map (+1) x
1:2:map (+1) [1, 2] <-- substitution
1:2:2:3:map (+1) x
1:2:2:3:map (+1) [1, 2, 2, 3] <-- substitution
1:2:2:3:2:3:3:4:map (+1) x
...

这显然不是正在发生的事情。我可以在正确答案中看到模式。我们只是一次将列表中的一个元素沿无限流向下移动。我认识的模式，我可以在代码中应用它。然而，它不符合我懒惰评估的心理模型。感觉有点“神奇”。我的直觉哪里错了？

Answer 1

记住只用它的定义替换一些东西。所以每当你展开 x , 你应该替换 1 : map (+1) x ，而不是它的“当前值”(无论这意味着什么)。

我将复制 Jeffrey 的想法，但对懒惰给予应有的尊重。

x = 1 : map (+1) x

take 5 x
= take 5 (1 : map (+1) x)                                 -- x
= 1 : take 4 (map (+1) x)                                 -- take
= 1 : take 4 (map (+1) (1 : map (+1) x)                   -- x
= 1 : take 4 (2 : map (+1) (map (+1) x))                  -- map and (+)
= 1 : 2 : take 3 (map (+1) (map (+1) x))                  -- take
= 1 : 2 : take 3 (map (+1) (map (+1) (1 : map (+1) x)))   -- x
= 1 : 2 : take 3 (map (+1) (2 : map (+1) (map (+1) x)))   -- map and (+)
= 1 : 2 : take 3 (3 : map (+1) (map (+1) (map (+1) x)))   -- map and (+)
= 1 : 2 : 3 : take 2 (map (+1) (map (+1) (map (+1) x)))   -- take

等等。

练习 自己完成这种风格的评估(信息量很大)。

注意我们是如何开始建立 map 的链的。 s 随着列表的增长。如果你只是 print x ，你会看到输出在一段时间后开始变慢；这就是为什么。有一种更有效的方法，留作练习([1..] 是作弊:-)。

注:这仍然没有实际发生的那么懒惰。 map (+1) (1 : ...)计算结果为 (1+1) : map (+1) ... ，并且只有在实际观察到数字时才会发生加法，方法是打印它或例如比较它。

Will Ness 在这篇文章中发现了一个错误；看到评论和他的回答。