標準ML仿函數可以使用另一個仿函數作爲參數嗎？

我有一個集合和映射作爲不平衡二叉樹的實現。由於集和地圖是如此相似，其實我只寫了一個實現了從無到有的地圖，然後以一般實現集作爲地圖從鍵單位：標準ML仿函數可以使用另一個仿函數作爲參數嗎？

signature EQ = 
sig 
    type t; 

    val eq : t * t -> bool; 
end; 

signature ORD = 
sig 
    include EQ; 

    val lt : t * t -> bool; 
end; 

signature SET = 
sig 
    structure Elem : EQ; 
    type  set; 

    val empty : set; 
    val member : Elem.t * set -> bool; 
    val insert : Elem.t * set -> set option; 
end; 

signature MAP = 
sig 
    structure Key : EQ; 
    type  'a map; 

    val empty : 'a map; 
    val lookup : Key.t  * 'a map -> 'a option; 
    val insert : Key.t * 'a * 'a map -> 'a map option; 
end; 

functor UnbalancedMap (Key : ORD) :> MAP = 
struct 
    structure Key  = Key; 
    datatype 'a tree = E | T of Key.t * 'a * 'a tree * 'a tree; 
    type  'a map = 'a tree; 

    val empty = E; 

    fun lookup (k, t) = 
    let 
     fun loop (k, E, E) = NONE 
     | loop (k, E, T (x, y, _, _)) = 
      if Key.eq (k, x) then SOME y 
          else NONE 
     | loop (k, t as T (x, _, a, b), r) = 
      if Key.lt (k, x) then loop (k, a, r) 
          else loop (k, b, t); 
    in 
     loop (k, t, E) 
    end; 

    fun insert (k, v, t) = 
    let 
     exception Exists; 

     fun loop (k, v, E, E) = T (k, v, E, E) 
     | loop (k, v, E, T (x, _, _, _)) = 
      if Key.eq (k, x) then raise Exists 
          else T (k, v, E, E) 
     | loop (k, v, t as T (x, y, a, b), r) = 
      if Key.lt (k, x) then T (x, y, loop (k, v, a, r), b) 
          else T (x, y, a, loop (k, v, b, t)); 
    in 
     SOME (loop (k, v, t, E)) handle Exists => NONE 
    end; 
end; 

functor UnbalancedSet (Elem : ORD) :> SET = 
struct 
    structure Map = UnbalancedMap (Elem); 
    structure Elem = Map.Key; 
    type  set = unit Map.map; 

    val empty = Map.empty; 

    fun member (x, t) = case Map.lookup (x, t) of 
     NONE => false 
    | _ => true; 

    fun insert (x, t) = Map.insert (x,(), t); 
end;

假設我想出了使用一些地圖的另一種實現方式其他數據結構。然後，我應該能夠重複使用的數據結構來定義組從鍵映射到單位，以及：

functor AnotherMap (Key : EQ) :> MAP = 
struct 
    (* ... *) 
end; 

functor AnotherSet (Elem : EQ) :> SET = 
struct 
    structure Map = AnotherMap (Elem); 
    structure Elem = Map.Key; 
    type  set = unit Map.map; 

    val empty = Map.empty; 

    fun member (x, t) = case Map.lookup (x, t) of 
     NONE => false 
    | _ => true; 

    fun insert (x, t) = Map.insert (x,(), t); 
end;

但是，如果我拿出地圖的任意許多實現中，重新定義使用相同的數據結構集因爲這些地圖很快變得乏味。我真正想要的是一個函子，它從X到MAP接收一個函子，併產生一個從X到SET的函子，其中X是包含EQ（或可能EQ本身）的任何簽名。這是可能的標準ML？

來源

2013-04-29 pyon

作爲一個非標準擴展，是的。我相信你正在尋找的功能被SML/NJ稱爲「高階函子」。關於它們的實現，這裏有一些有限的detail。

我強調這是而不是 SML的標準功能。直接使用SML模塊系統無法實現這一點。

來源

2013-04-29 13:41:11 Gian

標準ML仿函數可以使用另一個仿函數作爲參數嗎？

回答

相關問題