Haskell列表推导式是否为惰性？对应代码内存溢出如何优化？

问题1：惰性列表为何出现内存溢出 #

核心原因出在sum函数的默认实现和编译器优化触发条件上：

• GHC 7.10之前版本的sum基于惰性左折叠foldl实现，遍历过程中不会对累加值做强制求值，会累计上亿个未计算的thunk（待求值表达式），单个thunk的内存占用远高于Word32的4字节，直接撑爆内存。
• 即使是使用了严格折叠的新版本sum，如果没有开启-O2优化，GHC不会触发列表融合规则，中间的列表节点依然会逐个生成，即使惰性列表的节点可以被GC，短时间生成的大量临时节点也会远超GC的回收速度，最终触发OOM。
• 额外的低效点：当前写法的双重遍历复杂度为O(n²)，本身也会放大内存和性能问题。

问题2：符合Haskell惯用风格的实现 #

优先选择数学层面的等价优化

你当前的计算逻辑可以直接从O(n²)简化到O(1)，完全不需要嵌套遍历：
根据求和的线性性质，sum [i*j | i <- [0..10000], j <- [0..10000]] 完全等价于 (sum [0..10000]) ^ 2，整数除法可以放到最后执行，代码可以简化为：

import Data.Word

result :: Word32
result = div (sumSeq * sumSeq) 3
  where sumSeq = 10000 * 10001 `div` 2 -- 等差数列求和公式，直接O(1)计算0到10000的和

通用嵌套遍历场景的惯用写法

如果你的实际业务逻辑无法用数学公式简化，需要保留嵌套遍历，推荐以下写法：

1. 显式用严格左折叠替代默认sum，避免thunk积累，同时开启-O2优化触发列表融合，消除中间列表开销：

import Data.Word
import Data.List (foldl')

kernel :: (Word32, Word32) -> Word32
kernel (i,j) = div (i * j) 3

result :: Word32
result = foldl' (\acc x -> acc + kernel x) 0 $ (,) <$> [0 :: Word32 .. 10000] <*> [0 :: Word32 .. 10000]

2. 对于更复杂的流式计算场景，可以使用vector的高效遍历接口，或者conduit/pipes这类流式处理库，都是Haskell生态的标准选择，不需要手动写底层尾递归。

内容的提问来源于stack exchange，提问作者BitTickler