Возвращение в хаскелл

Question

Я должен пройти матрицу и сказать, сколько "характерных областей" каждого типа у нее есть.

Характеристическая область определяется как зона, в которой элементы значения n или> n являются смежными.

Например, с учетом матрицы:

0 1 2 2
0 1 1 2
0 3 0 0

Есть одна характерная область типа 1, которая равна исходной матрице:

0 1 2 2
0 1 1 2
0 3 0 0

Есть две характерные области типа 2:

0 0 2 2    0 0 0 0
0 0 0 2    0 0 0 0
0 0 0 0    0 3 0 0

И одна характерная область типа 3:

0 0 0 0 
0 0 0 0
0 3 0 0 

Итак, для вызова функции:

countAreas [[0,1,2,2],[0,1,1,2],[0,3,0,0]] 

Результат должен быть

[1,2,1]

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

move_right :: (Int,Int) -> [[Int]] -> Int -> Bool
move_right (i,j) mat cond | (j + 1) < number_of_columns mat && consult (i,j+1) mat /= cond = True
               | otherwise = False

move_left :: (Int,Int) -> [[Int]] -> Int -> Bool
move_left (i,j) mat cond | (j - 1) >= 0 && consult (i,j-1) mat /= cond = True
               | otherwise = False

move_up :: (Int,Int) -> [[Int]] -> Int -> Bool
move_up (i,j) mat cond | (i - 1) >= 0 && consult (i-1,j) mat /= cond = True
               | otherwise = False

move_down :: (Int,Int) -> [[Int]] -> Int -> Bool
move_down (i,j) mat cond | (i + 1) < number_of_rows mat && consult (i+1,j) mat /= cond = True
               | otherwise = False

imp :: (Int,Int) -> Int
imp (i,j) = i


number_of_rows :: [[Int]] -> Int
number_of_rows i = length i

number_of_columns :: [[Int]] -> Int
number_of_columns (x:xs) =  length x

consult :: (Int,Int) -> [[Int]] -> Int
consult (i,j) l = (l !! i) !! j

visited :: (Int,Int) -> [(Int,Int)] -> Bool
visited x y = elem x y

add :: (Int,Int) -> [(Int,Int)] -> [(Int,Int)]
add x y = x:y

visit :: (Int,Int) -> [(Int,Int)] -> [[Int]] -> Int -> [(Int,Int)]
visit (i,j) vis mat cond | move_right (i,j) mat cond && not (visited (i,j+1) vis) = visit (i,j+1) (add (i,j+1) vis) mat cond
               | move_down (i,j) mat cond && not (visited (i+1,j) vis) = visit (i+1,j) (add (i+1,j) vis) mat cond
               | move_left (i,j) mat cond && not (visited (i,j-1) vis) = visit (i,j-1) (add (i,j-1) vis) mat cond
               | move_up (i,j) mat cond && not (visited (i-1,j) vis) = visit (i-1,j) (add (i-1,j) vis) mat cond
               | otherwise = vis

Answer 1

Поможет ли вам использовать здесь тип Array, а не list-of-lists? Вы все еще занимаетесь функциональным программированием, просто используете лучшую структуру данных.

Вы можете создать Array (Int,Int) Int если это работает для вас. Увидеть:

http://hackage.haskell.org/packages/archive/array/0.2.0.0/doc/html/Data-Array-IArray.html

import Data.Array

... чтобы получить библиотеку.

Answer 2

Я не думаю, что возвращение назад на самом деле то, что вы после. Сдается мне, что ваша цель состоит в том, чтобы ваш visit Функция создает список посещений, так как она находит все связанные элементы в матрице из некоторой точки, которая удовлетворяет некоторому условию. Надо подумать, какой алгоритм этого достигнет. Не беспокойтесь о его выражении в терминах функционального или императивного программирования (пока). Просто подумайте: является ли алгоритм рекурсивным по своей природе? Повторяющийся? Если вы остановите его в середине вычислений, как вы узнаете, что делать дальше в алгоритме? Какие данные вам понадобятся?

На данный момент я не буду беспокоиться о различных улучшениях в коде (используя Array или устранение if заявления и т.д...), вы можете получить к ним позже. Ключ, который вам не хватает, является жизнеспособным алгоритмом.