Demystifying Ocaml's Functors

cyocum on 2010-05-21T19:31:07

Since I started using Ocaml, functors have been rather mystifying to me. They are Ocaml's highest form of type abstraction through modules and, for beginners like myself, they can be down right frustrating to understand. So, I took it upon myself to learn how to write one of these things by hook or by crook. Here is what I took away from that experience.

What will do here is take you through a trivial and probably completely useless example of a Functor which creates types of Linked Lists. You will need to know about Ocaml before you dig into this so I recommend having a look over here.

So, first you need to have a module type for which you will create a functor:

module type S =
sig
  type t
end;;

This creates a module type with only one thing in it: a generic type expression. Basically, this says: if a module is of type S then it will have a type t defined in it.

Now for the functor itself:

module Make (LinkedList : S) =
struct
  type t = Empty | Node of LinkedList.t * t ref

  let make () =
    ref Empty

  let insert x ll =
    let new_node = Node(x, ref Empty) in
      match new_node, !ll with
	  Node(_, next), Empty ->
	    next := Empty;
	    ll := new_node
	| Node(_, next1), (Node(_, next2) as head) ->
	    next1 := head;
	    ll := new_node
	| Empty, _ -> raise (Invalid_argument "Empty Argument")
  ;;

  let rec search x ll =
    match !ll with
 	Empty -> false
      | Node(y, next) -> 
 	  if x = y then 
 	    true
 	  else 
 	    search x next
   ;;
end;;

What you should notice here is that there is code here. Basically, any code that can be written without a reference to the type of thing being written should be put here. You should notice the LinkedList.t in the type expression at the top of the module. (LinkedList : S) means that LinkedList is of type S so has a different type than Make's type t (remember Make is itself a kind of module).

Now, we want to make LinkedList.t a concrete type. We do this by applying the Make functor to the module that we want to apply that functor to. So basically we want to apply the module type S to the module that we will create and attach the code in Make to that module. So, let's do that:

See the struct inside the Make? That is your module that you want to attach the code in Make to. Because the module is of type S you must now declare what type t is. This is also the case for ANY functions in module type S. You can actually define the module else where with a name and pass that name into Make.

Now, when you put this into the top level of Ocaml, you should get this signature:

module IntLinkedList :
  sig
    type t = Empty | Node of int * t ref
    val make : unit -> t ref
    val insert : int -> t ref -> unit
    val search : int -> t ref -> bool
  end

Note how the line in Make: type t = Empty | Node of LinkedList.t * t ref has been replaced by the type that you specified in the call to Make. This means that this is now a Module that creates Linked Lists of Ints.

You can now stack Functor created modules like so:

module IntSet = Set.Make(struct type t = int let compare = compare end);;
module LinkedListIntSet = Make(IntSet);;

module IntSetLinkedList :
  sig
    type t = Make(IntSet).t = Empty | Node of IntSet.t * t ref
    val make : unit -> t ref
    val insert : IntSet.t -> t ref -> unit
    val search : IntSet.t -> t ref -> bool
  end

Now, you may be wondering to yourself: why has he gone through all this trouble when he could have just used type parameters? That's the canonical way to write linked lists in Ocaml. It is just as type safe and probably faster. However, I can use a sledge hammer to crack a nut. This small example, however, shows all the steps that you need to go through to write a functor in the first instance. This is also small enough to understand. I hope it helps those out there grappling with the idea of functors.