这个列表如何理解其本身的工作？ [英] How does this list comprehension over the inits of itself work?
问题描述
在#haskell IRC频道有人问：
有没有一种简洁的方式来定义一个列表，其中第n个条目是所有条目的正方形之前？
我认为这听起来像是一个有趣的谜题，递归地定义无限列表就是其中之一真的需要练习。所以我激发了GHCi并开始使用递归定义。最后，我设法得到了
λ>让xs = 1：[sum（map（^ 2）ys）| ys < - inits xs，not（null ys）]
这似乎产生了正确的结果：
λ>以9 xs
[1,1,2,6,42,1806,3263442,10650056950806,113423713055421844361000442]
不幸的是，我不知道我写的代码是如何工作的。是否有可能解释当代码以中间Haskell用户可以理解的方式执行时会发生什么？
下到懒惰的评价。让我们继续讨论augustss的定义，因为它只是稍微简单一些，但将它称为大而不是 xs ，因为该标识符通常用于实用程序中。
Haskell只会立即评估代码。如果没有必要，那里有一个存根，基本上是一个指向函数闭包的指针，如果需要的话可以计算值。
假设我想评估大！ 4 。 !! 的定义如下：
[]！ ！ _ =错误Prelude。（!!）：index too large
（x：_）!! 0 = x
（_：xs）!! n = xs !! （n-1）
定义大是
big = 1：[sum（map（^ 2）ys）| ys< - tail（inits big）]
因此，在评估索引访问时，恰巧是必须选择正确的功能变体。列表数据类型有两个构造函数， [] 和 first：rest 。该电话是大！ 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 返回 []：stub2 。 tail 与此匹配，选择其第二个分支，并返回 stub2 。 stub2 是无所不在的空列表后的 big 的inits列表，尚未生成。 / p>
列表理解然后尝试给 ys stub2的第一个元素的值，所以必须进行评估。 inits 的第二个结果仍然是已知的，它是 [1] 。 ys 获取该值。此时，已知大为 1：stub3：stub4 ，其中 stub3 = sum（map（^ 2）[1]）和 stub4 是第一次迭代后的列表理解。
由于大现在被进一步评估，所以 stub1 。现在已知它是 stub3：stub4 ，我们最终可以在 !! 中前进。第一个分支不适用，因为列表不是空的。第二个分支不适用，因为 3 / = 0 。第三个分支适用于将 xs 绑定到 stub4 和 n 到 3 。递归调用是 stub4！ 2 。
我们需要评估一些 stub4 。这意味着我们进入理解的下一个迭代。我们需要 inits 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]）$ b $ b stub5 = sum（map（^ 2）[1，stub3]）
stub7 = sum（map（^ 2）[1，stub3 ，stub5]）
stub9 = sum（map（^ 2）[1，stub3，stub5，stub7]）
stub10 =任何剩余的列表理解
我们目前的电话是（stub9：stub10）！ 0 ，最后匹配第二个分支。 x 被绑定到 stub9 并返回。
以及只有现在，如果您真的尝试打印或以其他方式处理 x ，那么所有这些存根将被最终评估为实际数字。
In the #haskell IRC channel someone asked
Is there a succinct way to define a list where the nth entry is the sum of the squares of all entries before?
I thought this sounded like a fun puzzle, and defining infinite lists recursively is one of those things I really need to practise. So I fired up GHCi and started playing around with recursive definitions. Eventually, I managed to get to
λ> let xs = 1 : [sum (map (^2) ys) | ys <- inits xs, not (null ys)]
which seems to produce the correct results:
λ> take 9 xs
[1,1,2,6,42,1806,3263442,10650056950806,113423713055421844361000442]
Unfortunately, I have no idea how the code I wrote works. Is it possible to explain what happens when this code is executed in a way that an intermediate Haskell user would understand?
It comes down to lazy evaluation. Let's go with augustss's definition, since it is just slightly simpler, but call it big instead of xs, since that identifier is commonly used in utilities.
Haskell only evaluates code as immediately necessary. If something isn't necessary, there is a stub there, basically a pointer to a function closure that can calculate the value if needed.
Let's say I want to evaluate big !! 4. The definition of !! is something like this:
[] !! _ = error "Prelude.(!!): index too large"
(x:_) !! 0 = x
(_:xs) !! n = xs !! (n-1)
The definition of big is
big = 1 : [sum (map (^2) ys) | ys <- tail (inits big)]
So in evaluating the index access, the first thing that happens is that the correct function variant must be chosen. The list data type has two constructors, [] and first : rest. The call is big !! 4, and the first branch of !! just checks whether the list is []. Since the list explicitly starts with 1 : stub1, the answer is no, and the branch is skipped.
The second branch wants to know whether the first : rest form was chosen. The answer is yes, with first being 1 and rest being that big comprehension (stub1), its value irrelevant. But the second argument is not 0, so this branch is skipped as well.
The third branch also matches against first : last, but accepts anything for the second argument, so it applies. It ignores first, binds xs to the unevaluated comprehension stub1, and n to 4. It then recursively calls itself with the first argument being the comprehension and the second 3. (Technically, that's (4-1) and isn't yet evaluated, but as a simplification we will assume it is.)
The recursive call again has to evaluate its branches. The first branch checks whether the first argument is empty. Since the argument so far is an unevaluated stub, it will need to be evaluated. But only far enough to decide whether the branch is empty. So let's start evaluating the comprehension:
stub1 = [sum (map (^2) ys) | ys <- tail (inits big)]
The first thing we need is ys. It's set to tail (inits big). tail is simple:
tail [] = []
tail (_:xs) = xs
inits is rather complex to implement, but the important thing is that it generates its result list lazily, i.e. if you give it (x:unevaluated), it will generate [] and [x] before evaluating the rest of the list. In other words, if you don't look beyond those, it won't ever evaluate the rest.
So, so far big is known to be (1 : stub1), so inits returns [] : stub2. tail matches against this, chooses its second branch, and returns stub2. stub2 is the list of inits of big after the omnipresent empty list, and it hasn't yet been generated.
The list comprehension then tries to give ys the value of the first element of stub2, so it has to be evaluated. The second result of inits is still known, it's [1]. ys gets that value. At this point, then, big is known to be 1 : stub3 : stub4, where stub3 = sum (map (^2) [1]) and stub4 is the list comprehension after the first iteration.
Since big is now evaluated further, so is stub1. It is now known to be stub3 : stub4, and we can finally advance in !!. The first branch doesn't apply, since the list isn't empty. The second branch doesn't apply because 3 /= 0. The third branch applies, binding xs to stub4 and n to 3. The recursive call is stub4 !! 2.
We need to evaluate a bit of stub4. This means we enter the next iteration of the comprehension. We need the third element of inits big. Since big is by now known to be 1 : stub3 : stub4, the third element can be calculated without further evaluation as [1, stub3]. ys is bound to this value, and stub4 evaluates to stub5 : stub6, where stub5 = sum (map (^2) [1, stub3]) and stub6 is the comprehension after the first two iterations. With stub4 evaluated, we now know that big = 1 : stub3 : stub5 : stub6.
So stub4 still doesn't match the first branch of !! (nothing ever will, since we're dealing with an infinite list). 2 still doesn't match the second branch. We have another recursive call, and then another, following the same pattern as we had so far. When the index finally reaches 0, we have:
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
Our current call is (stub9 : stub10) !! 0, which finally matches the second branch. x is bound to stub9 and returned.
And only now, if you actually try to print or otherwise process x, are all of these stubs finally evaluated to an actual number.
这篇关于这个列表如何理解其本身的工作？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
