左折叠实现的列表拼接在Haskell惰性求值中的复杂度分析

你提的这个问题非常关键——惰性求值确实给foldl (++) []的时间复杂度带来了和严格求值语言完全不同的表现，你的手动推导方向是对的，咱们来系统拆解一下：

先回顾严格求值的情况 #

在像OCaml这样的严格求值语言里，foldl (++) []处理[xs1, xs2, ..., xsn]时，每一步拼接都会立即完全计算：

• 第一步：[] ++ xs1 → 得到xs1，遍历0个元素
• 第二步：xs1 ++ xs2 → 遍历xs1的所有元素，把它们逐个放到xs2前面
• 第三步：(xs1++xs2) ++ xs3 → 遍历xs1++xs2的所有元素，再放到xs3前面
• ...
  总遍历次数是len(xs1) + len(xs1)+len(xs2) + ... + sum_{i=1 to n-1} len(xsi)，这显然是元素总数的平方级O(n²)。

Haskell惰性求值下的变化 #

Haskell的惰性求值会延迟所有不必要的计算，咱们先明确标准的(++)实现：

(++) :: [a] -> [a] -> [a]
xs ++ ys = case xs of
    []     -> ys
    x:xs'  -> x : (xs' ++ ys)

现在看你举的例子foldl (++) [] [[1,2,3], [4,5,6], [7,8,9]]，它对应的表达式是(([] ++ [1,2,3]) ++ [4,5,6]) ++ [7,8,9]，简化后就是([1,2,3] ++ [4,5,6]) ++ [7,8,9]。

按照惰性求值的规则，只有当我们需要取出列表的具体元素时，才会逐步展开(++)的计算：

1. 当我们要取第一个元素时，外层的(++)需要匹配它的第一个参数[1,2,3] ++ [4,5,6]，于是展开这个内层(++)：

   (++) ((++) [1,2,3] [4,5,6]) [7,8,9]
   → (++) (1 : ([2,3] ++ [4,5,6])) [7,8,9]
   → 1 : (([2,3] ++ [4,5,6]) ++ [7,8,9])
   

   这时候我们得到了第一个元素1，剩下的部分是一个未计算的thunk：(([2,3] ++ [4,5,6]) ++ [7,8,9])。

2. 当我们要取第二个元素时，继续展开剩下的thunk：

   (([2,3] ++ [4,5,6]) ++ [7,8,9])
   → (++) ((++) [2,3] [4,5,6]) [7,8,9]
   → (++) (2 : ([3] ++ [4,5,6])) [7,8,9]
   → 2 : (([3] ++ [4,5,6]) ++ [7,8,9])
   

   得到第二个元素2，依此类推。

整个过程中，每个元素只会被遍历一次：当元素被求值出来后，后续访问直接使用这个值，不会再重新计算前面的拼接操作。所以当我们完全遍历最终列表一次时，总时间复杂度是O(n)，n是所有元素的总数。

注意点：多次遍历的情况 #

这里有个容易踩坑的地方：如果我们多次遍历foldl (++) []生成的列表，每次遍历都会重新展开所有的thunk，这时候总时间复杂度就会变成O(m*n)（m是遍历次数）。而如果用foldr (++) []，它生成的是一个直接的链表结构，多次遍历都是O(n)，因为没有嵌套的thunk需要重复展开。

总结你的推导 #

你的手动推理是完全正确的！惰性求值的核心就是“按需计算”，foldl (++) []并没有提前把所有拼接都完成，而是生成了一个嵌套的计算链，只有在需要元素的时候才一步步展开，每个元素只被处理一次，所以单次遍历的时间复杂度是线性的，而不是严格求值中的平方级。

内容的提问来源于stack exchange，提问作者Dan Oneață