Slash Boxes
NOTE: use Perl; is on undef hiatus. You can read content, but you can't post it. More info will be forthcoming forthcomingly.

All the Perl that's Practical to Extract and Report

use Perl Log In

Log In

[ Create a new account ]

cyocum (7706)

  (email not shown publicly)

An American post-graduate student living in Scotland.

Journal of cyocum (7706)

Friday May 21, 2010
02:31 PM

Demystifying Ocaml's Functors

[ #40362 ]

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 =
  type t

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) =
  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
         search x next

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:

module IntLinkedList = Make(struct type t = int end);;

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 :
    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

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 :
    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

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.

The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
More | Login | Reply
Loading... please wait.