Haskell对列表多次执行map操作的时间复杂度：遍历1次还是3次？

开发者阿泽

2026-10-3

Haskell 多次链式列表操作的遍历次数问题解答

结论

你给出的示例代码执行时只会遍历列表1次，时间复杂度为O(n)，不会出现命令式语言中常见的三次遍历、生成两次中间列表的情况。

这是Haskell惰性求值特性的天然效果，不需要依赖额外的编译优化：惰性求值模式下，表达式仅在需要其值时才会触发计算，且只会计算到能返回所需结果的最小程度。
你给出的链式调用代码：
```
map (+1) $ map (*2) $ map (^2) [1..100]
```
执行逻辑和手动合并函数后的写法完全等价：
```
map ( (+1) . (*2) . (^2) ) [1..100]
```
具体求值流程（以取结果列表第一个元素为例）：
1. 仅取出源列表的第一个元素1
2. 依次对该元素执行平方、乘2、加1三个操作，得到结果3直接返回
3. 剩余99个元素的计算会推迟到需要访问的时候才触发，全程不会生成任何完整的中间列表
该逻辑对filter等其他列表操作同样适用：所有链式操作会合并到单次遍历中，对每个元素依次执行所有操作后才会处理下一个元素，不会触发多次全量遍历。