Functor

A type constructor f with a map operation, fmap : (a -> b) -> f a -> f b, that preserves identity and composition. Lists, options, trees and functions out of a fixed type are functors. In OCaml the word also means something else: a module parametrised by another module, such as Map.Make.

The two laws:

In category theory a functor $F:\mathcal{C}\to \mathcal{D}$ sends each object $A$ to $FA$ and each arrow $f:A\to B$ to $Ff:FA\to FB$, preserving identities and composition. A type constructor with a lawful fmap is a functor from the category of types and functions to itself: list sends $a$ to $alist$, and List.map sends $f$ to its action on lists.

(* The same shape of map for different type constructors. *)
type 'a tree = Leaf | Node of 'a tree * 'a * 'a tree
 
let rec map_tree f = function
  | Leaf -> Leaf
  | Node (l, x, r) -> Node (map_tree f l, f x, map_tree f r)
 
(* Functions out of a fixed type: mapping is composition. *)
let map_reader f g = fun r -> f (g r)
 
(* Pairs: map over the second component. *)
let map_pair f (a, b) = (a, f b)
 
(* A module functor, OCaml's other meaning of the word: a module
   parametrised by a module. *)
module IntMap = Map.Make (Int)

map_tree (fun x -> x * 10) t      ->  [10; 20; 30]
identity law:     map id t = t    ->  true
composition law:  holds on t      ->  true
map_reader succ String.length "abc"  ->  4
map_pair succ ("x", 1)            ->  ("x", 2)
IntMap.bindings                   ->  [(1, a); (3, c)]

A type is a functor in a parameter when the parameter occurs only in covariant positions: to the right of arrows, inside other functors. In $r\to a$ the $a$ is covariant, and mapping is composition. In $a\to r$ it is contravariant, and no fmap exists; such a type maps the other way, $(b\to a)\to (a\to r)\to (b\to r)$, which makes it a contravariant functor.

For a given type there is at most one fmap satisfying the identity law. This follows from parametricity, so writing fmap is a matter of finding the only function that type-checks and keeps the shape.

OCaml's module functors, like Map.Make, take a module and return a module. They are not related to fmap beyond the name: both come from the category-theoretic term, one applied to modules and signatures, the other to types and functions.

• ApplicativeA functor with pure : a -> f a and a way to combine independent computations, <*> : f (a -> b) -> f a -> f b, or equivalently product : f a -> f b -> f (a * b). Every monad is applicative, but applicatives are strictly more general: because later steps cannot depend on earlier results, effects can be accumulated, parallelised or inspected before running.
• MonadIn functional programming, a monad is a type constructor m with two operations, return : a -> m a and bind : m a -> (a -> m b) -> m b, satisfying three laws. It lets code with some extra behaviour, such as failure, several results, configuration, state or I/O, be written as a sequence of ordinary steps, with the behaviour defined once in bind. The notion comes from category theory.
• Yoneda lemmaFor a functor F and an object a, natural transformations from Hom(a, -) to F correspond one to one with elements of F a. In Haskell, forall b. (a -> b) -> f b is isomorphic to f a, and the left-hand form turns a chain of fmaps into one composed function and a single fmap.
• Higher-kinded typeA type that abstracts over a type constructor rather than over a type, so that Functor f can be instantiated at Maybe or at lists without naming their element types. It is what makes a single Monad class usable across every container instead of one class per shape.
• HylomorphismA function that unfolds a seed into a recursive structure and folds that structure into a result, written so the structure is never built: hylo f g = f . fmap (hylo f g) . g. The call tree of the recursion is the intermediate structure.

1. [1]S. Mac Lane, Categories for the Working Mathematician, Springer (2nd ed., 1998).
2. [2]P. Wadler, “Theorems for free!”, FPCA (1989).
3. [3]The OCaml manual, “Functors”, in the chapter on the module system.