SML - Can't find where "uncaught exception Empty" is thrown in quicksort algorithm

Question

I am trying to write a quicksort algorithm without using any List.nth functions. I've come up with this but when I try to test it, it ends up throwing an "uncaught exception Empty". I can't seem to find where this exception is thrown. Here is my code:

(*returns last element in list*)
fun last (h::nil) = h
|   last(h::lst)  = last(lst)
|   last _        = ~1;

(*returns middle element in list*)
fun middle (lst) = 
    let
        fun middle_rec (_ :: [])      (x :: _)  = x
        |   middle_rec (_ :: _ :: []) (x :: _)  = x
        |   middle_rec (_ :: _ :: xs) (_ :: ys) = middle_rec xs ys
        |   middle_rec _              _         = ~1
    in
        middle_rec lst lst
    end;

(*return median of three elements*)
fun median(a,b,c) = 
    if ((b>a andalso a>c) orelse (c>a andalso a>b))
        then a
        else if ((a>b andalso b>c) orelse (c>b andalso b>a))
            then b
            else if ((a>c andalso c>b) orelse (b>c andalso c>a))
                then c
                else ~1;

(*partitions a list with one containing elements smaller than or equal to p and one with elements greater than p*)
fun partition([], p) = ([],[])
|   partition(lst,p) =
    let
        fun part_rec ([], x::xs, y::ys, p) = (x::xs, y::ys)
        |   part_rec (lst, x, y, p) =
                if hd(lst) <= p
                    then part_rec(tl(lst), hd(lst)::x, y, p)
                    else part_rec(tl(lst), x, hd(lst)::y, p)
    in
        part_rec(lst,[],[],p)
    end;

(*quicksort function*)
fun quicksort [] = []
|   quicksort(x::xs) = 
    let val (left, right) = partition(x::xs, median(x, middle(x::xs), last(x::xs)))
    in
        quicksort left @ [x] @ quicksort right
    end;

quicksort([9,4,7,2,8,5,1,6,4,3]);

question from:https://stackoverflow.com/questions/65877224/sml-cant-find-where-uncaught-exception-empty-is-thrown-in-quicksort-algorit

Answer 1

Waitting for answers