exception - SML - 在快速排序算法中找不到“未捕获异常空”的位置

Question

我正在尝试在不使用任何 List.nth 函数的情况下编写快速排序算法。我想出了这个，但是当我尝试测试它时，它最终抛出了一个“未捕获的异常空”。我似乎无法找到引发此异常的位置。这是我的代码：

(*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]);

标签： exceptionsml