Haskell列表的嵌套笛卡尔积

Question

我想制作一个方法,我可以给它一个长度列表,它将返回笛卡尔坐标的所有组合,直到这些长度.用例子更容易解释:

cart [2,5]
Prelude> [ [0,0],[0,1],[0,2],[0,3],[0,4],[1,0],[1,1],[1,2],[1,3],[1,4] ]

cart [2,2,2]
Prelude> [ [0,0,0],[0,0,1],[0,1,0],[0,1,1],[1,0,0],[1,0,1],[1,1,0],[1,1,1] ]

一个简单的列表理解将无法工作,因为我不知道列表将有多长.虽然我喜欢Haskell对于许多问题的简单性,但我可以在5分钟内编写程序(在C或其他东西),而Haskell给我一个动脉瘤!

这个特定问题的解决方案可以帮助我很多; 在处理这样的事情时,我也很想知道你的思维过程.

Answer 1

嗯..

cart = sequence . map (enumFromTo 0 . subtract 1)

期望[[a]] -> [[a]]函数执行我们期望的函数已经存在于库中是合理的.所以,如果一个不熟悉sequence,发现它是一个简单的事情hoogling它.

编辑:正如newacct所指出:

cart = mapM (enumFromTo 0 . subtract 1)

通过将先前的解决方案提供给HLint也可以找到这一点.

Answer 2

这可以递归地解决.首先,没有任何东西的笛卡尔积是{∅}:

cart [] = [[]]

(或者,如果空产品无效,则仅定义1元素形式:

cart [x] = [[i] | i <- [0 .. x-1]]

)

然后,笛卡尔积x:xs可以写成

cart (x:xs) = [i:rest | i <- [0 .. x-1], rest <- cart xs]

一般来说,如果你要写一个需要列表长度为N的函数f,试着想办法让f(N)依赖于较小的列表,例如f(N-1),然后求解基本情况f( 0)或f(1)等.这将问题转换为可以轻松解决的递归.

Answer 3

我打赌你的程序解决方案会涉及递归.我们的Haskell解决方案也将涉及递归.

所以,递归.首先是递归案例.

cart (c : cs) = [i : r | i <- [0 .. c-1], r <- rcart]
  where rcart = cart cs

在这里,我们只是说,对于每个可能的初始坐标,并且从剩余的长度笛卡尔坐标的每个可能的组合,我们做的统筹与剩余的坐标相结合的明显的事情.

然后是基础案例.

cart [] = [[]]

你可能会想cart [] = [].我起初做了.但想想基本案例中递归案例需要什么.