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普通型的不同結構

回答

相關問題