Implementing Radix Sort in SML

Question

I am trying to implement radix sort in SML via a series of helper functions. The helper function I am having trouble with is called sort_nth_digit, it takes a digit place to be sorted by and a list to sort (n and L respectively). The way I am doing this is to find the first two elements of the list (for now we can assume there are at least 3), compare them by digit n, then concatenating them back onto the list in the proper order. The list should be sorted in ascending order. Now, the problem: The function compiles but I get the following:

HW4.sml:40.5-44.30 Warning: match nonexhaustive (0,L) => ... (n,nil) => ... (n,a :: b :: L) => ...

val sort_nth_digit = fn : int -> int list -> int list

Additionally, when you pass arguments, you don't get an answer back which I believe indicates infinite recursion?

Q:How is the match nonexhaustive and why am I recursing infinitely:

 fun sort_nth_digit 0 L = []
|   sort_nth_digit n [] = []
|       sort_nth_digit n (a::b::L) = if ((nth_digit a n) < (nth_digit b n)) then a::b::(sort_nth_digit n L)
        else
            b::a::(sort_nth_digit n L)

Thanks for the help in advance! (*My first post on stackoverflow ^.^ *)

Nonexhasutive match fix:

fun sort_nth_digit 0 L = []
|   sort_nth_digit n [] = []
|       sort_nth_digit n (a::[]) = a::[]
|       sort_nth_digit n (a::b::L) = if ((nth_digit a n) < (nth_digit b n)) then a::b::(sort_nth_digit n L)
        else
            b::a::(sort_nth_digit n L) 

Input that results in no output, console just sits at this line:

- sort_nth_digit 1 [333,222,444,555,666,444,333,222,999]; 

Code for nth_digit & anonymous helper pow:

fun nth_digit x 0 =  0
|   nth_digit x n = if (num_digits x) < n then 0
        else 
            let 
                fun pow x 1 = x
                |   pow x y= x * pow x (y-1)
            in
(*Finding the nth digit of x: ((x - x div 10^n) * 10^n div 10^n-1))*)
            (x - ((x div pow 10 n) * pow 10 n)) div (pow 10 (n-1))  (*Me*)
            end

If anyone thinks it would be useful to have access to the rest of my code I can provide it via github as an eclipse project (you can just pull the .sml file if you don't have eclipse set up for sml)

Answer 1

The match is not exhaustive because it does not cover the case of a list with only one element (and inductively, any list with an odd number of elements).

I'm not sure what you mean by "not getting an answer". This function does not diverge (recurse infinitely), unless your nth_digit helper does. Instead, you should get a Match exception when you feed it a list with odd length, because of the above.