All combinations of two ranges as a list of tuples of two indices-CodePudding

For example, given a tuple (2, 3) as an argument, it should return [(0,0), (0,1), (0,2), (1,0), (1,1), (1,2)], though it can be in any order.

This is the code I came up with, however it doesn't return the correct result, could anyone give a better solution or idea?

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)

update:

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)

I try to computing it into two situations, but I have a problem that when I input for example (0,3), it will output [(0,2), (0,1), (0,0), (0,0)]. I know why this will output (0,0) two times, but I don't know how to solve it, could you look through my code and see where is the problem?

CodePudding user response：

A clean way to implement this that I can think of is by using list comprehensions:

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

If you have to solve it with recursion:

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)

CodePudding user response：

You write

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

so far so good.

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

and this is already wrong. It should produce [(0,0), (0,1), (1,0), (1,1)].

This is clear from the description. The two Ints define two ranges,

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

This is known as List comprehensions. And in fact this code is all you need to have in your function. No need to test for any cases either. It will just work.

But what does it mean? Just as it seems to be, visually, it creates a list of all pairings of is from 0 upto x and js from 0 upto y.

There's lots of other ways to code this, but ultimately, it is about enumerating the cells in the rectangle

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

It can be expressed in pseudocode as two nested loops:

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

The nested loops can be unrolled into a sequence of loops:

    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)

The above can be expressed as one loop which resets the j value after reaching the limit while advancing the i value... Which is what the recursive versions in other answers are doing, producing the pairs one by one and placing them into the output list with :. The nested loops are usually coded in Haskell as concatMaps, producing the lists one by one (row by row) and combining them with instead of :....

Lots of ways to code this. But ultimately it's about tracing that square (rectangle, whatever):

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

You can see how it's all the same thing really.

And we could even trace it by diagonals.

CodePudding user response：

Your recursive function should eventually terminate, but you only terminate in case of (0, 0) or (1, 1). In case x and y are greater than one, then you make a recursive call where you increment both x and y, and this thus can never terminate. Other cases are ignored and thus (0, 1) will for example raise an error.

What you can do is work with a helper function that starts with (0, 0), and each time increments the y-coordinate until that coordinate is greater than or equal to the upper bound. In that case we make a recursive call with as y-coordinate zero, and increment the x coordinate. Like:

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

Since the items can be returned in any order, another strategy is to decrement the values, and thus set y (or x) back to the initial y (or x) and decrement the other coordinate (y or x) until both hit zero so:

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)

You can however make use of list comprehensions or the Applicative instance of a list to produce this result in a more compact way. For example with:

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

here f <$> xs <*> ys will construct a list where we call f for each combination of items from xs and ys. We thus will for each combination of an element x_i from xs and each element y_i from ys, call (,) x_i y_i which is a more canonical form of (x_i, y_i)