两个范围的所有组合作为包含两个索引的元组的列表

Question

例如，给定一个元组(2, 3)作为参数，它应该返回[(0,0), (0,1), (0,2), (1,0), (1,1), (1,2)]，虽然可以是任意顺序

这是我想出的代码，但它没有返回正确的结果，谁能给一个更好的解决方案或想法?

getAll :: (Int, Int) —> [(Int,Int)] 
getAll (x,y) 
| x == 0 && y == 0 = [(0,0)] 
| x == 1 && y == 1 = [(1,1)] 
| 0 + 1 < x && 0 + 1 < y 
= (0,0) : getAll (x+1, y+1) 

更新:

getAll :: (Int, Int) -> [(Int,Int)]
getAll (x,y) = case (x,y) of
(0,0) -> [(0,0)]
(1,1) -> [(0,0)]
(0, y) -> (0, y-1) : getAll (0, y-1)
(x, 0) -> (x-1, 0) : getAll (x-1, 0)    

我尝试将其计算为两种情况，但我有一个问题，即当我输入例如(0,3)时，它将输出[(0,2), (0,1), (0,0), (0,0)]。我知道为什么这将输出(0,0)两次，但我不知道如何解决它，你可以通过我的代码，看看问题在哪里?

Answer 1

我能想到的一种简洁的实现方法是使用列表推导式:

getAll :: (Int, Int) -> [(Int,Int)]
getAll (x, y) = [(a, b) | a <- [0..x-1], b <- [0..y-1]]

如果你必须用递归来解决它:

getAll :: (Int, Int) -> [(Int,Int)]
getAll (x, y) = go 0 0 where
go x' y'
| x' == x            = []
| y' == y            = go (x'+1) 0
| otherwise          = (x', y') : go x' (y'+1)

Answer 2

你写

getAll (x,y) 
| x == 0 && y == 0 = [(0,0)] 

到目前为止一切顺利。

| x == 1 && y == 1 = [(1,1)] 

，这已经错了。它应该产生[(0,0), (0,1), (1,0), (1,1)]。

从描述中可以清楚地看出。两个Int定义了两个范围

[ (i,j) | i <- [0..x-1], j <- [0..y-1]]

这被称为列表推导式。实际上，这段代码就是你的函数所需要的。也不需要检测任何病例。它会工作的。

---

但是这是什么意思呢?从视觉上看，它创建了从0到x的is和从0到y的js的所有配对列表。

还有很多其他的编码方法，但最终，它是关于枚举矩形中的单元格

j   0  1  2  ........   y-1
i
0     *  *  *  *  *  *  *  *
1     *  *  *  *  *  *  *  *
2     *  *  *  *  *  *  *  *
.     *  *  *  *  *  *  *  *
.     *  *  *  *  *  *  *  *
x-1    *  *  *  *  *  *  *  *

可以用伪代码表示为两个嵌套循环:

for  i  in  0 .. x-1 :
for  j  in  0 .. y-1 :
produce  (i,j)

嵌套循环可以展开成一个循环序列:

for  i=0  and  j  in  0 .. y-1 : produce  (i,j)
for  i=1  and  j  in  0 .. y-1 : produce  (i,j)
for  i=2  and  j  in  0 .. y-1 : produce  (i,j)
..............
for  i=x-1 and j  in  0 .. y-1 : produce  (i,j)

以上可以表示为一个循环，在达到极限后重置j值，同时推进i值…这就是其他答案中的递归版本所做的，一个接一个地生成对，并将它们放入:的输出列表中。嵌套循环通常在Haskell中编码为concatMaps，生成一个接一个(逐行)的列表，并将它们与++而不是:组合在一起....

很多代码的方法。但最终它是关于跟踪正方形(矩形，无论什么):

concat                              -- concat 
[ [ (i , j)                     --   [ map (i ,)  
| j <- [0..y-1] ]        --               [0..y-1]
| i <- [0..x-1] ]            --       |  i <-  [0..x-1] ]
==
[ (0,j) | j <- [0..y-1] ]  ++
[ (1,j) | j <- [0..y-1] ]  ++
[ (2,j) | j <- [0..y-1] ]  ++
............
[ (x-1,j) | j <- [0..y-1] ] 

你可以看到其实都是一样的。

我们甚至可以通过对角线来追踪它。

Answer 3

递归函数最终应该终止，但只在(0, 0)或(1, 1)的情况下终止。如果x和y大于1，则进行递归调用，其中增加x和y，因此这永远不会终止。其他情况被忽略，因此(0, 1)将会引发一个错误。

您可以使用以(0, 0)开头的辅助函数，每次递增y-坐标，直到该坐标大于或等于上界。在这种情况下，我们使用asy-坐标0进行递归调用，并增加x坐标。如:

getAll :: (Int, Int) -> [(Int, Int)]
getAll (xn, yn) = go (0, 0)
where go (x, y)
| x >= xn = []  -- terminate, we reached the end
| y >= yn = go (x + 1, 0)  -- increment x, set y to 0
| otherwise = (x, y) : go (x, y + 1) -- yield and increment y

由于项可以以任何顺序返回，另一种策略是递减值，从而将y(或x)设置为初始的y(或x)，并递减另一个坐标(y或x)，直到两者都为零，因此:

getAll :: (Int, Int) -> [(Int, Int)]
getAll t@(_, yn) = go t
where go (x, y) 
| x < 0 = []
| y < 0 = go (x-1, yn)
| otherwise = (x, y) : go (x, y-1)

但是，您可以使用列表推导式或列表的Applicative实例以更紧凑的方式生成此结果。例如:

getAll :: (Int, Int) -> [(Int, Int)]
getAll (x, y) = (,) <$> [0 .. x-1] <*> [0 .. y-1]

这里f <$> xs <*> ys将构造一个列表，对于xs和ys中的每个项目的组合，我们调用f。因此，对于xs中的元素xi和ys中的元素yi的每个组合，我们将其称为(,) xiyi，这是(xi, yi)的更规范形式