Get all possible neighbour coordinates

user_14861341 0
Viewed 144

I represented a 3D coordinate with a tuple of type (Int, Int, Int)

To get the direct neighbours of a coordinate I did something like this :

neighbours (x,y,z) =
    [(x',y',z') | x' <- [(x-1)..(x+1)], y' <- [(y-1)..(y+1)], z' <- [(z-1)..(z+1)], (x,y,z) /= (x',y',z')]

Now, I need to use 4D coordinates too, I could do something very similar to get the neighbours with a tuple of 4 elements and it would work. But, I would need to duplicate all the functions I did for the 3D coordinates, this time for 4D coordinates.

To avoid this, I thought of basically replacing tuples with a list of Int, now for a 3D coordinate it would be for example [9, 3, 0] and a 4D coordinate [5, 1, 0, 1] and so on.

How can I get the neighbours with an array of Int ? I tried using list comprehension but I failed finding a solution.

PS: I am new to Haskell and functional programming

combinations functional-programming haskell
1 Answers

You could proceed recursively, and implement (N+1)-D neighbours in terms of N-D neighbours.

Essentially, if you have a (N+1)-D point [x1,...,xNplus1] this is of the form x1 : xs where xs is an N-D point. So, if you already know the list of neighbours of xs, you can turn that into the list of neighbours of x1 : xs.

Here's a simple attempt, which should almost work.

almostNeighbours :: [Int] -> [[Int]]
almostNeighbours []     = [[]]
almostNeighbours (x:xs) =
   [ x' : xs'
   | x' <- [x-1 .. x+1] , xs' <- almostNeighbours xs ]

Note that we do include the point itself in the list of neighbours. Failing to do so would not produce enough points in the recursive case. (I recommend convincing yourself this is indeed the case.)

If you do not want the point itself, you can always remove it later using an additional function, without affecting the recursive definition.

Finally, note that the code above probably won't be as fast as your original one, since lists are slower to access than tuples.

Minor alternative: using applicative style we can shorten the code slightly.

almostNeighbours :: [Int] -> [[Int]]
almostNeighbours []     = pure []
almostNeighbours (x:xs) = (:) <$> [x-1 .. x+1] <*> almostNeighbours xs
user_32349590
Related