The Standard Library's Map module is a great example of functors! It implements a Tree Map (a map backed by balanced binary trees). The Map module has a functor in it called make. It makes a Map data structure based on a Map.OrderedType module.
You must pass in module that has two things, a type, t, for the keys, and a comparison function, compare, for the keys.
(The Map module needs a comparison function for the balanced binary tree implementation)
The output of the functor is of type S, which contains all the typical map structures. Let's create a map for days of the week!
First, we'll need a type.
type day = Mon | Tue | Wed | Thu | Fri | Sat | Sun
type day = Mon | Tue | Wed | Thu | Fri | Sat | Sun
We'll also probably want to map a day to an integer:
let int_of_day = function
| Mon -> 1
| Tue -> 2
| Wed -> 3
| Thu -> 4
| Fri -> 5
| Sat -> 6
| Sun -> 7
val int_of_day : day -> int = <fun>
Now let's create a map whose keys are days. We need to create a module for this:
module DayKey = struct
type t = day
(* this is based on the documentation of the map *)
let compare day1 day2 = int_of_day day1 - int_of_day day2
end
module DayKey : sig type t = day val compare : day -> day -> int end
Now we can write a map to map days to whatever else we want!
module DayMap = Map.Make(DayKey)
module DayMap :
sig
type key = DayKey.t
type 'a t = 'a Map.Make(DayKey).t
val empty : 'a t
val is_empty : 'a t -> bool
val mem : key -> 'a t -> bool
val add : key -> 'a -> 'a t -> 'a t
val update : key -> ('a option -> 'a option) -> 'a t -> 'a t
val singleton : key -> 'a -> 'a t
val remove : key -> 'a t -> 'a t
val merge :
(key -> 'a option -> 'b option -> 'c option) -> 'a t -> 'b t -> 'c t
val union : (key -> 'a -> 'a -> 'a option) -> 'a t -> 'a t -> 'a t
val compare : ('a -> 'a -> int) -> 'a t -> 'a t -> int
val equal : ('a -> 'a -> bool) -> 'a t -> 'a t -> bool
val iter : (key -> 'a -> unit) -> 'a t -> unit
val fold : (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
val for_all : (key -> 'a -> bool) -> 'a t -> bool
val exists : (key -> 'a -> bool) -> 'a t -> bool
val filter : (key -> 'a -> bool) -> 'a t -> 'a t
val filter_map : (key -> 'a -> 'b option) -> 'a t -> 'b t
val partition : (key -> 'a -> bool) -> 'a t -> 'a t * 'a t
val cardinal : 'a t -> int
val bindings : 'a t -> (key * 'a) list
val min_binding : 'a t -> key * 'a
val min_binding_opt : 'a t -> (key * 'a) option
val max_binding : 'a t -> key * 'a
val max_binding_opt : 'a t -> (key * 'a) option
val choose : 'a t -> key * 'a
val choose_opt : 'a t -> (key * 'a) option
val split : key -> 'a t -> 'a t * 'a option * 'a t
val find : key -> 'a t -> 'a
val find_opt : key -> 'a t -> 'a option
val find_first : (key -> bool) -> 'a t -> key * 'a
val find_first_opt : (key -> bool) -> 'a t -> (key * 'a) option
val find_last : (key -> bool) -> 'a t -> key * 'a
val find_last_opt : (key -> bool) -> 'a t -> (key * 'a) option
val map : ('a -> 'b) -> 'a t -> 'b t
val mapi : (key -> 'a -> 'b) -> 'a t -> 'b t
val to_seq : 'a t -> (key * 'a) Seq.t
val to_seq_from : key -> 'a t -> (key * 'a) Seq.t
val add_seq : (key * 'a) Seq.t -> 'a t -> 'a t
val of_seq : (key * 'a) Seq.t -> 'a t
end
DayMap must now have keys that are days. Let's map them to their long names (strings):
let m =
let open DayMap in
empty
|> add Mon "Monday"
|> add Tue "Tuesday"
|> add Wed "Wednesday"
|> add Thu "Thursday"
|> add Fri "Friday"
|> add Sat "Saturday"
|> add Sun "Sunday"
val m : string DayMap.t = <abstr>
Note that m is abstract, but we can use the functions that DayMap provides to examine our tree. It's easiest to do that if we just open DayMap here:
open DayMap;;
Let's check if monday is a key in the map!
mem Mon m
- : bool = true
Let's find the value of Tuesday!
find Tue m
- : string = "Tuesday"