考虑以下两个累积和(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。这是因为递归列表附加了后者吗?
:欢迎任何智能的累积和定义。
EDIT:我正在使用(在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求值顺序"one_answers"弱头范式"来获得更精确的解释。