Skip navigation

Let’s talk about Functors in the OCaml programming language. I will assume that you know about modules in OCaml, if not you can refresh by reading the manual.

Functors are “functions” from structures to structures.

The above is probably the best definition I’ve seen of a functor. It touches on what I see as the main motivation behind using a functor. A Functor being a function from structure to structure means that if you keep the signature of the input structure and the signature of the output structure constant, you are free to change the implementation details without affecting any of the modules that use it. Functors allow the software designer an easy way of avoiding duplication, increasing orthogonality, all in a type safe package.

Let’s write an algorithm to determine if a string contains balanced parentheses. To start, we’ll define the type of stack we want to work with:

module type STACK = sig
  type 'a t
  exception Empty
  val create : unit -> 'a t
  val push : 'a -> 'a t -> unit
  val pop : 'a t -> 'a
  val is_empty : 'a t -> bool
end

Here we have the basic operations on a very minimalist stack. Now, we’ll create a functor that will take a stack structure of this type and return a module containing our parenthesis matching algorithm.

module Matcher (S : STACK) = struct
  let is_balanced str =
    let s = S.create () in try
      String.iter
        (fun c -> match c with
            '(' -> S.push c s
          | ')' -> ignore (S.pop s)
          | _ -> ()) str;
        S.is_empty s
    with S.Empty -> false
end

While we rely on the Stack with the STACK type to not change the semantics of its functions, we can guarantee that for any stack with this kind of structure and with the right semantics, our algorithm will work. Any use of this functor will create a module with one function: val is_balanced : string -> bool. This also means that if we maintain the signature of the functor we just wrote, we can change any of the implementation details and not affect the outside world.

To use a different stack, all we have to do is change one line of code from module M = Matcher(Stack) to module M = Matcher(CStack) to change our algorithm to use a stack that keeps a count of the number of things pushed onto it in its lifetime.

Conclusion: functors allow you to write code that will work irrespective of the implementation of the given structure (so long as it does what it should), and produces a structure containing functions that we are free to modify, but only have to change in one location, that of the functor.

About these ads

3 Trackbacks/Pingbacks

  1. By More Functors « Stateless on 10 Apr 2009 at 11:21 am

    [...] April 2009 Aside from the features mentioned in my previous article, functors can also provide you with the ability to add more functions to the resulting [...]

  2. By Top Posts « WordPress.com on 10 Apr 2009 at 5:33 pm

    [...] Functors for the Beginner Let’s talk about Functors in the OCaml programming language. I will assume that you know about modules in OCaml, [...] [...]

  3. [...] to compare keys, and it gets the comparison function from the functor’s parameter.)” 2. alexleighton博客上关于Functor的叙述: “A Functor being a function from structure to structure means [...]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: