How are functors in Haskell and OCaml similar?

Question

I've been toying around in a Haskell for the past year or so and I'm actually starting to 'get' it, up until Monads, Lenses, Type Families, ... the lot.

I'm about to leave this comfort zone a little and I am moving to an OCaml project as a day job. Going through the syntax a little I was looking for similar higher level concepts, like for example functor.

I read the code in OCaml and the structure of a functor but I cannot seem to get whether they are now similar concepts in Haskell and OCaml or not. In a nutshell, a functor in Haskell is for me mainly a way to lift functions in Haskell and I use it (and like it) like that. In OCaml it gives me the feeling that it's closer to programming to an interface (for example when making a set or a list, with that compare function) and I wouldn't really know how to for example lift functions over the functor or so.

Can somebody explain me whether the two concepts are similar and if so what am I missing or not seeing? I googled around a bit and there doesn't seem to be a clear answer to be found.

Kasper

Answer 1

From a practical standpoint, you can think of "functors" in OCaml and Haskell as unrelated. As you said, in Haskell a functor is any type that allows you to map a function over it. In OCaml, a functor is a module parametrized by another module.

In Functional Programming, what is a functor? has a good description of what functors in the two languages are and how they differ.

However, as the name implies, there is actually a connection between the two seemingly disparate concepts! Both language's functors are just realizations of a concept from category theory.

Category theory is the study of categories, which are just arbitrary collections of objects with "morphisms" between them. The idea of a category is very abstract, so "objects" and "morphisms" can really be anything with a few restrictions—there has to be an identity morphism for every object and morphisms have to compose.

The most obvious example of a category is the category of sets and functions: the sets are the objects and the functions between sets the morphisms. Clearly, every set has has an identity function and functions can be composed. A very similar category can be formed by looking at a functional programming language like Haskell or OCaml: concrete types (e.g. types with kind *) are the objects and Haskell/OCaml functions are the morphisms between them.

In category theory, a functor is a transformation between categories. It is like a function between categories. When we're looking at the category of Haskell types, a functor is essentially a type-level function: it maps types to something else. The particular kind of functor we care about maps types to other types. A perfect example of this is Maybe: Maybe maps Int to Maybe Int, String to Maybe String and so on. It provides a mapping for every possible Haskell type.

Functors have one additional requirement—they have to map the category's morphisms as well as the objects. In particular, if we have a morphism A → B and our functor maps A to A' and B to B', it has to map the morphism A → B to some morphism A' → B'. As a concrete example, let's say we have the types Int and String. There are a whole bunch of Haskell functions Int → String. For Maybe to be a proper functor, it has to have a function Maybe Int → Maybe String for each of these.

Happily, this is exactly what the fmap function does—it maps functions. For Maybe, it has the type (a → b) → Maybe a → Maybe b; we can add some parentheses to get: (a → b) → (Maybe a → Maybe b). What this type signature tells us is that for any normal function we have, we also have a corresponding function over Maybes.

So a functor is a mapping between types that also preserves the functions between them. The fmap function is essentially just a proof of this second restriction on functors. This makes it easy to see how the Haskell Functor class is just a particular version of the mathematical concept.

So what about OCaml? In OCaml, a functor is not a type—it's a module. In particular, it's a parametrized module: a module that takes another module as an argument. Already, we can see some parallels: in Haskell, a Functor is like a type-level function; in OCaml, a functor is like a module-level function. So really, it's the same mathematical idea; however, instead of being used on types—like in Haskell—it's used on modules.

There's far more detail about how OCaml functors related to category theory functors on the CS site: What is the relation between functors in SML and Category theory?. The question talks about SML rather than OCaml per se, but my understanding is that the module system of OCaml is very closely related to that of SML.

In summary: functors in Haskell and in OCaml are two fundamentally different structures which both happen to be reifications of the same very abstract mathematical idea. I think it's pretty neat :).