I have an implementation of sets and maps as unbalanced binary trees. Since the sets and cards are so similar, I actually just wrote an implementation for cards from scratch, and then trivially implemented sets as cards from keys to units:
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;
Suppose I came up with a different map implementation using some other data structure. Then I should be able to reuse this data structure to define sets in the form of maps from keys to units:
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;
However, if I arbitrarily come up with many map implementations, overriding sets that use the same data structures as these maps quickly become tedious. I would like it to be a functor that takes a functor from X to MAP and creates a functor from X to SET, where X is any signature that includes EQ (or, possibly, EQ itself). Is this possible in standard ML?