Haskell列表的嵌套笛卡尔积 [英] Nested cartesian product of Haskell lists

问题描述

我想创建一个方法，我可以给它一个长度列表，它会返回直到这些长度的所有笛卡尔坐标组合。更容易用一个例子来解释：

  cart [2,5] 
 Prelude> [[0,0]，[0,1]，[0,2]，[0,3]，[0,4]，[1,0]，[1,1]，[1,2]，[ 1,3]，[1,4]] 
 
购物车[2,2,2] 
前奏> [[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给了我一个动脉瘤！

解决方案对这个特定的问题会帮助我很多;我也喜欢在处理这样的东西时听到您的思维过程。 解决方案

这可以递归地解决。首先，笛卡儿式的产品是{∅}：

  cart [] = [[]] 
  

（或者如果空白产品无效，则定义1元素表单：

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

p>

然后， x：xs 的笛卡尔乘积可以写成

  cart（x：xs）= [i：rest | i < -  [0 .. x-1]，rest <-cart xs] 
  

---

一般来说，如果你要写一个需要列表长度的函数 f ，试着想办法让f（N）取决于较小的列表，例如只有f（N-1），然后解决基本情况 f（0）或 f（1）等。一个可以很容易解决的递归。

I would like to make a method where I could give it a list of lengths and it would return all combinations of cartesian coordinates up to those lengths. Easier to explain with an example:

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] ]

A simple list comprehension won't work because I don't know how long the lists are going to be. While I love Haskell's simplicity for many problems, this is one that I could write procedurally (in C or something) in 5 minutes whereas Haskell gives me an aneurysm!

A solution to this specific problem would help me out a lot; I'd also love to hear about your thought processes when tackling stuff like this.

解决方案

This can be solved recursively. First, the Cartesian product of nothing is {∅}:

cart [] = [[]]

(Or define just the 1-element form if the empty product is invalid:

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

)

Then, the Cartesian product of x:xs can be written as

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

---

In general, if you what to write a function f that requires the list's length N, try to think of a way to make f(N) depends on smaller lists e.g. f(N - 1) only, then solve the base case f(0) or f(1) etc. This transforms the problem into a recursion that can be easily solved.

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