SML Uncaught Exception Empty

Question

I am quite new to SML and am trying to implement a selection sort. I am running into an uncaught empty error however and can't seem to see why.

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;

I would appreciate suggestions as to where my mistake is and how to fix it.

Answer 1

There is no base case in your recursion. removeMin immediately calls removeMin with the tail of lst. Eventually lst will be the empty list and tl lst will fail with an Empty exception. So you have to identify when you recursion should stop and add this case to removeMin.

You have actually identified this base case in your function: if null (tl lst) then (hd lst, []). But this case should be checked right before the recursive call. By reorganising your function and getting rid of calls to hd and tl by using pattern matching constructs this is what I get:

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];