CODEWITHSUNDEEP
haskell
whd
whd

Reputation: 1861

neighbours in 2dm matrix represented as list of list

Well I can't figure out how I could make it in haskell. For example, I have such matrix

[[1,2],[3,4]]

and I want to generate a list of lists with all possible neighbours of each element for this matrix.

Expected result is:

[[1,2],[1,3],[1,4],[2,1],[2,3],[2,4],[3,1],[3,2],[3,4],[4,1],[4,2],[4,3]]

I know how to make function which will create list of list with cords of neighbours of each cell:

pos how = [ (0+dx,0+dy) | dx <- [0..(how-2)], dy <- [0..how-1] ] :: [(Int,Int)]
neighbour (x,y) how = [ (x+dx,y+dy) | dy <- [-1..1], dx <- [-1..1],
                                      x+dx >= 0, y+dy >= 0, x+dx<=how-2, y+dy <= how-1,
                                      (x,y)/=(x+dx,y+dy) ] :: [(Int,Int)]
all_n how = [ p | x <- pos how, let p = neighbour x how ] :: [[(Int,Int)]]

but I can't change it to work as I described.

Upvotes: 0

Views: 1328

Answers (2)

Daniel Wagner
Daniel Wagner

Reputation: 152707

To correct the code you have now, I provide a few questions for which a thoughtful answer may help you make progress:

  • how-2 is a strange thing. Why is 2 the right number to subtract?
  • The type of all_n is quite strange. Why is it a function? (What does its argument represent?) Why does it return a nested list, rather than a flat one?
  • It seems you're tracking only one size parameter, but your matrix is a two-dimensional matrix. Why is there such a discrepancy? (Why don't you have both a width and height parameter?)
  • Once you have a coordinate, do you know how to fetch the element at that position from the matrix? (Hint: there is a function (!!) :: [a] -> Int -> [a].) If you have a list of coordinates, do you know how to do this for each element in the list? (Hint: there is a function map :: (a -> b) -> ([a] -> [b]).)

Good luck!

Upvotes: 1

Daniel Wagner
Daniel Wagner

Reputation: 152707

Let me sketch a very different approach to the one you suggested. When talking about neighbors, I'll say a d-neighbor of e is the element one step in direction d from element e. So, for example, in the matrix [[1,2],[3,4]], the number 2 is a right-neighbor of number 1. We'll need to use some library code.

import Data.List

We'll start from the very simplest thing: let's just find right-neighbors of a one-dimensional list.

rightList (x:y:rest) = (x,y) : rightList (y:rest)
rightList _ = []

We can find all the right-neighbors in a matrix by nondeterministically choosing a row of the matrix and finding all right-neighbors in that row.

right m = m >>= rightList

We can take any function for finding neighbors and create the function for finding neighbors in the other direction by reversing the tuples. For example, left neighbors are the same as right neighbors, but with the tuple elements swapped, so:

swap (x,y) = (y,x)
co direction = map swap . direction
left = co right

What about down-neighbors? Actually, down-neighbors are just right-neighbors in the transposed matrix:

down = right . transpose
up   = co down

The next direction of interest are down-right-neighbors. This one is a little trickier; what we're going to do is walk down two lists in parallel, but offset by one.

downRight (xs:ys:rest) = zip xs (drop 1 ys) ++ downRight (ys:rest)
downRight _            = []
upLeft = co downRight

There's one final direction, namely up-right-neighbors; these are down-right-neighbors if we flip the matrix upside down.

upRight  = downRight . reverse
downLeft = co upRight

Finally, to form all neighbors, we can nondeterministically choose a neighboring direction, then find all neighbors in that direction.

allDirections = [right, left, up, down,
                 downRight, upLeft, upRight, downLeft]
neighbors m = allDirections >>= ($m)

The output isn't in exactly the order you specified, but I imagine this may not matter so much.

Upvotes: 6

Related Questions