为什么我对自我引用懒散序列的直觉是错误的？

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，而不是它的“当前值”(不管这意味着什么)。

我会照搬杰夫弗雷的想法，但要尊重懒惰。

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链的。如果您只是print x，那么您将看到输出在一段时间后开始减速；这就是原因。还有一种更有效的方法，将其作为练习( [1..]是作弊:-)。

注:这仍然比实际发生的事情要少一些懒惰。map (+1) (1 : ...)的计算结果为(1+1) : map (+1) ...，只有在实际观察到数字时，才会进行加法，方法是打印数字或进行比较。

Will Ness在这篇文章中指出了一个错误，见评论和他的回答。

Answer 2

您在整个列表上映射+1，以便初始1变为n，其中n是您懒惰地递归的次数，如果这有意义的话。因此，与您所想到的派生不同，它看起来更像这样：

1:...                            -- [1 ...]
1: map (+1) (1:...)              -- [1, 2 ...]
1: map (+1) (1:map (+1) (1:...)) -- [1, 2, 3 ...]

一个1被加到一个延迟计算的列表中，该列表的元素在递归的每一步中都会增加。

因此，您可以将递归的n第四步看作是接受列表[1, 2, 3, ..., n ...]，将其转换为list [2, 3, 4, ..., n+1 ...]，并在1前面加上一个。

Answer 3

让我们从数学角度看这个问题。假设

x = [1, 2, 3, 4, ...]

然后

map (+1) x = [2, 3, 4, 5, ...]

所以

1 : map (+1) x = 1 : [2, 3, 4, 5, ...] = x

这个(转身)是我们开始使用的等式：

x = 1 : map (+1) x

所以我们展示的是

x = [1, 2, 3, 4, ...]

是方程的一个解。

x = 1 : map (+1) x   -- Eqn 1

当然，下一个问题是Eqn 1是否有其他解决方案，答案是否定的。这一点很重要，因为Haskell的评估模型有效地选择了任何这样的方程的“最小定义”解。例如，如果我们定义了x = 1 : tail x，那么以1开头的任何列表都是一个解决方案，但实际上我们会得到1 : _|_，其中_|_表示一个错误或不终止。Eqn 1不会导致这种混乱：

设y是Eqn 1的任意解，所以

y = 1 : map (+1) y

请注意，我们可以从定义中看出

take 1 y = [1] = take 1 x

现在假设

take n y = take n x

然后

take (n+1) y = take (n+1) (1 : map (+1) y)
             = 1 : take n (map (+1) y)
             = 1 : map (+1) (take n y)
             = 1 : map (+1) (take n x)
             = 1 : take n (map (+1) x)
             = take (n+1) (1 : map (+1) x)
             = take (n+1) x

通过归纳法，我们发现take n y = take n x对于每个n。就是，y = x。