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

Question

这个问题在这里已经有了答案:





Calculate n-ary Cartesian Product

(6 个回答)


7 个月前关闭。




为了组合 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 中没有任意长度的元组，因此必须使用列表来收集生成的“元组”。
sequenceA :: (Traversable t, Applicative f) => t (f a) -> f (t a) 实际上在这里就足够了，但是列表的应用仿函数和 monad 是一样的，所以没关系。
如果任何列表可能是无限的，如果需要更公平的枚举，则必须采用一些对角化方案(参见例如 Cartesian product of infinite lists in Haskell 等)。
要自己实现，必须使用递归，

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

(但请参阅 haskell running out of memory with finite lists 进行重要讨论)。