SML 仿函数在不公开实现的情况下公开类型（实现集）

Question

我正在编写一个仿函数来在标准 ML 中实现集合。由于集合不允许重复而且我不希望它被限制为相等类型，它声明如下：

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

我使用 :> 这样列表操作就不能在集合上使用，隐藏内部实现并允许更改表示（例如更改为 BST）

但是，这也隐藏了 type t，因此函数 add 像这样使用时会出错：

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)

有没有办法隐藏实现但以某种方式暴露类型 t？还是有更好的方法来实现集合？

P.S。我不能有相等类型的主要原因是允许集合的集合，虽然我可以保持列表排序并定义 eqtype 'a set，但它增加了不必要的复杂性。

Answer 1

您需要有时称为 半透明 签名归属的东西，也就是说，您隐藏了一些类型并公开了其他类型：

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

Answer 2

您必须使用类型优化公开类型 t：

functor ListSet (Eq : sig type t val equal : t * t -> bool end) :> SET where type t = Eq.t =
struct
  ...
end

这等同于签名 SET 的扩展，其中类型 t 被透明地指定为

type t = Eq.t

SML 仿函数在不公开实现的情况下公开类型（实现集）

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

functional-programming

ml

sml

signature

functor