对 SML 列表进行排序时出现问题

Question

我是SML的新手。我得到了这个排序算法来实现在每次迭代中的位置，我必须从列表中选择最少的元素，将其删除并创建排序列表。

我在下面做了编码来解决问题。

我编写了 2 个辅助函数来从列表中选取最小元素并从列表中删除一个元素。

fun minList(x::xs) =List.foldl (fn (x,y)=> if x<y then x else y) x (x::xs);
fun remElem(x, l) =
   case l of
   [] => []
 | (x1::x2::xs) => if x1=x then (x2::xs) else (x1::xs)
;

以上两个程序运行成功。

下面是我的排序代码。

fun simpSort(xs)=
let fun aux(xs,acc)=
       case xs of
            [] =>acc
           | [x] => [x]
            | (x::xs) => let val m = minList(xs) 
                       in
                     aux(remElem(m,xs),acc@[m])
                       end
in aux(xs,[])
end;

此排序程序出错。

• simpSort([3,1](;

  未捕获的异常 匹配 [非穷举匹配失败]提高位置：标准输入：433.59

请指教。

Answer 1

既然你已经解决了你的问题，这里有一些改进代码工作版本的提示：

• 以支持空列表的方式查找列表的最小值：

  fun minimum [] = NONE
    | minimum (x::xs) = SOME (foldl Int.min x xs)
  

• 简化从列表中删除元素第一次出现的函数中的模式匹配：

  fun remove (_, []) = []
    | remove (y, x::xs) =
      if x = y
      then xs
      else x :: remove (y, xs)
  

• 结合使用它们来编写simpSort：

  fun simpSort xs =
      case minimum xs of
           NONE => []
         | SOME x => x :: simpSort (remove (x, xs))
  

我不应该说这种排序算法效率非常低。