What's the difference between functors and "generics"

Question

I'm looking at OCaml's functors. It looks to me pretty identical to the so called generic objects in C++/C#/Java. If you ignore Java's type erasion for now, and ignore the implementation details for C++ templates (I'm interested with the language feature), functors are quite indentical to generics. If I understand it correctly, functor gives you a new set of functions from a type you provide, so that for example

List<MyClass>.GetType() != List<MyOtherClass>.GetType()

But you could roughly rewrite OCaml's

#module Set =
   functor (Elt: ORDERED_TYPE) ->
     struct
       type element = Elt.t
       type set = element list
       let empty = []
       let rec add x s =
         match s with
           [] -> [x]
         | hd::tl ->
            match Elt.compare x hd with
              Equal   -> s         (* x is already in s *)
            | Less    -> x :: s    (* x is smaller than all elements of s *)
            | Greater -> hd :: add x tl
       let rec member x s =
         match s with
           [] -> false
         | hd::tl ->
             match Elt.compare x hd with
               Equal   -> true     (* x belongs to s *)
             | Less    -> false    (* x is smaller than all elements of s *)
             | Greater -> member x tl
     end;;

into C#

class Set<T> where T : ISortable
{
    private List<T> l = new List<T>();
    static public Set<T> empty = new Set<T>();
    public bool IsMember(T x) {return l.IndexOf(x) > -1;}
    public void Add(T x) {l.Add(x);}
}

Sure there's a slight different since a functor affects a Module (which is just a bunch of types function and values definitions, similar to C#'s namespace).

But is it just it? Are functors merely generics applied to namespaces? Or is there any signifcant different between functors and generics which I'm missing.

Even if functors are just generics-for-namespace, what's the significant advantage of that approach? Classes can also be used as ad-hoc namespaces using nested classes.

Answer 1

But is it just it? Are functors merely generics applied to namespaces?

Yes, I think one can treat functors as "namespaces with generics", and that by itself would be very welcome in C++ where the only option left is to use classes with all static members which becomes pretty ugly soon. Comparing to C++ templates one huge advantage is the explicit signature on module parameters (this is what I believe C++0x concepts could become, but oops).

Also modules are quite different from namespaces (consider multiple structural signatures, abstract and private types).

Even if functors are just generics-for-namespace, what's the significant advantage of that approach? Classes can also be used as ad-hoc namespaces using nested classes.

Not sure whether it qualifies for significant, but namespaces can be opened, while class usage is explicitly qualified.

All in all - I think there is no obvious "significant advantage" of functors alone, it is just different approach to code modularization - ML style - and it fits nicely with the core language. Not sure whether comparing module system apart from the language makes much sense.

PS C++ templates and C# generics are also quite different so that comparing against them as a whole feels little strange.

Answer 2

If I understand it correctly, functor gives you a new set of functions from a type you provide

More generally, functors map modules to modules. Your Set example maps a module adhering to the ORDERED_TYPE signature to a module implementing a set. The ORDERED_TYPE signature requires a type and a comparison function. Therefore, your C# is not equivalent because it parameterizes the set only over the type and not over the comparison function. So your C# can only implement one set type for each element type whereas the functor can implement many set modules for each element module, e.g. in ascending and descending order.

Even if functors are just generics-for-namespace, what's the significant advantage of that approach?

One major advantage of a higher-order module system is the ability to gradually refine interfaces. In OOP, everything is public or private (or sometimes protected or internal etc.). With modules, you can gradually refine module signatures at will giving more public access closer to the internals of a module and abstracting more and more of it away as you get further from that part of the code. I find that to be a considerable benefit.

Two examples where higher-order module systems shine compared to OOP are parameterizing data structure implementations over each other and building extensible graph libraries. See the section on "Structural abstraction" in Chris Okasaki's PhD thesis for examples of data structures parameterized over other data structures, e.g. a functor that converts a queue into a catenable list. See OCaml's excellent ocamlgraph library and the paper Designing a Generic Graph Library using ML Functors for an example of extensible and reusable graph algorithms using functors.

Classes can also be used as ad-hoc namespaces using nested classes.

In C#, you cannot parameterize classes over other classes. In C++, you can do some things like inheriting from a class passed in via a template.

Also, you can curry functors.