Would you please explain OCaml functors to me? [duplicate]

This questio开发者_运维问答n already has answers here: Closed 10 years ago.

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?

---

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

---

Functors are modules parameterized by modules, i.e. a reflection from modules to modules (ordinary function is reflection from values to values, polymorphic function is reflection from types to ordinary functions).

See also ocaml-tutorial on modules.

Examples in the manual are helpful too.

---

Check out this data structures in ocaml course:

http://www.cs.cornell.edu/Courses/cs3110/2009fa/lecturenotes.asp

the functor lecture: http://www.cs.cornell.edu/Courses/cs3110/2009fa/lectures/lec10.html

and the splay tree implementation using functor: http://www.cs.cornell.edu/Courses/cs3110/2009fa/recitations/rec-splay.html