Haskell中N个列表元素的所有组合

Question

为了合并 2 个列表，可以使用以下代码。

[(x,y) | x <- [1, 2, 3], y <- [4, 5, 6]]

或

(,) <$> [1,2,3] <*> [4,5,6]

产生

[(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]

在给定 N 个列表而不是 2 个列表的情况下，如何将它们以这种方式组合？

如果可能，最好使用列表理解，因为我发现它最容易解释。

Answer 1

sequence :: (Traversable t, Monad m) => t (m a) -> m (t a) 这样做：

> sequence [[1,2,3] , [4,5,6]]
[[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]]

> sequence [[1,2,3] , [4,5,6] , [7]]
[[1,4,7],[1,5,7],[1,6,7],[2,4,7],[2,5,7],[2,6,7],[3,4,7],[3,5,7],[3,6,7]]

虽然 Haskell 中没有任意长度的元组，因此必须使用 lists 来收集生成的“元组”。

sequenceA :: (Traversable t, Applicative f) => t (f a) -> f (t a)其实这里就够了，但是列表的applicative functor和monad是一样的，所以没关系。

如果任何列表可能是无限的，如果需要更公平的枚举，则必须采用一些对角化方案（参见 Cartesian product of infinite lists in Haskell 等）。

自己实现，必须用到递归，

ncart :: [[a]] -> [[a]]
ncart (xs:t) = [ x:r | x <- xs, r <- ncart t]
ncart []     = [[]]

（但请参阅 了解重要讨论）。