CODEWITHSUNDEEP
exceptionsyntax-errorsmlsmlnjml
Psycho Bunnies
Psycho Bunnies

Reputation: 43

SML Uncaught Exception Empty

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.

Upvotes: -1

Views: 286

Answers (1)

qouify
qouify

Reputation: 3920

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

Upvotes: 1

Related Questions