How to match function type in signature in SML

Question

I want to compare whether the values ​​of two sets are equal, but when I pass the set into the equals function, the display type does not match.

Error: value type in structure does not match signature spec
    name: equals
  spec:   'a ?.set * 'a ?.set -> bool
  actual: ''a list * ''a list -> bool

signature SET =
sig
  type 'a set
  val emptyset: 'a set
  val insert: 'a * 'a set -> 'a set
  val equals: 'a set * 'a set -> bool
end;

functor createSet (Element : sig type t end) :> SET =
struct
  type 'a set = 'a list
  val emptyset = []
  fun insert (x, s) = x :: s
  fun equals (s1, s2) = 
    if s1 = s2 then 
        let
          val x = hd(s1)
          val y = hd(s2)
        in
          if x = y then
            equals(tl(s1), tl(s2))
          else
            false
        end
    else
        false
end;

Can you help me solve this problem? And What is the difference between 'a and ''a ? I understand that 'a is a variable that can accept any type

Answer 1

In order to compare things with =, they must be of an equality type.
For example, integers and strings are equality types; reals and functions are not because they don't have a meaningful sense of equality.
(The SML view is more or less that real is just an approximation of real numbers, so can't meaningfully be "equal".)

Given createSet's parameter, I would expect to see something more like this, with the element type being provided by that structure instead of being arbitrary:

signature SET =
sig
  eqtype element (* 'eqtype' specifies that the type must be an equality type *)
  type t
  val emptyset: t
  val insert: element * t -> t
  val equals: t * t -> bool
end;

functor createSet (Element : sig eqtype t end) :> SET =
struct
  type element = Element.t
  type t = element list
  val emptyset = []
  fun insert (x, s) = x :: s
  (* If 'element' is an eqtype, then so is `element list', so = works as expected *)
  fun equals (s1, s2) = s1 = s2 
end;

Example:

- structure IntSet = createSet(struct type t = int end);
structure IntSet : SET
- val s = IntSet.emptyset;
val s = [] : IntSet.t
- IntSet.insert(123, s);
val it = [123] : IntSet.t
- structure StringSet = createSet(struct type t = string end);
structure StringSet : SET
- StringSet.insert("hello", StringSet.emptyset);
val it = ["hello"] : StringSet.t
- structure FunctionSet = createSet(struct type t = int -> int end);
stdIn:41.25-41.66 Error: type t must be an equality type
- 

You can get rid of the equality type requirement by - for instance - adding a function to the Element signature that you use for determining the "equality" of elements.
(Doing it left as an exercise.)