Erstellen einer ORD_MAP mit Tupples als Schlüssel in SML

Question

Ich mache eine Übung in SML, in der ich in einem Raster bin und von Zelle (i,j) starten und ich möchte zu Zelle (x,y) gehen. Um dies zu simulieren, wird jede Zelle als ein Zustand (i,j,move) behandelt, in dem sich die Zelle aus der vorherigen Zelle bewegt. Dann schrieb ich einen einfachen Traversalalgorithmus (mehr wie dfs), der die Suche nach den Zuständen beginnt, bis sie den gewünschten gefunden hat.

Beachten Sie, dass ich für die Traversierungsfunktion ein Map-Dictionary verwende, das einen Zustand als Index verwendet, um die besuchten Zustände zu verfolgen.

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 

Wenn ich das Programm laufen, ist es in einer Endlos-Schleife erhält, wenn die Traverse Funktion ausführt. Es geht vom Staat: (1,0)->(0,0)->(0,1)->(0,2)->(0,3)->(1,3)->(2,3)->(3,3)

Und von dort weiter geht es zwischen Staaten (3,3) und (3,2). Außerdem habe ich die Map-Struktur überprüft, wenn die Traversierungsfunktion im Zustand (3,2) ist und der Status (3,3) darin existiert, was bedeutet, dass sie es nicht erneut betrachten sollte und die anderen Zustände weiterhin prüfen soll.

Was genau funktioniert nicht so, wie ich denke, es funktioniert und verursacht diese Schleife?

Answer 1

Ich glaube, das Problem ist, dass Ihre Vergleichsfunktion kaputt ist. Edit: Zum Beispiel definiert es

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

die anti-Symmetrie verletzt. Aber das ist eine notwendige Eigenschaft einer Bestellung.

Sie wollen eine richtige lexikographische Ordnung:

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