retour en arrière dans haskell

Question

Je dois traverser une matrice et dire combien de "zones caractéristiques" de chaque type il a.

Une zone caractéristique est définie comme une zone où les éléments de valeur n ou> n sont adjacents.

Par exemple, étant donné la matrice:

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

Il y a une zone unique caractéristique de type 1, qui est égal à la matrice d'origine:

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

Il y a deux zones caractéristiques de type 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 

Et une zone caractéristique de type 3:

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

Ainsi, pour l'appel de fonction:

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

Le résultat devrait être

[1,2,1] 

Je n'ai pas encore défini countAreas, je suis coincé avec ma fonction visit quand il a plus de carrés possibles dans lesquels le déplacer se coince et ne fait pas l'appel récursif approprié. Je suis novice en programmation fonctionnelle et je me demande toujours comment implémenter un algorithme de backtracking ici. Jetez un oeil à mon code, que puis-je faire pour le changer?

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

Est-ce que cela vous aiderait à utiliser un type de tableau plutôt qu'une liste de listes? Vous faites toujours de la programmation fonctionnelle, en utilisant simplement une meilleure structure de données.

Vous pouvez créer un Array (Int,Int) Int si cela vous convient. Voir:

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

import Data.Array 

... pour obtenir la bibliothèque.

Answer 2

Je ne pense pas que le retour en arrière soit ce que vous recherchez. Il me semble que votre but est d'avoir votre visit fonction de construire une liste visitée car il trouve tous les éléments connectés dans la matrice à partir d'un certain point qui répondent à certaines conditions. Ce que vous devez penser est quel algorithme y parviendra. Ne vous inquiétez pas de l'exprimer en termes de programmation fonctionnelle ou impérative (encore). Pensez simplement: l'algorithme est-il récursif dans la nature? Itératif? Si vous l'avez arrêté au milieu de l'informatique, comment sauriez-vous que faire dans l'algorithme? De quelles données auriez-vous besoin?

Je ne voudrais pas m'inquiéter de diverses améliorations dans le code pour l'instant (en utilisant Array ou en éliminant les instructions if, etc ...), vous pouvez y accéder plus tard. La clé qui vous manque est un algorithme viable.