2017-10-18 170 views
2

我想編寫一個類似的集合如下。如何實現sml的類型?

signature COMPARABLE_SET= 
sig 
    type 'a set 
    val empty: 'a set 
    val insert: 'a * 'a set -> 'a set 
    val member: 'a * 'a set -> bool 
end 

我需要限制元件在「的一組類型是可比較:(存在與類型的函數:'a * 'a -> order)。

如何實現它?

+0

看看如何定義SML/NJ庫中的ORD_SET簽名:http://www.smlnj.org/doc/smlnj-lib/Manual/ord-set.html#ORD_SET:SIG: SPEC –

+1

另外,您想要的內容不能以SML中的安全方式書寫。我撰寫了兩篇與此主題相關的博文:http://igstan.ro/posts/2017-04-08-a-safe-type-in​​dexed-set-for-standard-ml.html和http:// igstan.ro/posts/2017-04-12-a-safe-type-in​​dexed-set-for-standard-ml-errata.html。 –

回答

4

如果你想這樣做OCaml中,這是一個簡單的仿函數情況:

首先,你需要定義元素的類型:

module type OrderedType = sig 
    type t 
    val compare : t -> t -> int 
end 

然後你將定義一個這種類型的函數:

module MakeComparableSet (Ord : OrderedType) : 
    sig 
    type elt = Ord.t 
    type t 
    val empty : t 
    val insert : elt -> t -> t 
    val member : elt -> t -> bool 
    end = struct 
    type elt = Ord.t 
    type t 
    let empty = failwith "TODO" 
    let insert = failwith "TODO" 
    let member = failwith "TODO" 
    end 

這正是什麼製作here


您可以在模塊上看到一個函子,它將創建新的模塊。這裏,函數ComparableSet採用簽名OrderedType的模塊並返回一個模塊,該模塊是一個集合。