haskell - 为地下城 map 选择什么数据类型

Question

作为编码挑战的一部分，我必须实现地下城 map 。

我已经使用 Data.Map 设计了它作为设计选择，因为不需要打印 map ，有时我必须更新 map 图 block ，例如当障碍物被摧毁时。

type Dungeon = Map Pos Tile

type Pos = (Int,Int) -- cartesian coordinates
data Tile = Wall | Destroyable | ...

但是如果我也必须打印它怎么办 - 那么我就必须使用类似的东西 elaboratePrint . sort $ fromList dungeon哪里elaboratePrint处理换行符并从图 block 集中生成漂亮的 unicode 符号。

我考虑的另一个选择是嵌套列表

type Dungeon = [[Tile]]

这会有一个缺点，即很难更新这样的数据结构中的单个元素。但打印的话就只是一张简单的衬垫unlines . map show .

我考虑的另一个结构是 Array ，但由于我不习惯数组，所以我浏览了一下 hackage 文档 - 我只找到了一个对索引进行操作的映射函数和一个对元素进行操作的映射函数，除非有人愿意使用可变数组来更新一个元素并不容易乍一看。并且打印数组也不清楚如何快速、轻松地做到这一点。

现在我的问题是 - 是否有更好的数据结构来表示地下城 map ，并且具有易于打印和易于更新单个元素的特性。

Answer 1

数组怎么样？ Haskell 有真实的二维数组。

import Data.Array.IArray -- Immutable Arrays

现在，Array 可以通过任意 Ix a => a 进行索引。幸运的是，有一个实例 (Ix a, Ix b) => Ix (a, b)。这样我们就可以有

 type Dungeon = Array (Integer, Integer) Tile

现在您可以使用多个函数中的任意一个来构造其中一个，最简单的使用是

array :: Ix i => (i, i) -> [(i, a)] -> Array i a

所以对于你来说，

startDungeon = array ( (0, 0), (100, 100) )
              [ ( (x, y), Empty ) | x <- [0..100], y <- [0..100]]

只需将 100 和 Empty 替换为适当的值即可。

如果速度成为一个问题，那么使用 MArray 是一个简单的修复方法。和ST。我建议不要切换，除非速度确实是一个真正的问题。

解决 pretty-print 问题

import Data.List
import Data.Function

pretty :: Array (Integer, Integer) Tile -> String
pretty = unlines . map show . groupBy ((==) `on` snd.fst) . assoc

并且 map 显示可以转换为您想要将[Tile]格式化为一行的格式。如果您决定确实希望以一种很棒且高效的方式打印这些内容(也许是控制台游戏)，您应该查看一个合适的 pretty-print 库，例如 this一个。