SML Common type for different structures

Question

I am implementing sets in Standard ML. Currently it looks like this:

signature SET = sig
    type t
    type 'a set
    ...
    val map : ('a -> t) -> 'a set -> t set
end

functor ListSetFn (EQ : sig type t val equal : t * t -> bool end)
        :> SET where type t = EQ.t = struct
    type t = EQ.t
    type 'a set = 'a list
    ...
    fun map f = fromList o (List.map f)
end

I want the map function to be able to take any set in a structure SET, ideally not even constrained to those from ListSetFn functor. However, on the top level it can only operate on sets created by a single structure: the one it is called from, e.g.:

functor EqListSetFn(eqtype t) :> SET where type t = t = struct
    structure T = ListSetFn(struct type t = t val equal = op= end)
    open T
end

structure IntSet = EqListSetFn(type t = int)
IntSet.map : ('a -> IntSet.t) -> 'a IntSet.set -> IntSet.t IntSet.set

While I'd really like it to be something like

IntSet.map : ('a -> IntSet.t) -> 'a ArbitrarySet.set -> IntSet.t IntSet.set

Is there a way to do it? I know it could be declared on the top level, but I want to hide the internal implementation and hence use opaque signature(s)

Answer 1

In principle, there are two ways to perform such a parameterisation:

1. Wrap the function into its own functor, that takes the other structure as argument.

2. Make the function polymorphic, passing the relevant functions to operate on the other type as individual arguments, or as a record of arguments.

Let's assume the SET signature contains these functions:

val empty : 'a set
val isEmpty : 'a set -> bool
val add : 'a * 'a set -> 'a set
val remove : 'a * 'a set -> 'a set
val pick : 'a set -> 'a

Then the former solution would look like this:

functor SetMap (structure S1 : SET; structure S2 : SET) =
struct
  fun map f s =
    if S1.isEmpty s then S2.empty else
    let val x = S1.pick s
    in S2.add (f x, map f (S2.remove (x, s)))
    end
end

For solution 2, you would need to pass all relevant functions directly, e.g. as records:

fun map {isEmpty, pick, remove} {empty, add} f s =
    let
      fun iter s =
        if isEmpty s then empty else
        let val x = pick s
        in add (f x, iter (remove (x, s)))
        end
    in iter s end

FWIW, this would be nicer with first-class structures, but SML does not have them as a standard feature.

fun map (pack S1 : SET) (pack S2 : SET) f s =
    let
      fun iter s =
        if S1.isEmpty s then S2.empty else
        let val x = S1.pick s
        in S2.add (f x, iter (S2.remove (x, s)))
        end
    in iter s end