Haskell 中的笛卡尔列表乘积（内存和速度）

Question

我正在尝试cart :: [[a]] -> [[a]]为笛卡尔积编写一个通用函数，以便生成从 0 到 7 的 9 元组数字集（9 个元素的列表，而不是实际的 9 元组）。我已经编写了几个语法相似的函数，但它们的性能却大不相同。

cart :: [[a]] -> [[a]]
cart [] = [[]]
cart (xs:xss) = [x:ys | x <- xs, ys <- cart xss]

cart' :: [[a]] -> [[a]]    -- Reverse binding
cart' [] = [[]]
cart' (xs:xss) = [x:ys | ys <- cart' xss, x <- xs]

xs = [0..7]

length $ cart $ replicate 9 xs    -- This is slow (4.1s) and memory hungry (1916MB total); ~75% garbage collection time
length $ sequence $ replicate 9 xs    -- Treating list as a monad; this is even slower (12s) and worse on memory (4214MB); ~75% garbage collection time
length $ cart' $ replicate 9 xs    -- This is slightly faster (3.4s), and uses very little memory (2MB); ~1.5% garbage collection time
length [[a,b,c,d,e,f,g,h,i] | a <- xs, b <- xs, c <- xs, d <- xs, e <- xs, f <- xs, g <- xs, h <- xs, i <- xs]    -- This is ultra-fast (0.5s) and uses virtually no memory (1MB); 0% garbage collection time

有没有办法编写一个通用的笛卡尔积函数，它的速度和内存效率与第四个实现大致相同？更重要的是，为什么这些实现差异如此之大？

类似线程