我最近发现自己正在解决很多二维矩阵搜索问题。一种典型的方法如下图所示，它在二维数组中沿着 4 个方向连接的路径搜索单词：
data State = S { word :: String, coord :: Coord } deriving (Eq, Ord, Read, Show)
data Coord = C Int Int deriving (Eq, Ord, Read, Show)
dfsOnN :: Ord r => (a -> r) -> (a -> [a]) -> [a] -> [a]
coordMap :: [[a]] -> Map Coord a
cardinals :: Coord -> [Coord]
neighbors :: Map Coord Char -> State -> [State]
solution :: [[Char]] -> String -> Bool
solution board w = any found . search . states w $ board
where
search = dfsOnN coord (neighbors vals)
found = (== "") . word
vals = coordMap board
带签名的DFS函数
dfsOnN :: Ord r => (a -> r) -> (a -> [a]) -> [a] -> [a]
采用投影函数，将状态发送到适合访问集的表示，以及后继函数，计算图中的邻居。
我的麻烦在于后继函数。从 的类型签名可以看出neighbors，我通常将位置映射到值，并在相邻坐标上执行查找以获取后继。但我觉得这是一种非常迂回的做法。如果我们总是将矩阵作为列表列表给出，那么列表已经“知道”附近有什么内容，因为它是连续的。
在许多类似的问题中，我们将其转换为坐标/索引的唯一原因就是执行索引算法来获取邻居。坐标本身对于问题而言完全是多余的。我们还必须担心查找可能会失败，Maybe如果我们使用类似的东西，则需要进行处理Map Coord Char，但这也应该是不必要的。列表列表已经“知道”其边界在哪里，当我们将其转换为坐标时，我们会丢弃此信息。
问题：a -> [a]是否有一种简洁的方法来实现不使用坐标的二维矩阵问题的快速总邻域函数？
限制：
- 简洁意味着包括类型签名在内的标记少于 100 个（我的坐标完整版本的粗略大小）
- 欢迎采用适合相当流行/常见/规范的库的解决方案。（因此
base，诸如containers、、、、等等。unordered-containers）fglheaps - 总计意味着没有诸如、、
!!等部分函数。headmaximum - 快的意思
O(log n)。
为什么要有特定的限制？很简单，因为我已经知道如何在没有这些限制的情况下解决问题。我感兴趣的是找到一种原则性的方法来解决这类问题，当不允许使用大型自定义模板库时，这种方法将非常适合竞技编程。
解决方案的想法：我想知道像2D 拉链这样的东西是否可以起作用。
注意：我问了一个标题与此处类似的问题，但这些问题完全不相关，因为类型[[NonEmpty a]]或类似的值与上述 DFS 函数不“兼容”。似乎没有很好的方法可以从单元格的邻居列表中获取值，然后在 O(1) 中依次获取其邻居，因为这需要我们在正确的位置重新索引列表，但我们在此表示中丢弃了有关位置的所有信息。
