Haskell中两个累积和（cumsum）函数的复杂性
考虑以下两个累积和（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'的常数低于cumsum 。 这是由于后者的递归列表附加？
注意 ：欢迎任何累积金额的明智定义。
编辑 ：我正在测量执行时间（使用后:set +s GHCi :set +s ）：
last $ cumsum [1..n]
这是由懒惰引起的测量误差。
Haskell中的每个值都是懒惰的：直到必要时才会对其进行评估。 这包括值的子结构 - 例如，当我们看到一个模式（ x:xs ）时，这只会强制对列表进行评估，足以确定列表非空，但不会强制头x或尾巴xs 。
last的定义如下所示：
last [x] = x
last (x:xs) = last xs
所以当last应用于cumsum'的结果时，它会递归地检查列表理解，但只能追查最后一个条目。 它不会强制任何条目，但它会返回最后一条。
当最后一个条目以ghci或其他格式打印时，它会被强制执行，这需要线性时间。 但其他条目从不计算，所以我们没有看到“预期”的二次行为。
使用maximum而不是last表明cumnorm'是二次的，而cumnorm是线性的。
[注意：这个解释有点手动：真正的评估完全是由最终结果所需要的，所以即使是last也只是因为需要结果而被评估。 搜索诸如“Haskell评估顺序”和“弱头范式”之类的内容以获得更精确的解释。]
上一篇: Complexity of two cumulative sum (cumsum) functions in Haskell