Haskell - сопоставление с образцом по двумерной сетке с использованием скользящего окна

Question

Я пытаюсь реализовать функцию, соответствующую заданному шаблону c в Haskell внутри двумерной сетки. Например, если моя сетка определена следующим образом:

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

и шаблон, который я ищу:

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

Я бы хотел, чтобы он возвращал индекс верхнего левого угла. элемент в сетке. В этом случае (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

Я не совсем уверен, как решить эту проблему. Метод, который я пытаюсь использовать здесь, представляет собой скользящее окно шаблона над сеткой, но я сейчас пытаюсь реализовать нечто подобное. Это то, что у меня есть до сих пор, но я думаю, что мне не хватает некоторых логик c за ним:

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

Решите это с помощью рекурсии.

Вот итеративная разработка. В дальнейшем вам необходимо сначала разобраться в понимании списков и функции 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.

При работающей реализации, соответствующей спецификациям, мы можем думать об эффективности дальше. Делает ли это какую-либо избыточную работу, неоднократно? Можно ли этого избежать?

Answer 2

Так что решение для этого заняло у меня некоторое время. Мне нужно было определить другую вспомогательную функцию и несколько других, чтобы заставить ее работать. Чтобы свести его к минимуму, есть функция 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)

Мне также нужна была функция для возврата значения по указанному индексу в сетке, 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 функцию. Это заняло большую часть работы функции. Это помогло «вложить» операцию по всей сетке. Вся его функция состоит в том, чтобы сдвинуть окно с фиксированным размером по всей сетке и найти совпадение. Как только он это делает, он дает самые верхние левые координаты этого соответствующего окна. Его определение таково:

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))))