为什么严格的长度函数表现得更快？

Question

我玩弄定义以更好地理解评估模型,并为列表的长度写了两个.

天真的定义:

len :: [a] -> Int
len [] = 0
len (_:xs) = 1 + len xs

严格(和尾递归)定义:

slen :: [a] -> Int -> Int
slen [] n = n
slen (_:xs) !n = slen xs (n+1)

len [1..10000000]大约需要5-6秒才能完成.
slen [1..10000000] 0执行大约需要3-4秒.

我很好奇为什么.在我检查表演之前,我很肯定他们会表现相同,因为len最多只能评估一次.出于演示目的:

len [a,b,c,d]
= 1 + len [b,c,d]
= 1 + 1 + len [c,d]
= 1 + 1 + 1 + len [d]
= 1 + 1 + 1 + 1 + len []
= 1 + 1 + 1 + 1 + 0
= 4

和

slen [a,b,c,d] 0
= slen [b,c,d] 1
= slen [c,d]   2
= slen [d]     3
= slen []      4
= 4

什么使得slen明显更快？

PS我还写了一个尾递归懒惰函数(就像slen但懒惰)作为尝试接近原因 - 也许是因为它是尾递归 - 但它执行与天真定义相同.

Answer 1

最后一步len不是O(1).将n个数加在一起是O(n).len在slen使用O(1)内存时也使用O(n )内存.

它使用O(n)内存的原因是每个thunk都占用了一些内存.所以当你有这样的事情时:

1 + 1 + 1 + 1 + len []

有五个未评估的thunk(包括len [])

在GHCi中,我们可以使用该:sprint命令更轻松地检查这种thunk行为.该:sprint命令打印给定值而不强制评估任何thunk(您可以从中了解更多信息:help).我将使用conses((:)),因为我们可以更容易地一次评估每个thunk,但原理是相同的.

?> let ys = map id $ 1 : 2 : 3 : [] :: [Int] -- map id prevents GHCi from being too eager here
?> :sprint ys
ys = _
?> take 1 ys
[1]
?> :sprint ys
ys = 1 : _
?> take 2 ys
[1,2]
?> :sprint ys
ys = 1 : 2 : _
?> take 3 ys
[1,2,3]
?> :sprint ys
ys = 1 : 2 : 3 : _
?> take 4 ys
[1,2,3]
?> :sprint ys
ys = [1,2,3]

未评估的thunks由表示_,你可以看到在原始中ys有4thunk嵌套在彼此内部,一个用于列表的每个部分(包括[]).

我知道看到这个并不是一个很好的方法,Int因为它的评估更多是全部或全部,但它仍然以相同的方式构建嵌套的thunk.如果你能看到这样,它的评估看起来像这样:

len [a,b,c,d]
= 1 + len [b,c,d]
= 1 + 1 + len [c,d]
= 1 + 1 + 1 + len [d]
= 1 + 1 + 1 + 1 + len []
= 1 + 1 + 1 + 1 + 0
= 1 + 1 + 1 + 1       -- Here it stops building the thunks and starts evaluating them
= 1 + 1 + 2
= 1 + 3
= 4