Can a Standard ML functor take another functor as parameter?
functor, ml, sml
Solution
As a non-standard extension, yes. I believe the feature you are looking for is called 'higher order functors' by SML/NJ. Here's some limited detail on their implementation.
I stress that this is not a standard feature of SML, though. It is not possible to achieve this directly using the SML module system.
Problem
I have an implementation of sets and maps as unbalanced binary trees. Because sets and maps are so alike, I actually only wrote an implementation for maps from scratch, and then trivially implemented sets as maps 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; ``` Let's assume I come up with another implementation of maps using some other data structure. Then I should be able to reuse that data structure to define sets as maps from keys to units as well: ``` 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 come up with arbitrarily many implementations of maps, redefining sets that use the same data structures as those maps quickly becomes tedious. What I would really like to have is a functor that takes a functor from X to MAP, and produces a functor from X to SET, where X is any signature that includes EQ (or possibly EQ itself). Is this possible in Standard ML?