扫雷板标签（初级）

我们得到了一份家庭作业，其中我们得到了一个类似扫雷的样本板，其中有空格而不是数字（板是[String]形式）并且已经放置了地雷。我们需要的是创建一个函数，用数字替换所有空格，数字等于相邻地雷的数量。

除了删除所有带零的空格之外，我无法取得任何真正的进展，这可能根本没有任何用处。我还遇到了 Char 类型的零的问题，这使我无法向其添加例如 +1 。如果可以在没有高级功能的情况下解决这个问题，那就太好了，这样我就可以理解它，但任何解决方案或至少解决方案的想法都可以。

这就是代码开头的样子。

import Data.Char

type Result = [String]

pp :: Result -> IO ()
pp x = putStr (concat (map (++"\n") x)) --prints strings in a column.


sampleInput = ["       ",
               " *     ",
               "    *  ",
               "   *   ",
               "      *",
               "***    ",
               "* *    ",
               "***    "]

minesweeper :: Result -> Result

结果应该是这样的

Prelude>pp(minesweeper sampleInput)
1110000
1*11110
1122*10
001*221
233211*
***2011
*8*3000
***2000

我非常高兴得到任何指导，因为我无法取得任何真正的进展。

更新：做了一些不同但相似的解决方案。您可以查看相关问题here https://stackoverflow.com/questions/58827023/how-to-make-my-function-move-through-two-lists-at-once/58836932#58836932

你在这里需要的叫做“模板卷积”。看这张图片：

111
1x1
111

这是你的模板。在游戏板上选择一个图块，然后将模板放在该图块的顶部。 多少1s 覆盖地雷，我们应该在此图块中显示该数字。例如：

       .....   .....
111    .*...   .....
1x1  + ..x*. = ..3..
111    ...*.   .....
       .....   .....

一旦我们将这个操作应用到整个板上，我们就基本上完成了。

有一些高级设备可以实现此目的，例如 comonad 和数组，但出于本文的目的 我会让事情变得简单，所以我们将以最简单的类型手工起草所有内容。我 我还将在代码中留下一些空白，以便读者不那么无聊。如果你 使能够-fdefer-typed-holes https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/glasgow_exts.html#typed-holes，你可以把类似的东西_wut代替... and ghc会告诉您它认为孔的类型应该是什么。

1. 我想处理数字，而不是字符：正如你所指出的，字符 不适合算法工作。转换应该是两种方式，这样我们就可以显示我们的 结果也是如此。

   charsToInts :: [[Char]] -> [[Int]]
   charsToInts = (fmap . fmap) charToInt
     where
       charToInt '*' = ...
       charToInt ... = ...
   
   intsToChars :: [[Int]] -> [[Char]]
   intsToChars = ...
   

2. 嵌套列表不是一种使用起来很舒服的类型。我们将定义一些辅助函数 让事情变得更容易。我们肯定需要的操作是“索引”，即访问 元素按其索引 - 如果它首先存在。

   lookup2DMaybe :: [[a]] -> (Int, Int) -> Maybe a
   lookup2DMaybe u (i, j) = do
       xs' <- lookupMaybe xs  i
       x   <- ...
       return x
     where
       lookupMaybe :: [a] -> Int -> Maybe a
       lookupMaybe xs i
           | 0 <= i && i < length xs = ...
           | ...                     = ...
   

3. 现在，介绍一些有趣的东西——模板应用。

   applyStencil :: [[Int]] -> (Int, Int) -> Int
   applyStencil u = sum . Data.Maybe.catMaybes . fmap (... u) . stencil
     where
       stencil :: (Int, Int) -> [(Int, Int)]
       stencil (i, j) = [ (i + di, ...) | di <- ..., dj <- ..., (di, dj) /= ... ]
   

   这有效吗？

   λ applyStencil (charsToInts sampleInput) (3, 5)
   2
   λ applyStencil (charsToInts sampleInput) (6, 1)
   8
   

4. 剩下要做的就是"map"雷区周围都有模板。为此，我们 将生成一个板，其中每个点的坐标都被写入。我希望在某个地方 您将会明白原因的方式。

   indices :: [[a]] -> [[(Int, Int)]]
   indices u = [ [ ... | ... ] | ... ]
   

   这里的想法是，我们给它一个任何东西的板，它创建一个坐标板 相同的尺寸。

5. 考虑一下我们目前拥有的类型：

   λ :type applyStencil (charsToInts sampleInput) 
   applyStencil (charsToInts sampleInput) :: (Int, Int) -> Int
   

   所以，这是一个将坐标转换为这些周围的地雷数量的函数 坐标。如果我们将它映射到坐标板上会发生什么？

   fill :: [[Int]] -> [[Int]]
   fill u = (fmap.fmap) (... u) (... u)
   
   λ intsToChars (fill (charsToInts sampleInput))
   ["1110000","1011110","1122110","0011221","2332110","2422011","4843000","2422000"]
   

   看起来不错，不是吗？

6. 只剩下一些小事情要做：给定两块字符板，将它们重叠起来。这在对另一个问题的回答 https://stackoverflow.com/a/58685116关于列表的列表。（我们收到很多这样的问题 有点晚了。向 Stack Overflow Haskell 教师助理的教授问好 团队！）

7. 最终解决方案！

   minesweeper x = overlay x (intsToChars . fill . charsToInts $ x)
   

   一点也不难！

有一些方法可以改进此代码：

1. 为电路板创建专门的类型，以便只能构建正确的电路板。
2. 为该类型定义一个comonad。
3. 彻底删除类型并将代码概括为 Store comonad。
4. 使用高效的数组处理。

但我们探索的想法是持久的。

一些进一步阅读：

1. 模板卷积的基础知识。 https://jaspervdj.be/posts/2014-11-27-comonads-image-processing.html
2. 使用标准 comonad 类型。 http://blog.ielliott.io/comonad-transformers-in-the-wild/
3. 模板卷积的高级优化。 https://www.microsoft.com/en-us/research/wp-content/uploads/2016/07/Stencil.pdf

让我知道事情的后续！