SML 不同结构的通用类型

Question

我正在标准 ML 中实现集合。目前看起来像这样：

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

我希望 map 函数能够接受结构 SET 中的任何集合，理想情况下甚至不限于来自 ListSetFn 仿函数的集合。但是，在顶层，它只能对由单个结构创建的集合进行操作：调用它的结构，例如：

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

虽然我真的很喜欢

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

有办法吗？我知道它可以在顶层声明，但我想隐藏内部实现并因此使用不透明签名

Answer 1

原则上，有两种方法可以执行这样的参数化：

将函数包装到它自己的函子中，将另一个结构作为参数。
使函数成为多态的，将相关函数作为单独的参数或作为参数记录传递给其他类型。

我们假设 SET 签名包含这些函数：

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

那么前一个解决方案将如下所示：

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

对于解决方案 2，您需要直接传递所有相关函数，例如作为记录：

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，使用 first-class 结构会更好，但 SML 没有将它们作为标准功能。

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

SML 不同结构的通用类型

SML Common type for different structures

functional-programming

sml

functor

signature

ml