SML merge_sort function using let in and pattern matching

Question

fun merge_sort (_, nil) = nil
  | merge_sort (_, [a]) = [a]
  | merge_sort (f, L)   =
    let
        fun halve nil = (nil,nil)
          | halve [a] = ([a], nil)
          | halve (a :: b :: rest) =
            let
                val (x , y) = halve rest
            in
                (a :: x, b :: y)
            end
        fun merge (f, nil, x) = x
          | merge (f, x, nil) = x
          | merge (f, a::b, x::y) =
            if f(a, b) then a :: merge (f, b, x::y)
                       else x :: merge (f, a::b, y);
        val (x, y) = halve L
    in
        merge(f, merge_sort(f, x), merge_sort(f,y))
    end;

merge_sort (op <) [2,1,3,2,4,3,45];

This is a SML function that I have been working on. It is meant to take a function call as shown in the bottom and merge sort. Must be one function. I am struggling understanding the pattern matching and how to fully make this function work.

I get this error code when I compile and run it.

$sml < main.sml
Standard ML of New Jersey v110.78 [built: Thu Aug 31 03:45:42 2017]
- val merge_sort = fn : ('a * 'a list -> bool) * 'a list -> 'a list
stdIn:23.1-23.35 Error: operator and operand don't agree [tycon mismatch]
  operator domain: ('Z * 'Z list -> bool) * 'Z list
  operand:         [< ty] * [< ty] -> bool
  in expression:
    merge_sort <
- 

I don't entirely know what I am doing wrong

Answer 1

Using the convention of naming lists with a plural "s" and using the same base name for the head and tail in patterns makes the problem stick out immediately:

merge (f, x::xs, y::ys) =
        if f(x, xs) then x :: merge (f, xs, y::ys)
                    else y :: merge (f, x::xs, ys);

where f(x, xs) should of course be f(x, y).

This convention is conventional because it's useful. Don't leave home without it.

Answer 2

You have a typo; this:

            if f(a, b) then a :: merge (f, b, x::y)
                       else x :: merge (f, a::b, y);

should be this:

            if f (a, x) then a :: merge (f, b, x::y)
                        else x :: merge (f, a::b, y)

(calling f on (a, x) rather than on (a, b)).

Since b and x have different types ('Z list and 'Z, respectively), the consequence of this typo is that f is inferred to have the wrong type ('Z * 'Z list -> bool rather than 'Z * 'Z -> bool), so the whole merge_sort function is inferred to have the wrong type scheme (('a * 'a list -> bool) * 'a list -> 'a list instead of ('a * 'a -> bool) * 'a list -> 'a list).

Some explicit type annotations (e.g. writing f : 'a * 'a -> bool in one place) might make it easier for the compiler to help you see where you're deviating from the types you intended; but, admittedly, if you don't already know where you're deviating, then it can be hard to figure out where to add annotations so the compiler can help you find where you're deviating.