Haskell中两个累积和(cumsum)函数的复杂性

Question

考虑以下两个累积和(cumsum)函数:

cumsum :: Num a => [a] -> [a]
cumsum [] = []
cumsum [x] = [x]
cumsum (x:y:ys) = x : (cumsum $ (x+y) : ys)

和

cumsum' :: Num a => [a] -> [a]
cumsum' x = [sum $ take k x | k <- [1..length x]]

当然,我更喜欢的定义cumsum到的cumsum',我知道,前者具有线性复杂度.

但为什么cumsum'还有线性复杂性呢？take本身具有线性复杂性在其参数的长度和k从运行1到length x.因此,我预计二次复杂度为 cumsum'.

而且,常数cumsum'低于cumsum.这是由于后者的递归列表附加吗？

注意:欢迎任何累积金额的明智定义.

编辑:我正在测量执行时间(:set +s在GHCi中启用后):

last $ cumsum [1..n]

Answer 1

这是由懒惰引起的测量误差.

Haskell中的每个值都是惰性的:在必要之前不会对其进行评估.这包括值的子结构 - 例如,当我们看到一个模式(x:xs)时,这只会强制对列表进行足够的评估,以确定该列表是非空的,但它不会强制执行头部x或尾部xs.

定义last如下:

last [x] = x
last (x:xs) = last xs

因此,当last应用于结果时cumsum',它以递归方式检查列表推导,但仅足以跟踪最后一个条目.它不强制任何条目,但它确实返回最后一个条目.

当最后一个条目以ghci或其他方式打印时,它会被强制执行,这需要预期的线性时间.但其他条目从未计算过,因此我们没有看到"预期的"二次行为.

使用maximum而不是last表明它cumnorm'是二次的而是cumnorm线性的.

[注意:这种解释有点波动:真正的评价完全last取决于最终结果所需要的,所以即使只是评估,因为需要它的结果.搜索"Haskell评估顺序"和"弱头正常形式"之类的内容,以获得更精确的解释.