SMLNJ Insertion Sort Operator and Operand dont agree error

Question

Im making an insertion sort code in SML, here it is

fun compare(x:real, y:real, F) = F(x, y);
fun isEqual(x:real, y:real) = ((x <= y) andalso (x >= y));

fun rinsert(x: real, [], F) = [x]
    |rinsert(x, (y::ys), F) =
    if isEqual(x, y) then rinsert (x, ys, F)
    else if compare(x, y, F) then x::y::ys
            else y::(rinsert (x, ys, F));

fun rinsort([], F) = []
    |rinsort(x::xs, F) = rinsert(x, (rinsort(xs, F), F));

However, on running it i get this error

val isEqual = fn : real * real -> bool                                                                                                                                                               
val rinsert = fn : real * real list * (real * real -> bool) -> real list                                                                                                                             
stdIn:12.27-12.58 Error: operator and operand don't agree [tycon mismatch]                                                                                                                           
  operator domain: real * real list * (real * real -> bool)                                                                                                                                          
  operand:         'Z * ('Y list * 'X)                                                                                                                                                               
  in expression:                                                                                                                                                                                     
    rinsert (x,(rinsort (<exp>,<exp>),F))

I understand that rinsort is calling rinsert incorrectly, but I'm not sure how to fix it.

Answer 1

If it can be useful, This is an example of how your code should work with areal list:

fun compare(x:real, y:real, F) = F x y;
fun isEqual(x:real, y:real) = ((x <= y) andalso (x >= y));

fun rinsert(x: real, [], F) = [x]
    |rinsert(x, (y::ys), F) =
    if isEqual(x, y) then rinsert (x, ys, F)
    else if compare(x, y, F) then x::y::ys
            else y::(rinsert (x, ys, F));

fun rinsort([], F) = []
    |rinsort(x::xs, F) = rinsert(x, rinsort(xs, F), F);

val funcComp = fn r1 : real => fn r2 : real => if r1 < r2 then true else false;
val l : real list = [1.0, 3.8, 5.6, 3.8, 4.4, 5.6, 6.3, 5.5, 4.6, 8.1];
val b = rinsort(l, funcComp);

Answer 2

Some general feedback:

• The function compare only serves the purpose to switch the order of the arguments of F, so you might as well just refer to F itself then.

• The function isEqual is kind of bad. Since reals are not equality types in SML for a reason, try and avoid comparing them like that. It turns out, in order to sort reals, you only need <=, not =.

• The function rinsert has strict : real type annotations that are unnecessary since your insertion sort, in taking the comparison operator F as a parameter, might as well be generic (polymorphic).

• You might want to call the parameter F something more descriptive, like cmp, leq, or whatever reminds you of its purpose.

Here's an example of how one might also make an insertion sort function:

fun sort leq xs =
    let fun insert (x, []) = [x]
          | insert (x, y::ys) =
              if leq (x, y)
              then x::y::ys
              else y::insert (x, ys)
    in List.foldl insert [] xs
    end

It has the type ('a * 'a -> bool) -> 'a list -> 'a list. This is comparable to e.g. SML/NJ's built-in ListMergeSort.sort. I've chosen sort to be curried since you might want to specialize it by partial function application, e.g.,

val realsort = sort (op <=) : real list -> real list
val stringsort = sort (op >) : string list -> string list

but I've let the embedded helper function insert to be uncurried since List.foldl takes a function with type ('a * 'b -> 'b), i.e., a tuple of (x, ys) and returns a modified ys with x inserted.

You may want to consider which properties that can test that your function does sort. One property could be that all list elements in the sorted list are in the order specified by the comparison operator leq.

fun sorted_prop _ [] = true
  | sorted_prop _ [_] = true
  | sorted_prop leq (x::y::xs) = leq (x, y) andalso sorted_prop leq (y::xs)

Another property could be that each element in the unsorted list exists in the sorted list. The latter property may be hard to test if you're not assuming x to have an equality type (''a). But you could do that in the test specifically.