Creating an ORD_MAP with Tupples as Key in SML

Question

I'm doing an exercise in SML in which I'm in a grid and start from cell (i,j) and I want to go to cell (x,y). To simulate this every cell is treated as a State (i,j,move) where move how it got there from the previous cell. Then I wrote a simple traversal algorithm (more like dfs) which starts searching the States until it finds the desired one.

Note that for the traversal function I use a Map-Dictionary which takes a State as an Index in order to keep track of the visited States.

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

When I run the program, it gets in an infinite loop when executing the traverse function. It goes from State: (1,0)->(0,0)->(0,1)->(0,2)->(0,3)->(1,3)->(2,3)->(3,3)

And from there on it keeps on going between States (3,3) and (3,2). Also, I checked the Map struct when the traversal function is in State (3,2) and State (3,3) exists in it, meaning that it shouldn't look at it again and continue checking the other States.

What exactly doesn't work the way I think it works and causes this loop?

Answer 1

I believe the problem is that your comparison function is broken. Edit: For example it defines

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

which violates anti-symmetry. But that's a necessary property of an ordering.

You want a proper lexicographic ordering:

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