SML普通型的不同结构

我实现套标ML。目前，它看起来像这样：SML普通型的不同结构

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

有没有办法做到这一点？我知道它可以在顶级声明，但我想隐藏的内部实现，因此使用不透明签名（S）

来源

2017-07-04 zlotnleo

在原则上，有两种方法来执行这样的参数设置：

将函数包装到它自己的函数中，该函数将其他结构作为参数。
使函数多态的，通过有关职能对其他类型的个别参数上操作，或作为参数的记录。

让我们假设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

对于方案二，则需要通过所有相关直接起作用，例如作为记录：

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

来源

2017-07-04 15:53:52

SML普通型的不同结构

回答

相关问题