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 则让我头疼！

解决这个特定问题的方案将对我非常有帮助；我也很想听听您处理此类问题时的思考过程。

- cspyr0

---

哇，感谢Kenny和Dave。我从未想到把递归调用放入列表理解式定义中-非常酷。使用map和fold的版本也很棒。我尽量在能想到方法时使用高阶函数，所以这是一个很好的学习例子！ - cspyr0

只要您使用高阶函数，就应该知道它不应该是晦涩难懂的。并且使用正确的函数有助于实现这一点，“sequence”就是您需要的。 - yairchu

感谢yairchu提供简洁明了的解决方案，也感谢他向我介绍了hoogle。没有它我怎么能做到这一点呢？！ - cspyr0

对于 ndmitchell 提供的另一个有趣工具，可以看看 hlint。正如 newacct 指出的那样，它建议进一步缩短我的解决方案。 - yairchu

Answer 1

嗯...

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

可以合理地期望库中已经存在一个 [[a]] -> [[a]] 的函数，其执行符合我们的期望。因此，如果不熟悉 sequence，只需通过 hoogling 找到它。

编辑：如 newacct 指出：

cart = mapM (enumFromTo 0 . subtract 1)

将先前的解决方案提供给HLint，也可以找到此内容。

- yairchu

---

cart = mapM (enumFromTo 0 . subtract 1) - newacct

@newacct: 好的，顺便说一句，hlint也建议这样做 :) - yairchu

哇，有趣的是，sequence . map (...) 已经深入人心成为这类问题的答案了，因为这也是我的最初反应。 - Reid Barton

Answer 2

这可以通过递归解决。首先，空集的笛卡尔积是 {∅}：

cart [] = [[]]

< p >（或者如果空的积不合法，则只定义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)等。这将把问题转换为可轻松解决的递归问题。

- kennytm

Answer 3

我打赌你的过程式解决方案将涉及递归。我们的Haskell解决方案也将涉及递归。

那么，递归。首先是递归情况。

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

在这里，我们只是说明对于每个可能的初始坐标和剩余长度的每个可能的笛卡尔坐标组合，我们会将该坐标与其余坐标结合起来。

然后是基本情况。

cart [] = [[]]

你可能会认为cart [] = []。我一开始也是这么想的。但是想一想递归情况需要从基本情况中得到什么。

- dave4420