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.

## 3 Trackbacks/Pingbacks

[…] 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 […]

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

[…] 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 […]