笛卡尔积在Haskell的列表中 [英] Cartesian product over a list of lists in Haskell

问题描述

给出一个长度为 x 的列表列表，其中所有子列表的长度都为 y ，输出 y ^ x 长度为 x 的列表，其中每个子列表中包含一项。

Given a list of lists of length x where all the sublists have the same length y, output the y^x lists of length x that contain one item from each sublist.

示例（ 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中，因为它是我最熟悉的语言。

I wrote actual code to perform this task, but in Ruby, as it is the language I am most comfortable with.

def all_combinations(lst)
   lst.inject {|acc, new| acc.product(new).map(&:flatten) }
end

类型

输入是包含a类型项的列表列表，输出也是如此。

Input is a list of lists that contains items of type a and so is the output.

allProduct :: [[a]] -> [[a]]

笛卡尔积，展平和折叠

看看我的Ruby解决方案，我认为充分利用这些功能可能足以解决问题。问题是，虽然笛卡尔乘积输出一个元组列表，但是我需要一个列表列表。

Looking at my Ruby solution makes me think that a good use of these functions may be enough to solve the problem. The problem is that while the Cartesian Product outputs a list of tuples but I need a list of lists.

推荐答案

<sub>注意：这篇文章是用识字的Haskell写的。将其另存为
* .lhs并将其加载到GHCi中。</sub>

> -- remove this line if you don't have QuickCheck installed
> import Test.QuickCheck 

---

一个简单的递归变量

让我们从 allProduct 的简单变体开始：

> allProductFirst :: [[a]] -> [[a]]
> allProductFirst []     = [[]]
> allProductFirst (x:xs) =

现在 x 本身是一个再次列出。假设 allProduct xs 会给我们其他列表的结果。

Now x itself is a list again. Let's say that allProduct xs would give us the product of the other lists.

>    let rest = allProductFirst xs

我们需要做什么？我们需要为 x 中的每个元素创建一个新列表，并将它们连接在一起：

What do we need to do? We need to create a new list for every element in x and concat them together:

>    in concatMap (\k -> map (k:) rest) x

请注意，此变体不是100正确的百分比，因为 allProduct [] 是 [[]] 。

Note that this variant isn't 100% correct, as allProduct [] is [[]].

如果我们使用 [] << c $ c> Monad 实例，会是什么样子？ / code>？

How would this look like if we were to use the Monad instance of []?

> allProduct' :: [[a]] -> [[a]]
> allProduct' []     = [[]]
> allProduct' (x:xs) = do

我们要获取 x的每个元素

>      elementOfX <- x

并将其限制在我们的列表可以包含的所有可能的后缀中：

and cons it onto all the possible suffixes our list can have:

>      rest       <- allProduct' xs
>      return $ elementOfX : rest

这意味着我们基本上是在评估列表monad中的每个动作。但这有一个功能： sequence :: Monad m => [马]-> m [a] 。如果我们使用 m〜[] ，则其类型可以专用于 sequence :: [[a]]-> [[a]] 。

This means we're basically evaluation every action inside our list monad. But there's a function for that: sequence :: Monad m => [m a] -> m [a]. If we use m ~ [], its type can be specialized to sequence :: [[a]] -> [[a]].

我们以最后一个变体结尾：

We end up with our last variant:

> 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个通过的测试。

Use :main in GHCi, runhaskell or compile and run your program, and you should end up with 100 passed tests.

这篇关于笛卡尔积在Haskell的列表中的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！