How to count the number of 1's surrounding a given element in a 2D list with Haskell?

Suppose I have the following nested list:

list =   
  [[0, 1, 0],  
   [1, 9, 1],  
   [1, 1, 0]]

Assuming you are only given the x and y coordinate of 9. How do I use Haskell code to find out how many 1's surrounds the number 9?

Let me clarify a bit more, assume the number 9 is positioned at (0, 0). What I am trying to do is this:

int sum = 0;
for(int i = -1; i <= 1; i++){
  for(int j = -1; j <= 1; j++)开发者_运维问答{
    if(i == 0 || j == 0) continue;
    sum += list[i][j];
  }
}

The positions surrounding (0,0) are the following coordinates:

 (-1, -1) (0, -1) (1, -1)
 (-1,  0)         (1,  0)
 (-1,  1) (0,  1) (1,  1)  

---

list = [[0,1,0],[1,9,1],[1,1,0]]
s x y = sum [list !! j !! i | i <- [x-1..x+1], j <- [y-1..y+1], i /= x || j /= y]
--s 1 1 --> 5

Note that I there is no error correction if the coordinates are at the edge. You could implement this by adding more conditions to the comprehension.

A list of lists isn't the most efficient data structure if things get bigger. You could consider vectors, or a Map (Int,Int) Int (especially if you have many zeros that could be left out).

[Edit]

Here is a slightly faster version:

s x y xss = let snip i zs = take 3 $ drop (i-1) zs 
                sqr = map (snip x) $ snip y xss
            in sum (concat sqr) - sqr !! 1 !! 1     

First we "snip out" the 3 x 3 square, then we do all calculations on it. Again, coordinates on the edges would lead to wrong results.

---

Edit: switched to summing surrounding 8 rather than surrounding 4

How often do you just want the surrounding count for just one entry? If you want it for all the entries, lists still perform fairly well, you just have to look at it holistically.

module Grid where
import Data.List (zipWith4)

-- given a grid A, generate grid B s.t.
-- B(x,y) = A(x-1,y-1) + A(x,y-1) + A(x+1,y-1)
--        + A(x-1,y)              + A(x+1,y)
--        + A(x-1,y+1) + A(x,y+1) + A(x+1,y+1)
-- (where undefined indexes are assumed to be 0)
surrsum :: [[Int]] -> [[Int]]
surrsum rs = zipWith3 merge rs ([] : init rs') (tail rs' ++ [[]])
  where -- calculate the 3 element sums on each row, so we can reuse them
        rs'            = flip map rs $ \xs -> zipWith3 add3 xs (0 : xs) (tail xs ++ [0])
        add3 a b c     = a+b+c
        add4 a b c d   = a+b+c+d
        merge [] _  _  = []
        -- add the left cell, right cell, and the 3-element sums above and below (zero-padded)
        merge as bs cs = zipWith4 add4 (0 : init as) (tail as ++ [0]) (bs ++ repeat 0) (cs ++ repeat 0)

-- given a grid A, replace entries not equal to 1 with 0
onesOnly :: [[Int]] -> [[Int]]
onesOnly = map . map $ \e -> if e == 1 then 1 else 0

list :: [[Int]]
list = [[0, 1, 0]
       ,[1, 9, 1]
       ,[1, 1, 0]]

Now you can drop down to ghci to see it work:

*Grid Control.Monad> mapM_ (putStrLn . unwords . map show) list
0 1 0
1 9 1
1 1 0
*Grid Control.Monad> mapM_ (putStrLn . unwords . map show) $ onesOnly list
0 1 0
1 0 1
1 1 0
*Grid Control.Monad> mapM_ (putStrLn . unwords . map show) . surrsum $ onesOnly list
2 2 2
3 5 2
2 3 2