标准ML的functor能否以另一个functor作为参数？

Question

我有一个基于非平衡二叉树的集合和映射实现。由于集合和映射非常相似，我实际上只编写了从头开始的映射实现，并通过将键映射到元素的方式轻松地实现了集合：

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中是否可能实现这一点？

- pyon

Answer 1

作为一种非标准扩展，是的。 我相信您要寻找的功能被SML / NJ称为“高阶函数子”。 在这里可以找到关于它们实现的一些有限 详细信息。

我强调这不是SML的标准功能。 不能直接使用SML模块系统实现此功能。

- Gian