Haskell中高效生成列表所有交错序列的方法及优化探讨

在并发测试场景中，我们常需要遍历多条指令的所有交错执行可能，这本质是生成两个（或多个）输入列表的所有交错序列。Stack Overflow上有一个基础的interleavings实现：

interleavings :: [a] -> [a] -> [[a]]
interleavings [] ys = [ys]
interleavings xs [] = [xs]
interleavings (x:xs) (y:ys) = map (x:) (interleavings xs (y:ys)) ++ map (y:) (interleavings (x:xs) ys)

这个实现逻辑直观，但存在效率瓶颈：Haskell的单链表特性导致++操作需要遍历左侧整个列表才能完成拼接，当输入列表较长、交错序列数量增多时，重复遍历会带来显著的性能损耗。

结合惰性求值与单链表的优化方案 #

利用Haskell的惰性求值，搭配**差集列表（DList）**可以优化拼接操作的效率。DList通过函数式封装实现了O(1)时间的拼接和头部插入，完全适配单链表的惰性特性：

import Data.DList (DList, toList, cons)
import qualified Data.DList as DL

interleavingsDL :: [a] -> [a] -> [DList a]
interleavingsDL [] ys = [DL.fromList ys]
interleavingsDL xs [] = [DL.fromList xs]
interleavingsDL (x:xs) (y:ys) = map (cons x) (interleavingsDL xs (y:ys)) ++ map (cons y) (interleavingsDL (x:xs) ys)

-- 转换为普通列表输出
interleavingsOpt :: [a] -> [a] -> [[a]]
interleavingsOpt xs ys = map toList (interleavingsDL xs ys)

这里cons操作是O(1)，且DList的拼接不会立即触发列表遍历——惰性求值会延迟实际列表的构造，直到你调用toList时才会生成最终的普通列表，彻底避免了基础实现中++带来的重复遍历开销。

无需驻留内存的按需处理优化 #

如果不需要把所有交错序列都存在内存里，只需要对每个序列执行特定逻辑（比如测试断言、结果打印），可以直接在生成过程中处理序列，完全规避内存堆积：

方案1：折叠式遍历（Fold-Based Traversal） #

实现一个折叠函数，直接将处理逻辑传入，逐个生成并处理交错序列：

foldInterleavings :: (b -> [a] -> b) -> b -> [a] -> [a] -> b
foldInterleavings f acc [] ys = f acc ys
foldInterleavings f acc xs [] = f acc xs
foldInterleavings f acc (x:xs) (y:ys) =
  let accAfterLeft = foldInterleavings f acc xs (y:ys)
  in foldInterleavings f accAfterLeft (x:xs) ys

这个函数不会存储任何中间序列，每生成一个交错序列就用传入的f处理，处理完成后该序列即可被GC回收，内存占用始终维持在单个序列的大小。比如用它统计符合条件的序列数量：

countValid :: [Int] -> [Int] -> Int
countValid xs ys = foldInterleavings (\acc seq -> if sum seq > 10 then acc +1 else acc) 0 xs ys

方案2：惰性列表配合逐个处理 #

如果还是需要返回序列流，但不想驻留所有结果，可以利用Haskell的惰性列表特性，搭配mapM_这类逐个处理元素的函数：

interleavingsLazy :: [a] -> [a] -> [[a]]
interleavingsLazy [] ys = [ys]
interleavingsLazy xs [] = [xs]
interleavingsLazy (x:xs) (y:ys) = map (x:) (interleavingsLazy xs (y:ys)) ++ map (y:) (interleavingsLazy (x:xs) ys)

-- 逐个处理每个交错序列，处理完即丢弃
processSequences :: ([a] -> IO ()) -> [a] -> [a] -> IO ()
processSequences f xs ys = mapM_ f (interleavingsLazy xs ys)

interleavingsLazy生成的是惰性列表，mapM_会逐个取出序列处理，处理完一个才会生成下一个，不会把所有序列都加载到内存中。

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