Création d'un ORD_MAP avec Tupples comme clé dans SML

Question

Je fais un exercice dans SML dans lequel je suis dans une grille et commence à partir de la cellule (i,j) et je veux aller à la cellule (x,y). Pour simuler ceci chaque cellule est traitée comme un état (i,j,move) où déplacer comment il est arrivé là de la cellule précédente. Puis j'ai écrit un algorithme de traversée simple (plus semblable à dfs) ​​qui commence à chercher les états jusqu'à ce qu'il trouve celui désiré.

Notez que pour la fonction de traversée, j'utilise un Map-Dictionary qui prend un état en tant qu'index afin de garder une trace des états visités.

code:

val startp = (0,0) 
val endp = (3,0) 
val (N,M) = (4,4) 

(*Define the Basic structures tht will be used*) 
datatype movement = RIGHT | DOWN | LEFT | UP 

type State = int * int * movement 

val firstState = (#1 startp,#2 startp,UP): State 

structure STATES_KEY: ORD_KEY = 
    struct 
    type ord_key = State 
    val compare = fn (s1:State, s2:State) => 
     if (#1 s1 = #1 s2) andalso (#2 s1 = #2 s2) 
     then EQUAL 
     else if (#1 s1 > #1 s2) then GREATER 
     else LESS 
    end 

structure StatesMap = SplayMapFn(STATES_KEY) 

fun convert_ij id = (id div M, id mod N) 

fun getNextStates ((i,j,_):State): State list = 
    [ (i,j+1,RIGHT), 
    (i+1,j,DOWN), 
    (i,j-1,LEFT), 
    (i-1,j,UP)] 

fun getPrevState ((i,j,move):State): State = 
    case move of 
     RIGHT => (i,j-1,UP) 
    | LEFT => (i,j+1,UP) 
    | UP => (i+1,j,UP) 
    | DOWN => (i-1,j,UP) 

(*True -> Invalid State*) 
fun checkInvalidState ((i,j,_):State) = 
    if (i < 0 orelse i > N-1 orelse j < 0 orelse j > M-1) 
    then true 
    else false 

fun checkEnd ((i,j,_):State) = 
    if (i = #1 endp andalso j = #2 endp) 
    then true 
    else false 

fun traversal [] visited = visited 
    | traversal (h::t) visited = 
    if (checkEnd h) then visited 
    else if (checkInvalidState h) then traversal t visited 
    else if (StatesMap.find (visited, h) = NONE) 
    then 
    let 
     val [s1,s2,s3,s4] = getNextStates h 
    in 
     traversal (s1::s2::s3::s4::t) (StatesMap.insert (visited, h, h)) 
    end 
    else traversal t visited 

val it = traversal [firstState] StatesMap.empty 

Quand je lance le programme, il est dans une boucle infinie lors de l'exécution de la fonction transversale. Il va de l'état: (1,0)->(0,0)->(0,1)->(0,2)->(0,3)->(1,3)->(2,3)->(3,3)

Et à partir de là, il continue entre États (3,3) et (3,2). Aussi, j'ai vérifié la structure de carte quand la fonction de traversée est dans l'état (3,2) et l'état (3,3) existe dedans, signifiant qu'il ne devrait pas le regarder encore et continuer à vérifier les autres états.

Qu'est-ce qui ne fonctionne pas exactement comme je le pense et provoque cette boucle?

Answer 1

Je crois que le problème est que votre fonction de comparaison est cassée. Edit: Par exemple, il définit

(0, 2) < (0, 1) 
(0, 1) < (0, 2) 

qui viole anti-symétrie. Mais c'est une propriété nécessaire d'un ordre.

Vous voulez un bon ordre lexicographique:

fun compare ((x1,y1,_), (x2,y2,_)) = 
    case Int.compare (x1, x2) of 
     EQUAL => Int.compare (y1, y2) 
    | order => order