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

В принципе, есть два способа выполнить такую ​​параметризацию:

1. Оберните функцию в ее собственный функтор, который принимает в качестве аргумента другую структуру.

2. Сделайте функцию полиморфной, передав соответствующие функции для работы с другим типом как отдельные аргументы или как запись аргументов.

Давайте предположим, что 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, это было бы лучше с первоклассными структурами, но 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