SML 未捕获异常为空

Question

我对 SML 很陌生，正在尝试实现选择排序。然而，我遇到了一个未捕获的空错误，似乎不明白为什么。

fun removeMin lst =
  let
    val (m, l) = removeMin(tl lst)
  in
    if null (tl lst) then
      (hd lst, [])
    else if hd lst < m then
      (hd lst, tl lst)
    else
      (m, hd lst::l)
  end;

fun selectionSort [] = []
  | selectionSort lst =
    let
      val (m, l) = removeMin(lst)
    in
      m::selectionSort(l)
    end;

我希望得到有关我的错误在哪里以及如何解决的建议。

Answer 1

您的递归中没有基本情况。立即removeMin
使用 lst 的尾部调用 removeMin。最终lst将是
空列表和 tl lst 将失败并出现 Empty 异常。所以你
必须确定递归何时应停止并将此情况添加到
removeMin。

您实际上已经在函数中确定了这个基本情况：if null (tl lst) then (hd lst, [])。但这种情况应该检查一下
在递归调用之前。通过重组你的功能并获得
使用模式匹配结构消除对 hd 和 tl 的调用
这就是我得到的：

fun removeMin [] = raise Empty  (* should not be called with an empty list *)
  | removeMin [x] = (x, [])     (* base case of the recursion *)
  | removeMin (x :: tl) = let
      val (m, l) = removeMin tl
  in
      if x < m
      then (x, tl)
      else (m, x :: l)
  end;

fun selectionSort [] = []
  | selectionSort lst = let
      val (m, l) = removeMin(lst)
  in
      m :: selectionSort(l)
  end;

selectionSort [3, 2, 12, 4];