Functors are basically modules parameterized with other modules.
This is an incredible boon to expressiveness, because it lets
you turn a combinatorial growth in the number of implementations
into linear growth.

This is best seen with an example. I'll use Objective Caml because
that's the dialect I know the best. Suppose that we have an interface
for priority queues. This might look like the following

module type Q =
  sig
    type key
    type q

    val empty : q

    val add : key -> q -> q  (* Add an element to the queue *) 
    val max : q -> key       (* Get the highest priority element *)
    val del : q -> q         (* Delete the highest priority element *)
  end

When actually implementing the queue, there are two dimensions
of implementation: the data structure used to represent the
priority queue, and the order relation on the elements of the
queue.

In a Java-like language, the way one would do this is to first
define an interface for the priority queue, and then for
each different data structure you would define an abstract
method for the comparison routine. Then, you'd specialize
each class with concrete implementations.

So if you had (say) 5 different queue structures, and 10 different
comparison routines, then there would need to be 5 x 10 = 50
concrete implementation classes. Worse, there would be a lot
of duplication, since every comparison would have to be textually
repeated 5 times.

Functors let you break that problem, and write just the 5
different data structures and the 10 comparisons, and then
combine them. That's 5 + 10 = 15 bits of code you need to
write, and there's no duplication whatsoever.

So what you'd do is define an interface for the comparisons,
like this:

module type ORD =
  sig
    type t

    val cmp : t -> t -> int (* An ordering relation; when two elements
                               x & y are compared, return
                               
                                           { -1, if x < y
                                 cmp x y = {  0, if x = y
                                           { +1, if x > y 
                            *)
  end

And writing some parameterized modules -- functors. Here are two
implementing priority queues as sorted lists and as binary trees:

module ListQueue(Elt : ORD) : Q with type key = Elt.t = 
  struct
    type key = Elt.t
    type q = key list

    let empty = []

    let rec add x q =
      match q with
        [] -> [x]
      | x' :: q' when Elt.cmp x x' < 0 ->
          x' :: (add x q')
      | _ -> x :: q

    let max q = List.hd q

    let del q = List.tl q
  end 

module TreeQueue(Elt : ORD) : Q with type key = Elt.t = 
  struct
    type key = Elt.t

    type q = Nil | Node of q * key * q

    let empty = Nil

    let rec add key q =
      match q with
        Nil ->
          Node(Nil, key, Nil)
      | Node(left, key', right) when Elt.cmp key key' < 0 ->
          Node(add key left, key', right)
      | Node(left, key', right) when Elt.cmp key key' > 0 ->
          Node(left, key, add key right)
      | Node(left, key', right) -> 
          Node(left, key, right)

    let rec max q =
      match q with
        Nil ->
          raise Not_found
      | Node(left, key, Nil) -> 
          key
      | Node(left, key, right) -> 
          max right

    let rec del q =
      match q with
        Nil ->
          raise Not_found
      | Node(left, key, Nil) -> 
          left
      | Node(left, key, right) -> 
          Node(left, key, del right)
  end

Note that some of the capabilities of functors are provided
by multiple inheritance used in a mixin style. However, this
is quite fragile vis-a-vis functors because all the internals
of each mixin class are visible in the subclass, whereas with
functors only the specified interface is available, /and/ it's
in another namespace. Also, the benefits of functors get larger
and larger as the number of possible ways to combine your
program grow.

They are a bit similar, but not precisely the same thing.

The difficulty in comparing them is mostly due to the fact that the
C++ standards committee was careless in the template specification
and accidentally got something a lot more powerful than they expected.
As a result, templates are a very weird language construct -- they
were intended to make parametric polymorphism easier to do but
are actually capable of a lot more than that.

Parametric polymorphism is the ability to write a function that
operates the same way on multiple types. The simplest example is
the identity function

  # let identity x = x
  val identity : 'a -> 'a 

The function identity simply returns its argument, and the type 'a -> 'a
indicates that it can accept any type argument. Similarly, you can
write a polymorphic length function for lists like this:

 # let rec len x =
     match x with
       [] -> 0
     | x :: xs -> 1 + len xs

 val len: 'a list -> int

Here, you can see that len operates on lists of any element -- that's what
the type 'a list means. The translations for identity and len in C++ are
two of the first examples people see when using templates.

Note that there are no type declarations in the OCaml code; the compiler
automatically infers the most general typing for every expression
submitted to the compiler, and will signal a compile error if there is
no correct type for the code. This is different from C++, where every
type has to be explicitly declared, and every polymorphic function
needs to be enclosed in an explicit template expression.

Note that parametric polymorphism is a very specific kind of polymorphim:
a polymorphic function does exactly the same thing regardless of the
types of the arguments. Sometimes you need to parameterize your code
so that it does different things at different types. This is what ML
offers functors for -- they let you write modules that are parameterized
with other modules.

C++ uses templates plus inheritance to model this case, plus some linking games. This is IME rather complicated, and doesn't map to how people
think about it. Not a fatal problem, but definitely an annoyance. The
real killer argument for me is that functors and parametric polymorphism
do not break separate compilation and do not cause code bloat. Due to
the way they are specified, a compiler can generate a single piece of
code for each polymorphic function and each functor.

Passing an explicit comparison function/object would work in ML too, but I left it out of the list of possibilities because it's not as type-safe a solution, and I wanted to compare maximally safe solutions in both languages.

Eg, two priority queues with different ordering schemes would have the same signature, which means that it's possible to (for example) incorrectly merge two queues with different ordering schemes. If each kind of ordering is a queue with a different type, then this error can get caught at compile-time. With the signature I outlined it's not a big deal, but for things like a Set class (which have union and intersection methods) it becomes a more significant problem.