SML functor expose a type without exposing implementation (implementing sets)

Question

I'm writing a functor to implement sets in standard ML. Since sets don't allow duplicates and I don't want it to be constrained to equality types, it's declared like this:

signature SET = sig
    type t
    type 'a set

    val add : t -> t set -> t set
    ...
end

functor ListSet (EQ : sig type t val equal : t * t -> bool end) :> SET = struct
    type t = EQ.t
    type 'a set = 'a list

    fun add x s = ...
    ...
end

I use :> so that list operations cannot be used on sets, hiding the internal implementation and allowing to change the representation (e.g. to a BST)

However, this also hides type t, therefore function add when used like this gives an error:

structure IntSet = ListSet (struct type t = int val equal = op= end);
val s0 = IntSet.empty
val s1 = IntSet.add 0 s0

Function: IntSet.add : IntSet.t -> IntSet.t IntSet.set -> IntSet.t IntSet.set
Argument: 0 : int
Reason:
  Can't unify int (*In Basis*) with
    IntSet.t (*Created from applying functor ListEqSet*)
    (Different type constructors)

Is there a way to keep the implementation hidden but somehow expose the type t? Or is there a better approach to implementing sets?

P.S. The main reason I can't have equality types is to allow sets of sets, and while I can keep the lists sorted and define eqtype 'a set, it adds unnecessary complexity.

Answer 1

You need what's sometimes called a translucent signature ascription, that is, you hide some of the types and expose the others:

functor ListSet (Eq : EQ) :> SET where type t = Eq.t = ...