在 SML 中创建一个以元组作为键的 ORD_MAP

Question

我正在做一个 SML 练习，我在一个网格中，从单元格 (i,j) 开始，我想转到单元格 (x,y)。为了模拟这一点，每个单元格都被视为一个状态 (i,j,move)，其中移动它是如何从前一个单元格到达那里的。然后我写了一个简单的遍历算法（更像 dfs），它开始搜索状态，直到找到所需的状态。

请注意，对于遍历函数，我使用了一个 Map-Dictionary，它以一个 State 作为索引，以便跟踪访问过的 States。

代码：

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

当我运行这个程序的时候，在执行遍历函数的时候会进入死循环。它来自州：(1,0)->(0,0)->(0,1)->(0,2)->(0,3)->(1,3)->(2,3)->(3,3)

从那以后，它继续在州 (3,3) 和 (3,2) 之间进行。另外，当遍历函数在State (3,2) 并且其中存在State (3,3) 时，我检查了Map结构，这意味着它不应该再次查看它并继续检查其他States.

到底是什么不符合我的想法并导致了这个循环？

Answer 1

我认为问题在于您的比较功能已损坏。 编辑： 例如它定义

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

这违反了反对称。但这是订购的必要属性。

您想要正确的字典顺序：

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

在 SML 中创建一个以元组作为键的 ORD_MAP

Creating an ORD_MAP with Tupples as Key in SML

algorithm

structure

sml

smlnj