笛卡尔积在Haskell中的列表列表中

Question

给定x所有子列表具有相同长度的长度列表列表y,输出包含每个子列表中的一个项目y^x的长度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中,因为它是我最熟悉的语言.

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

类型

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

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

笛卡尔积,扁平化和折叠

看看我的Ruby解决方案让我觉得充分利用这些功能可能足以解决问题.问题是虽然笛卡尔积输出了一个元组列表,但我需要一个列表列表.

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

这意味着我们基本上会评估列表monad中的每个操作.但是有一个功能:sequence :: Monad m => [m a] -> m [a].如果我们使用m ~ [],它的类型可以专门用于sequence :: [[a]] -> [[a]].

运用 sequence

我们最后得到了最后一个变体:

> allProduct :: [[a]] -> [[a]]
> allProduct = sequence

测试结果

我们使用快速检查,以测试它的可能是同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

:main在GHCi中使用,runhaskell或者编译和运行你的程序,最终你应该通过100次测试.