4
불균형 이진 트리로 세트와 맵을 구현했습니다. 세트와 맵이 너무 비슷하기 때문에, 사실만을 처음부터지도에 대한 구현을 작성하고 하찮게 단위로 키에서지도로 세트를 구현 :Standard ML Functor가 다른 Functor를 매개 변수로 사용할 수 있습니까?
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까지 functor를 가져 와서 X에서 SET까지 functor를 생성하는 functor가 있습니다. 여기서 X는 EQ (또는 아마도 EQ 자체)를 포함하는 모든 시그니처입니다. 표준 ML에서 가능합니까?