Haskell 中列表列表的笛卡尔积
Cartesian product over a list of lists in Haskell
给定一个长度为 x 的列表列表，其中所有子列表具有相同的长度 y，输出包含一个项目的长度为 x 的 y^x 个列表来自每个子列表。
示例（x = 3、y = 2）：
[ [1, 2], [3, 4], [5, 6] ]
输出（2^3 == 8 不同的输出）：
[ [1, 3, 5], [1, 4, 5], [1, 3, 6], [1, 4, 6],
[2, 3, 5], [2, 4, 5], [2, 3, 6], [2, 4, 6] ]
我的研究/工作
Ruby
我编写了实际代码来执行此任务，但使用的是 Ruby，因为这是我最熟悉的语言。
def all_combinations(lst)
lst.inject {|acc, new| acc.product(new).map(&:flatten) }
end
类型
输入是包含类型 a 的列表的列表，输出也是。
allProduct :: [[a]] -> [[a]]
笛卡尔积，展平折叠
看着我的 Ruby 解决方案，我认为好好利用这些功能可能足以解决问题。问题是虽然笛卡尔积输出元组列表，但我需要列表列表。
注：这个post是写文的Haskell。另存为
*.lhs 并将其加载到 GHCi 中。
> -- remove this line if you don't have QuickCheck installed
> import Test.QuickCheck
一个简单的递归变体
让我们从 allProduct 的简单变体开始：
> allProductFirst :: [[a]] -> [[a]]
> allProductFirst [] = [[]]
> allProductFirst (x:xs) =
现在x本身又是一个列表。假设 allProduct xs 会给我们其他列表的乘积。
> let rest = allProductFirst xs
我们需要做什么？我们需要为 x 中的每个元素创建一个新列表并将它们连接在一起：
> in concatMap (\k -> map (k:) rest) x
请注意，此变体并非 100% 正确，因为 allProduct [] 是 [[]]。
单子变体
如果我们使用 [] 的 Monad 实例会是什么样子？
使用do表示法
> allProduct' :: [[a]] -> [[a]]
> allProduct' [] = [[]]
> allProduct' (x:xs) = do
我们要获取 x
的每个元素
> elementOfX <- x
并将其添加到我们的列表可能包含的所有可能后缀中：
> rest <- allProduct' xs
> return $ elementOfX : rest
这意味着我们基本上是在评估列表 monad 中的每个动作。但是有一个函数：sequence :: Monad m => [m a] -> m [a]。如果我们使用m ~ []，它的类型可以特化为sequence :: [[a]] -> [[a]].
使用sequence
我们以最后一个变体结束：
> allProduct :: [[a]] -> [[a]]
> allProduct = sequence
测试结果
我们使用 QuickCheck 来测试它可能与 allProductFirst 相同
和 allProduct':
> main :: IO ()
> main = do
> quickCheck $
> forAll (choose (1,8)) $ \n -> -- number of lists
> forAll (choose (1,4)) $ \s -> -- number of elements per list
> forAll (vectorOf n $ vector s) $ \xs ->
> allProduct' xs === allProduct (xs :: [[Integer]]) .&.
> allProductFirst xs === allProduct xs
在 GHCi 中使用 :main，runhaskell 或编译并 运行 你的程序，然后你
最终应该有 100 个通过测试。
给定一个长度为 x 的列表列表，其中所有子列表具有相同的长度 y，输出包含一个项目的长度为 x 的 y^x 个列表来自每个子列表。
示例（x = 3、y = 2）：
[ [1, 2], [3, 4], [5, 6] ]
输出（2^3 == 8 不同的输出）：
[ [1, 3, 5], [1, 4, 5], [1, 3, 6], [1, 4, 6],
[2, 3, 5], [2, 4, 5], [2, 3, 6], [2, 4, 6] ]
我的研究/工作
Ruby
我编写了实际代码来执行此任务，但使用的是 Ruby，因为这是我最熟悉的语言。
def all_combinations(lst)
lst.inject {|acc, new| acc.product(new).map(&:flatten) }
end
类型
输入是包含类型 a 的列表的列表，输出也是。
allProduct :: [[a]] -> [[a]]
笛卡尔积，展平折叠
看着我的 Ruby 解决方案，我认为好好利用这些功能可能足以解决问题。问题是虽然笛卡尔积输出元组列表，但我需要列表列表。
注：这个post是写文的Haskell。另存为 *.lhs 并将其加载到 GHCi 中。
> -- remove this line if you don't have QuickCheck installed
> import Test.QuickCheck
一个简单的递归变体
让我们从 allProduct 的简单变体开始：
> allProductFirst :: [[a]] -> [[a]]
> allProductFirst [] = [[]]
> allProductFirst (x:xs) =
现在x本身又是一个列表。假设 allProduct xs 会给我们其他列表的乘积。
> let rest = allProductFirst xs
我们需要做什么？我们需要为 x 中的每个元素创建一个新列表并将它们连接在一起：
> in concatMap (\k -> map (k:) rest) x
请注意，此变体并非 100% 正确，因为 allProduct [] 是 [[]]。
单子变体
如果我们使用 [] 的 Monad 实例会是什么样子？
使用do表示法
> allProduct' :: [[a]] -> [[a]]
> allProduct' [] = [[]]
> allProduct' (x:xs) = do
我们要获取 x
> elementOfX <- x
并将其添加到我们的列表可能包含的所有可能后缀中：
> rest <- allProduct' xs
> return $ elementOfX : rest
这意味着我们基本上是在评估列表 monad 中的每个动作。但是有一个函数：sequence :: Monad m => [m a] -> m [a]。如果我们使用m ~ []，它的类型可以特化为sequence :: [[a]] -> [[a]].
使用sequence
我们以最后一个变体结束：
> allProduct :: [[a]] -> [[a]]
> allProduct = sequence
测试结果
我们使用 QuickCheck 来测试它可能与 allProductFirst 相同
和 allProduct':
> main :: IO ()
> main = do
> quickCheck $
> forAll (choose (1,8)) $ \n -> -- number of lists
> forAll (choose (1,4)) $ \s -> -- number of elements per list
> forAll (vectorOf n $ vector s) $ \xs ->
> allProduct' xs === allProduct (xs :: [[Integer]]) .&.
> allProductFirst xs === allProduct xs
在 GHCi 中使用 :main，runhaskell 或编译并 运行 你的程序，然后你
最终应该有 100 个通过测试。