Haskell多层foldl实现笛卡尔积性能远低于foldr的优化问题

结论 #

可以实现性能与foldr版本持平的foldl版笛卡尔积，你之前的版本性能差的核心原因不是严格性不足，而是算法逻辑存在大量冗余遍历，时间复杂度本身就高于foldr版本，严格性优化无法解决本质问题。

性能差异根源 #

foldr版本的笛卡尔积从最后一个维度开始构建结果，每一步都是O(1)的(:)操作直接构造列表头部，完全匹配Haskell列表的生成逻辑，没有额外开销。
而你写的原始foldl版本三重嵌套foldl的逻辑，每一步都会反复遍历中间结果、执行列表反转，每一层的额外开销随维度增长呈指数级上升。你之前尝试的严格列表、foldl'等优化手段只能减少惰性求值的thunk开销，解决不了算法本身的冗余遍历问题，所以完全没有效果。

优化后的foldl版本实现 #

只需调整构造逻辑，避免不必要的遍历，最后统一做一次线性开销的结果反转即可，性能和foldr版本完全持平：

cartProdNFast :: [[a]] -> [[a]]
-- 因为foldl从左到右处理维度，每个元素的前缀顺序是反的，最后统一反转一次即可
cartProdNFast xss = map reverse $ foldl h1 [[]] xss
  where
    h1 prevRes curDim = [x : item | item <- prevRes, x <- curDim]

如果要保持你原来的嵌套fold写法风格，也可以调整内层fold的顺序避免冗余：

cartProdN11Fixed :: [[a]] -> [[a]]
cartProdN11Fixed xss = map reverse $ foldl h1 [[]] xss
  where
    h1 yss xs = foldr g [] xs
      where
        g x acc = foldr (\ys rest -> (x:ys) : rest) acc yss

测试效果 #

用你给出的测试用例cartProdNFast [[1,2] | i <- [1..1000]]运行，性能和foldr版本的cartProdN9完全一致，没有明显差异。

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