Haskell

Question

我正在尝试实现一个函数来匹配二维网格内 Haskell 中的特定模式。例如，如果我的网格定义如下：

grid = [[0,0,0,0],
        [0,1,1,0],
        [0,1,1,0],
        [0,0,0,0]]

我正在寻找的模式是：

pattern = [[1, 1], 
           [0, 0]]

我想要它 return 网格中左上角元素的索引。在这种情况下，(2,1)。我的函数具有以下类型：

matches2d :: Eq a 
          => [[a]]          -- ^ The 2D grid to match over 
          -> [[a]]          -- ^ The 2D pattern to match
          -> [(Int, Int)]   -- ^ Top left corner of sections matching the pattern

我不确定如何解决这个问题。我在这里尝试使用的方法是在网格上滑动 window 模式，但我一直在尝试实现类似的东西。到目前为止，这是我所知道的，但我想我遗漏了它背后的一些逻辑：

matches2d :: Eq a => [[a]] -> [[a]] -> [(Int, Int)] 
matches2d _ [] = [] 
matches2d f (x:xs) = matcher x pattern 
  where matcher x y (x:xs) = sort x == sort y

在此先感谢您的帮助。

Answer 1

所以解决这个问题花了我一些时间。我需要定义另一个辅助函数和其他几个函数才能让它工作。归结起来有一个 slicer 函数：它需要一个完整的网格和两个元组，然后提取子网格，其中包含第一个元组范围内的行和第二个元组的列。它的定义如下：

slicer :: [[a]] -> (Int, Int) -> (Int, Int) -> [[a]]
slicer [] _ _ = []
slicer a (x1,x2) (y1,y2) =form (head ( [[index a (i,j)|i<-[x1..x2-1],j<-[y1..y2-1]]])) (x2-x1,y2-y1)

我还需要一个函数来 return 网格中给定索引处的值，index:

index :: [[a]] -> (Int, Int) -> a
index (b:bb) (0,0) = head b
index (c:cc) (0,y) = index [(tail c)] (0,y-1)
index (d:dd) (x,y) = index dd (x-1,y)

接下来是定义 helper 函数。这占用了函数的大部分工作。它有助于 "nest" 整个网格的操作。它的全部功能就是把固定大小的window滑遍整个格子，找到一个匹配项。一旦完成，它会给出匹配 window 的最左上角的坐标。它的定义是这样的：

helper :: Eq a => [[a]] -> [[a]] -> (Int, Int, Int) -> [(Int, Int)]
helper x _ (l, m, n) | (l > length x) = []
helper x y (l, m, n) | (n > length (concat (take 1 x))) = helper x y (l+1, 0, (length (concat (take 1 y))))
helper x y (l, m, n) | (slicer x (l, (length y) + l) (m, n) == y) = [(l, m)] ++ helper x y (l, (m+1), (n+1))
helper x y (l, m, n) | (slicer x (l, (length y) + l) (m, n) /= y) = [] ++ helper x y (l, (m+1), (n+1))

最后，在所有这些子功能之后，是时候真正实现我从一开始就尝试实现的功能了。具有讽刺意味的是，它是其中最简单的，因为它只是在网格的长度上采用给定的模式。

matcher :: Eq a => [[a]] -> [[a]] -> [(Int, Int)]
matcher x y = helper x y (0, 0, (length (concat (take 1 y))))

Answer 2

递归求解。

这是一些迭代开发。在下文中，您首先需要了解列表理解和 zipWith 函数。它是求解方程的最简单的函数

zipWith <b>f</b> (x:xs) (y:ys) = <b>f</b> x y : zipWith <b>f</b> xs ys

或者，如果您熟悉 zip，

zipWith <b>f</b> xs ys = [<b>f</b> x y | (x,y) <- zip xs ys]

此外，

and (x:xs) = x && and xs
           =  all (\x -> x == True) xs
           =  all (\x -> x) xs
           =  all id xs

这样，

1.

matches2d_1 :: Eq a => [[a]] -> [[a]] -> Bool
<b>matches2d_1</b> pattern xss = 
    and (map and (zipWith (zipWith (==)) pattern xss))     -- does it match?
    ||  <b>matches2d_1</b> pattern (drop 1 xss)            -- or start at next row
    ||  <b>matches2d_1</b> pattern (map (drop 1) xss)      -- or start at next column

这在边缘情况下是错误的，但给出了一个总体思路。它的核心是and (zipWith (\a b -> and (zipWith (==) a b)) pattern xss)位

请注意，它只为我们提供了第一个成功结果的指示，但我们需要所有结果，因此，它们的列表。因此，

2.

matches2d_2 :: Eq a => [[a]] -> [[a]] -> [Bool]
matches2d_2 pattern xss    | shorter xss pattern       = []  -- not enough rows
matches2d_2 pattern (xs:_) | shorter xs (head pattern) = []  -- not enough columns
matches2d_2 pattern xss = 
    <b>[True |</b> and (map and (zipWith (zipWith (==)) pattern xss))<b>]</b>  -- this match
    <b>++</b>  matches2d_2 pattern (drop 1 xss)            -- or other
    <b>++</b>  matches2d_2 pattern (map (drop 1) xss)      --      ones...
shorter a b = -- length a < length b
       .... implement it better

这会处理边缘情况，但不会返回实际成功结果它仍然只是报告它们中的每一个。

3.

matches2d :: Eq a => [[a]] -> [[a]] -> [(Int,Int)]
.....

增加上面的内容应该会给我们在这里想要的实际结果。

4.

通过遵循规范的工作实施，我们接下来可以考虑效率。它会重复做任何多余的工作吗？这可以避免吗？

Haskell - 使用滑动 window 在 2D 网格上进行模式匹配

Haskell - pattern match over a 2D grid using a sliding window

pattern-matching

sliding-window