如何使用 Haskell 计算 2D 列表中给定元素周围 1 的数量？

Question

假设我有以下嵌套列表：

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

假设只给定 x 和 y 坐标 9。如何使用 Haskell 代码找出数字 9 周围有多少个 1？

让我再澄清一下，假设数字 9 位于 (0, 0)。 我想做的是：

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

(0,0) 周围的位置是以下坐标：

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

Answer 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

请注意，如果坐标位于边缘，则不会进行纠错。您可以通过在理解中添加更多条件来实现这一点。

如果数据变大，列表的列表就不是最有效的数据结构。您可以考虑向量或 Map (Int,Int) Int（特别是如果您有许多可以省略的零）。

[编辑]

这是一个稍微快一点的版本：

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     

首先我们“剪出”3 x 3 的正方形，然后我们对其进行所有计算。同样，边缘上的坐标会导致错误的结果。

Answer 2

编辑：切换为求和周围 8 而不是周围 4

您多久只需要一个条目的周围计数？如果您希望所有条目都如此，列表仍然表现得相当好，您只需从整体上看待它即可。

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

现在你可以下拉到 ghci 查看它的工作情况：

*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