这归结为惰性评估。让我们采用 augustss 的定义,因为它稍微简单一些,但称之为big
代替xs
,因为该标识符在实用程序中常用。
Haskell 仅在需要时才评估代码。如果不需要的话,那里有一个存根,基本上是一个指向函数闭包的指针,可以在需要时计算该值。
假设我想评估big !! 4
。的定义!!
是这样的:
[] !! _ = error "Prelude.(!!): index too large"
(x:_) !! 0 = x
(_:xs) !! n = xs !! (n-1)
的定义big
is
big = 1 : [sum (map (^2) ys) | ys <- tail (inits big)]
因此,在评估索引访问时,首先要做的就是必须选择正确的函数变体。列表数据类型有两个构造函数,[]
and first : rest
。通话内容是big !! 4
,以及第一个分支!!
只是检查列表是否是[]
。由于列表明确以1 : stub1
,答案是否定的,并且该分支被跳过。
第二个分支想知道是否first : rest
选择了形式。答案是肯定的,与first
being 1
and rest
这么大的理解力(stub1
),其值无关紧要。但第二个论点不是0
,所以这个分支也被跳过。
第三个分支也与first : last
,但接受第二个参数的任何内容,因此它适用。它忽略了first
, binds xs
未评估的理解stub1
, and n
to 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)
,它会生成[]
and [x]
在评估列表的其余部分之前。换句话说,如果你不超越这些,它就永远不会评估其余的。
所以,到目前为止big
已知是(1 : stub1)
, so inits
回报[] : stub2
. tail
与此匹配,选择其第二个分支,然后返回stub2
. stub2
是单位列表big
在无所不在的空列表之后,它还没有生成。
然后列表理解尝试给出ys
第一个元素的值stub2
,所以必须对其进行评估。第二个结果是inits
仍然已知,它是[1]
. ys
得到那个值。那么此时,big
已知是1 : stub3 : stub4
, where stub3 = sum (map (^2) [1])
and stub4
是第一次迭代后的列表理解。
Since big
现在正在进一步评估,所以stub1
。现在已知的是stub3 : stub4
,我们终于可以前进了!!
。第一个分支不适用,因为列表不为空。第二个分支不适用,因为3 /= 0
。第三分支适用,具有约束力xs
to stub4
and n
to 3
。递归调用是stub4 !! 2
.
我们需要评估一下stub4
。这意味着我们进入理解的下一个迭代。我们需要第三个元素inits big
. Since big
目前已知是1 : stub3 : stub4
,第三个元素无需进一步评估即可计算为[1, stub3]
. ys
与该值绑定,并且stub4
评估为stub5 : stub6
, where stub5 = sum (map (^2) [1, stub3])
and stub6
是前两次迭代后的理解。和stub4
评估后,我们现在知道big = 1 : stub3 : stub5 : stub6
.
So 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
,所有这些存根最终都会评估为实际数字。