Haskell 中与 DFS 兼容的无坐标邻居

Question

我最近发现自己解决了很多二维矩阵搜索问题。典型的方法如下所示，它沿着 2D 数组中的 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

  、

  fgl

  、

  heaps

  等）Total 表示没有部分函数，如
!!
• 、

  head

  、

  maximum

  等快意味着
O(log n)
• 。
为什么有具体限制？只是因为我已经知道如何在没有这些限制的情况下解决它。我有兴趣找到解决此类问题的原则性方法，当不允许使用大型自定义模板库时，该方法将非常适合竞争性编程。

解决方案的想法：

我想知道2D拉链是否可以工作。

注意：我问了一个标题与here类似的问题，但这些问题完全不相关，因为

[[NonEmpty a]]

或类似类型的值与上面的DFS函数不“兼容”。似乎没有好的方法可以从单元格的邻居列表中获取值，然后在 O(1) 中依次获取 its 邻居，因为这需要我们重新索引到列表中在正确的位置，但我们已经在此表示中丢弃了有关位置的所有信息。

Answer 1

当然，只需使用

这个答案

中的neighbors即可。然后就可以写了

neighborMap :: [[String]] -> Map String [String]
neighborMap ss = M.fromListWith [(k, [v]) | (k, v) <- neighbors ss]

您可以使用

Maybe

来避免查找中的

M.findWithDefault []

。 （我经常认为应该有一个专门化

M.lookupMonoid :: Monoid v => k -> Map k v -> v; M.lookupMonoid = M.findWithDefault mempty

或类似的东西，但也许它太短了，不值得添加一个新名称来记住。）