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.

How many arguments does `rinsert` take? How many are you calling it with? — melpomene, Jul 07 '17 at 18:23
rinsert takes three arguments, a real, a list, and an operator (like op<). It should only be calling the three — small502, Jul 07 '17 at 21:13
I don't understand what you mean by "*it should only be calling the three*". Look at the code. Count the arguments. How many are there? — melpomene, Jul 07 '17 at 21:46
Wow that was an awful oversight on my part, thanks mate. Works just fine now — small502, Jul 08 '17 at 00:09

Marco Luzzara · Answer 1 · 2017-07-12T15:26:35.207

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);

edited Jul 12 '17 at 15:26

answered Jul 07 '17 at 19:08

Marco Luzzara

5,540
3
16
42

`if r1 > r2 then false else true` is better expressed as `r1 <= r2`. – sshine Jul 12 '17 at 15:17
Yes, but not exactly, because `isEqual` already check for their equality. Anyway your version is certainly better to understand. – Marco Luzzara Jul 12 '17 at 15:25
1

You shouldn't be comparing reals like that. You might be interested in [Why can't I compare reals in Standard ML?](https://stackoverflow.com/questions/41394992/why-cant-i-compare-reals-in-standard-ml) Consider using `Real.==` or an epsilon test. – sshine Jul 13 '17 at 07:17

score 0 · Answer 2 · answered Jul 13 '17 at 09:07

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.

SMLNJ Insertion Sort Operator and Operand dont agree error

2 Answers2

Linked