haskell - 此列表如何理解其自身的单位？

Question

在#haskell IRC channel 中，有人问

Is there a succinct way to define a list where the nth entry is the sum of the squares of all entries before?

我认为这听起来像是一个有趣的难题，并且递归定义无限列表是我真正需要练习的事情之一。因此，我启动了GHCi并开始使用递归定义。最终，我设法

λ> let xs = 1 : [sum (map (^2) ys) | ys <- inits xs, not (null ys)]

这似乎会产生正确的结果:

λ> take 9 xs
[1,1,2,6,42,1806,3263442,10650056950806,113423713055421844361000442]

不幸的是，我不知道我编写的代码是如何工作的。可以解释以中级Haskell用户理解的方式执行此代码时会发生什么情况吗？

Answer 1

归结为懒惰的评估。让我们来看一下augustss的定义，因为它稍微简单一些，但是将其称为big而不是xs，因为该标识符通常在实用程序中使用。

Haskell仅在需要时评估代码。如果不需要某些内容，则在其中存在一个 stub ，基本上是一个指向函数闭包的指针，该闭包可以根据需要计算值。

假设我要评估big !! 4。 !!的定义是这样的:

[] !! _ = error "Prelude.(!!): index too large"
(x:_) !! 0 = x
(_:xs) !! n = xs !! (n-1)

big的定义是

big = 1 : [sum (map (^2) ys) | ys <- tail (inits big)]

因此，在评估索引访问时，首先发生的事情是必须选择正确的函数变体。列表数据类型具有两个构造函数 []和 first : rest。调用为 big !! 4，并且 !!的第一个分支仅检查列表是否为 []。由于该列表显式以 1 : stub1开头，因此答案为否，并且跳过该分支。

第二个分支想知道是否选择了 first : rest形式。答案是肯定的， first是 1，而 rest是那么大的理解力( stub1)，其值无关紧要。但是第二个参数不是 0，因此也跳过了该分支。

第三分支也匹配 first : last，但是第二个参数接受任何内容，因此适用。它忽略 first，将 xs绑定(bind)到未评估的理解 stub1，并将 n绑定(bind)到 4。然后，它以第一个参数为comprehension和第二个 3递归地调用自身。 (从技术上讲，这是 (4-1)，尚未进行评估，但为简化起见，我们假设是。)

递归调用再次必须评估其分支。第一个分支检查第一个参数是否为空。由于到目前为止该参数是未评估的 stub ，因此需要对其进行评估。但是仅够确定分支是否为空。因此，让我们开始评估理解力:

stub1 = [sum (map (^2) ys) | ys <- tail (inits big)]

我们需要的第一件事是 ys。它设置为 tail (inits big)。 tail很简单:

tail [] = []
tail (_:xs) = xs

inits的实现相当复杂，但是重要的是它会懒惰地生成结果列表，即如果给它 (x:unevaluated)，它将在评估列表的其余部分之前生成 []和 [x]。换句话说，如果您不仅仅局限于这些，那么它将永远不会评估其余部分。

因此，到目前为止， big已知为 (1 : stub1)，因此 inits返回 [] : stub2。 tail与此匹配，选择其第二个分支，并返回 stub2。 stub2是无处不在的空列表之后 big的初始化列表，并且尚未生成。

然后，列表理解会尝试为 ys提供 stub2的第一个元素的值，因此必须对其进行评估。 inits的第二个结果仍然是已知的，它是 [1]。 ys获得该值。然后，此时 big称为 1 : stub3 : stub4，其中 stub3 = sum (map (^2) [1])和 stub4是第一次迭代后的列表推导。

由于现在进一步评估了 big，因此对 stub1也进行了评估。现在知道它是 stub3 : stub4，我们终于可以在 !!中前进。第一个分支不适用，因为列表不为空。第二个分支不适用，因为 3 /= 0。应用第三个分支，将 xs绑定(bind)到 stub4，将 n绑定(bind)到 3。递归调用是 stub4 !! 2。

我们需要评估一下 stub4。这意味着我们进入了理解的下一个迭代。我们需要 inits big的第三个元素。由于现在已知 big是 1 : stub3 : stub4，因此无需进一步评估就可以计算出第三个元素作为 [1, stub3]。 ys绑定(bind)到该值，并且 stub4的计算结果为 stub5 : stub6，其中 stub5 = sum (map (^2) [1, stub3])和 stub6是前两次迭代后的理解。经过 stub4评估，我们现在知道 big = 1 : stub3 : stub5 : stub6。

因此， stub4仍然与 !!的第一个分支不匹配(永远不会，因为我们正在处理一个无限列表)。 2仍然与第二个分支不匹配。我们有另一个递归调用，然后有另一个递归调用，遵循的是与到目前为止相同的模式。当索引最终达到0时，我们有:

big = 1 : stub3 : stub5 : stub7 : stub9 : stub10
stub3 = sum (map (^2) [1])
stub5 = sum (map (^2) [1, stub3])
stub7 = sum (map (^2) [1, stub3, stub5])
stub9 = sum (map (^2) [1, stub3, stub5, stub7])
stub10 = whatever remains of the list comprehension

我们当前的调用是 (stub9 : stub10) !! 0，它最终与第二个分支匹配。 x绑定(bind)到 stub9并返回。

直到现在，如果您实际尝试打印或以其他方式处理 x，所有这些 stub 最终都会被评估为实际数字。