在 Haskell 中对列表的列表进行笛卡尔积

Question

给定一个列表，其中包含长度为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 解决方案，我认为这些函数的好处足以解决问题。问题在于，虽然笛卡尔积输出了一个元组列表，但我需要一个列表的列表。

- Caridorc

---

所有产品等于序列。 - Zeta

m 是列表类型的构造器 ([])，在这种情况下。如果需要，您可以始终使 allProduct 的类型更加具体化：allProduct = sequence :: [[a]] -> [[a]]。 - jub0bs

你尝试了什么？在搜索[[a]] -> [[a]]时，返回了sequence的结果。 - jub0bs

@Jubobs 我看到类型不完全相同，所以错误地认为它对我没有用处。我会学习在搜索Hoogle时也检查类似的类型，谢谢你的提示 :) - Caridorc

[[a]]比m [a]和[m a]更加具体，因为在sequence类型签名中，m代表任意的monad，但[]仅仅是Monad的一个实例。 - jub0bs

Answer 1

_{注意：本文使用可读性强的 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

这意味着我们基本上在评估列表单子中的每个操作。但是有一个函数可以做到这一点：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 个测试通过的结果。

- Zeta

---

我们使用QuickCheck来证明[...]，“证明”这个词太强了。那“增加我们的信心”如何？ - jub0bs

@Jubobs将其更改为“测试它很可能是相同的”更加诚实，我认为。但我同意，那不是一个“证明”。 - Zeta

这是一个很棒的答案。 - Chris Taylor

QuickCheck就像伪证明，相比Agda或Idris的正式证明。 - Erik Kaplun

sequence 是错误的，因为 sequence [] 是空的。 - PyRulez

@PyRulez allProduct []没有被OP定义，所以它是不明确的。话虽如此，Ruby代码最终在空列表上得到了nil，因此Haskell翻译没有有效的基本情况。答案中也提到了这种模棱两可的行为，尽管没有详细说明：“请注意，这个变体并不是100%正确的，因为allProduct []是[[]]”。询问OPallProduct []应该是什么。 ¯\(ツ)/¯ - Zeta