这个列表对自身单位的理解是如何工作的？
How does this list comprehension over the inits of itself work?
在#haskell IRC 频道有人问
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 用户可以理解的方式执行此代码时会发生什么？
好的，我试试。
（我不确定你要找的 "intermediate" 级别，所以我会自己解释一下，希望它不会太 "sub-intermediate"。）
sum (map (^2) ys) 很简单：列表的平方和。
生成器也很简单：y 接受 xs 的所有非空初始序列，即（稍微滥用符号）y <- [take 1 xs, take 2 xs, take 3 xs,...].
（我将在下文中保留 take 符号，因为我认为它很清楚。这很可能不是您闪亮的 Haskell 机器内部发生的情况。）
唯一棘手的事情是组合它们，因为 xs 是我们定义的值。
这不是一个大问题，因为我们知道 xs 的第一个元素 - 它是 1.
数量不多，但它是 take 1 xs.
所需要的一切
再挥手一下，xs是
1 : (sum (map (^2) (take 1 xs))) : (sum (map (^2) (take 2 xs))) : ...
即（因为我们知道第一个元素是1）：
xs = 1 : (sum (map (^2) [1])) : (sum (map (^2) (take 2 xs))) : ...
xs = 1 : 1 : (sum (map (^2) (take 2 xs))) : (sum (map (^2) (take 3 xs))) : ...
我们有第二个元素，我们可以继续：
xs = 1 : 1 : (sum (map (^2) [1,1])) : (sum (map (^2) (take 3 xs))) : ...
xs = 1 : 1 : 2 : (sum (map (^2) (take 3 xs))) : (sum (map (^2) (take 4 xs))) : ...
xs = 1 : 1 : 2 : (sum (map (^2) [1,1,2])) : (sum (map (^2) (take 4 xs))) : ...
等等。
之所以有效，是因为列表中的每个元素都只依赖于前面的元素——你总是可以依靠过去来告诉你发生了什么；未来不太可靠。
归根结底是惰性求值。让我们继续 augustss 的定义，因为它稍微简单一些，但将其称为 big 而不是 xs，因为该标识符在实用程序中很常用。
Haskell 只评估立即需要的代码。如果不需要，那里有一个存根，基本上是一个指向函数闭包的指针，可以在需要时计算值。
假设我想评估 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 绑定到未评估的理解 stub1，并将 n 绑定到 4。然后它递归地调用自己，第一个参数是理解，第二个参数是 3。 （从技术上讲，那是 (4-1) 并且尚未评估，但作为简化，我们假设它是。）
递归调用必须再次评估其分支。第一个分支检查第一个参数是否为空。由于到目前为止的参数是一个未评估的存根，因此需要对其进行评估。但只够判断分支是否为空。那么让我们开始评估理解：
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 returns [] : stub2。 tail 与之匹配，选择它的第二个分支，returns stub2。 stub2是无处不在的空列表之后big的inits列表，还没有生成。
列表理解然后尝试给 ys stub2 的第一个元素的值，因此必须对其进行评估。 inits的第二个结果仍然是已知的，它是[1]。 ys 获取该值。那么，此时，big 已知为 1 : stub3 : stub4，其中 stub3 = sum (map (^2) [1]) 和 stub4 是第一次迭代后的列表理解。
由于 big 现在被进一步评估，所以 stub1。现在已知是stub3 : stub4，我们终于可以在!!前进了。第一个分支不适用，因为列表不为空。第二个分支不适用，因为 3 /= 0。第三个分支适用，将 xs 绑定到 stub4 并将 n 绑定到 3。递归调用是stub4 !! 2.
我们需要评估一下stub4。这意味着我们进入了理解的下一个迭代。我们需要 inits big 的第三个元素。由于现在已知 big 为 1 : stub3 : stub4，因此无需进一步计算即可计算出第三个元素为 [1, stub3]。 ys 绑定到此值，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 绑定到 stub9 并返回。
只有现在，如果您实际尝试打印或以其他方式处理 x，所有这些存根是否最终评估为实际数字。
稍微调整一下您的代码，直到它变成更易于理解的形式，我们得到
xs = 1 : [sum (map (^2) ys) | ys <- inits xs, not (null ys)]
= 1 : (map (sum . map (^2)) . map (`take` xs)) [1..]
= 1 : map (sum . map (^2) . (`take` xs)) [1..]
= 1 : scanl1 (\a b-> a+b^2) xs
= x1 : xs1
where { x1 = 1;
xs1 = scanl1 g xs
= scanl g x1 xs1; -- by scanl1 definition
g a x = a+x^2 }
scanl 适用于 non-empty 列表，如
scanl g a xs = a : case xs of (h:t) -> scanl g (g a h) t
so xs1 = scanl g a xs1 将首先将当前已知的累加值放在其输出的头部 (xs1 = (a:_))，然后才会读取该输出，因此这个定义是有效的。我们还看到 h = a，所以 g a h = g a a = a+a^2 = a*(a+1) 我们可以纯迭代地对该流进行编码，如
xs = 1 : iterate (\a -> a*(a+1)) 1
在#haskell IRC 频道有人问
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 用户可以理解的方式执行此代码时会发生什么？
好的，我试试。
（我不确定你要找的 "intermediate" 级别，所以我会自己解释一下，希望它不会太 "sub-intermediate"。）
sum (map (^2) ys) 很简单：列表的平方和。
生成器也很简单：y 接受 xs 的所有非空初始序列，即（稍微滥用符号）y <- [take 1 xs, take 2 xs, take 3 xs,...].
（我将在下文中保留 take 符号，因为我认为它很清楚。这很可能不是您闪亮的 Haskell 机器内部发生的情况。）
唯一棘手的事情是组合它们，因为 xs 是我们定义的值。
这不是一个大问题，因为我们知道 xs 的第一个元素 - 它是 1.
数量不多，但它是 take 1 xs.
再挥手一下，xs是
1 : (sum (map (^2) (take 1 xs))) : (sum (map (^2) (take 2 xs))) : ...
即（因为我们知道第一个元素是1）：
xs = 1 : (sum (map (^2) [1])) : (sum (map (^2) (take 2 xs))) : ...
xs = 1 : 1 : (sum (map (^2) (take 2 xs))) : (sum (map (^2) (take 3 xs))) : ...
我们有第二个元素，我们可以继续：
xs = 1 : 1 : (sum (map (^2) [1,1])) : (sum (map (^2) (take 3 xs))) : ...
xs = 1 : 1 : 2 : (sum (map (^2) (take 3 xs))) : (sum (map (^2) (take 4 xs))) : ...
xs = 1 : 1 : 2 : (sum (map (^2) [1,1,2])) : (sum (map (^2) (take 4 xs))) : ...
等等。
之所以有效，是因为列表中的每个元素都只依赖于前面的元素——你总是可以依靠过去来告诉你发生了什么；未来不太可靠。
归根结底是惰性求值。让我们继续 augustss 的定义，因为它稍微简单一些，但将其称为 big 而不是 xs，因为该标识符在实用程序中很常用。
Haskell 只评估立即需要的代码。如果不需要，那里有一个存根，基本上是一个指向函数闭包的指针，可以在需要时计算值。
假设我想评估 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 绑定到未评估的理解 stub1，并将 n 绑定到 4。然后它递归地调用自己，第一个参数是理解，第二个参数是 3。 （从技术上讲，那是 (4-1) 并且尚未评估，但作为简化，我们假设它是。）
递归调用必须再次评估其分支。第一个分支检查第一个参数是否为空。由于到目前为止的参数是一个未评估的存根，因此需要对其进行评估。但只够判断分支是否为空。那么让我们开始评估理解：
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 returns [] : stub2。 tail 与之匹配，选择它的第二个分支，returns stub2。 stub2是无处不在的空列表之后big的inits列表，还没有生成。
列表理解然后尝试给 ys stub2 的第一个元素的值，因此必须对其进行评估。 inits的第二个结果仍然是已知的，它是[1]。 ys 获取该值。那么，此时，big 已知为 1 : stub3 : stub4，其中 stub3 = sum (map (^2) [1]) 和 stub4 是第一次迭代后的列表理解。
由于 big 现在被进一步评估，所以 stub1。现在已知是stub3 : stub4，我们终于可以在!!前进了。第一个分支不适用，因为列表不为空。第二个分支不适用，因为 3 /= 0。第三个分支适用，将 xs 绑定到 stub4 并将 n 绑定到 3。递归调用是stub4 !! 2.
我们需要评估一下stub4。这意味着我们进入了理解的下一个迭代。我们需要 inits big 的第三个元素。由于现在已知 big 为 1 : stub3 : stub4，因此无需进一步计算即可计算出第三个元素为 [1, stub3]。 ys 绑定到此值，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 绑定到 stub9 并返回。
只有现在，如果您实际尝试打印或以其他方式处理 x，所有这些存根是否最终评估为实际数字。
稍微调整一下您的代码，直到它变成更易于理解的形式，我们得到
xs = 1 : [sum (map (^2) ys) | ys <- inits xs, not (null ys)]
= 1 : (map (sum . map (^2)) . map (`take` xs)) [1..]
= 1 : map (sum . map (^2) . (`take` xs)) [1..]
= 1 : scanl1 (\a b-> a+b^2) xs
= x1 : xs1
where { x1 = 1;
xs1 = scanl1 g xs
= scanl g x1 xs1; -- by scanl1 definition
g a x = a+x^2 }
scanl 适用于 non-empty 列表，如
scanl g a xs = a : case xs of (h:t) -> scanl g (g a h) t
so xs1 = scanl g a xs1 将首先将当前已知的累加值放在其输出的头部 (xs1 = (a:_))，然后才会读取该输出，因此这个定义是有效的。我们还看到 h = a，所以 g a h = g a a = a+a^2 = a*(a+1) 我们可以纯迭代地对该流进行编码，如
xs = 1 : iterate (\a -> a*(a+1)) 1