Would you please explain OCaml functors to me?

Question

Possible Duplicate:
In Functional Programming, what is a functor?

I don't know much about OCaml, I've studied F# for some time and quite understand it.

They say that F# misses functor model, which is present in OCaml. I've tried to figure out what exactly functor is, but wikipedia and tutorials didn't help me much.

Could you please illuminate that mystery for me? Thanks in advance :)

EDIT:

I've caught the point, thx to everyone who helped me. You can close the question as exact duplicate of: In Functional Programming, what is a functor?

Answer 1

If you come from an OOP universe, then it probably helps to think of a module as analogous to a static class. Similar to .NET static classes, OCaml module have constructors; unlike .NET, OCaml modules can accept parameters in their constructors. A functor is a scary sounding name for the object you pass into the module constructor.

So using the canonical example of a binary tree, we'd normally write it in F# like this:

type 'a tree =
    | Nil
    | Node of 'a tree * 'a * 'a tree

module Tree =
    let rec insert v = function
        | Nil -> Node(Nil, v, Nil)
        | Node(l, x, r) ->
            if v < x then Node(insert v l, x, r)
            elif v > x then Node(l, x, insert v r)
            else Node(l, x, r)

Fine and dandy. But how does F# know how to compare two objects of type 'a using the < and > operators?

Behind the scenes, its doing something like this:

> let gt x y = x > y;;

val gt : 'a -> 'a -> bool when 'a : comparison

Alright, well what if you have an object of type Person which doesn't implement that particular interface? What if you wanted to define the sorting function on the fly? One approach is just to pass in the comparer as follows:

    let rec insert comparer v = function
        | Nil -> Node(Nil, v, Nil)
        | Node(l, x, r) ->
            if comparer v x = 1 then Node(insert v l, x, r)
            elif comparer v x = -1 then Node(l, x, insert v r)
            else Node(l, x, r)

It works, but if you're writing a module for tree operations with insert, lookup, removal, etc, you require clients to pass in an ordering function everytime they call anything.

If F# supported functors, its hypothetical syntax might look like this:

type 'a Comparer =
    abstract Gt : 'a -> 'a -> bool
    abstract Lt : 'a -> 'a -> bool
    abstract Eq : 'a -> 'a -> bool

module Tree (comparer : 'a Comparer) =
    let rec insert v = function
        | Nil -> Node(Nil, v, Nil)
        | Node(l, x, r) ->
            if comparer.Lt v x then Node(insert v l, x, r)
            elif comparer.Gt v x then Node(l, x, insert v r)
            else Node(l, x, r)

Still in the hypothetical syntax, you'd create your module as such:

module PersonTree = Tree (new Comparer<Person>
    {
        member this.Lt x y = x.LastName < y.LastName
        member this.Gt x y = x.LastName > y.LastName
        member this.Eq x y = x.LastName = y.LastName
    })

let people = PersonTree.insert 1 Nil

Unfortunately, F# doesn't support functors, so you have to fall back on some messy workarounds. For the scenario above, I would almost always store the "functor" in my data structure with some auxillary helper functions to make sure it gets copied around correctly:

type 'a Tree =
    | Nil of 'a -> 'a -> int
    | Node of 'a -> 'a -> int * 'a tree * 'a * 'a tree

module Tree =
    let comparer = function
        | Nil(f) -> f
        | Node(f, _, _, _) -> f

    let empty f = Nil(f)

    let make (l, x, r) =
        let f = comparer l
        Node(f, l, x, r)

    let rec insert v = function
        | Nil(_) -> make(Nil, v, Nil)
        | Node(f, l, x, r) ->
            if f v x = -1 then make(insert v l, x, r)
            elif f v x = 1 then make(l, x, insert v r)
            else make(l, x, r)

let people = Tree.empty (function x y -> x.LastName.CompareTo(y.LastName))