Why do types 'a and ''Z not match up in SML?

Question

I have the following recursive function:

fun tester (f:'a -> 'b, tl:(string * 'a * 'b) list) =
    case tl of
    [] => []
     | (t, c, e)::rest => 
       let val tr = f (c)
       in
           if tr <> (e)
           then ((t), (e), tr)::(tester (f, rest))
           else tester (f, rest)
       end;

When loading it I get "Error: operator and operand don't agree [UBOUND match]':

lec1test.sml:17.5-19.26 Error: operator and operand don't agree [UBOUND match]
  operator domain: ''Z * ''Z
  operand:         'b * 'Y
  in expression:
    tr <> e

uncaught exception Error
  raised at: ../compiler/TopLevel/interact/evalloop.sml:66.19-66.27
             ../compiler/TopLevel/interact/evalloop.sml:44.55
             ../compiler/TopLevel/interact/evalloop.sml:296.17-296.20

I have figured out that I think it has something with the generic binding of tr, but I can't see why that is a problem. I am assigning trto a value of the function from f, which returns 'b. I then compare the result with the last value in the tuple which also is of type 'b. Can someone explain why this is giving me an error?

Answer 1

Not all types support the equality operators = and <>, only so-called equality types. For example, int or string list or bool * unit are equality types, but e.g. function types t -> u never are, because there is no reasonable (decidable) way to compare functions.

Values of a polymorphic type like 'a are not equality types either, because the type variable can be instantiated by any type. To get a polymorphic type restricted to equality types, you need to write a type variable with a double tick, e.g. ''a.

In your case, changing the first line to

fun tester (f : ''a -> ''b,  tl : (string * ''a * ''b) list) =

should fix it for you.