Functor

In functional programming, a functor is a type constructor $F$ with an operation $fmap:(a\to b)\to Fa\to Fb$ that applies a function to the values inside a structure without changing the structure itself, and that preserves identity and composition. Lists, options, results, trees and functions out of a fixed type are functors. The notion comes from category theory, where a functor is a structure-preserving map between categories. In OCaml the word also names something different: a module parametrised by another module, such as Map.Make.

List.map, Option.map and Result.map have the same type up to the name of the container: they take a function on elements and return a function on containers. A functor is anything with such an operation that behaves like these do: it reaches every element, applies the function, and leaves everything else about the structure alone.

(* One shape of map, for many type constructors. *)
let map_option f = function Some x -> Some (f x) | None -> None
let map_result f = function Ok x -> Ok (f x) | Error e -> Error e
let map_pair f (a, b) = (a, f b)                (* the second component *)
let map_fun f g = fun r -> f (g r)              (* functions out of a fixed type *)
 
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)
 
(* Identity and constant functors: map applies f, or ignores it. *)
type 'a identity = Identity of 'a
let map_identity f (Identity x) = Identity (f x)
type ('c, 'a) const = Const of 'c
let map_const _f (Const c) = Const c

map_option succ (Some 1)      ->  Some 2
map_result succ (Error "e")   ->  Error e
map_pair succ ("k", 1)        ->  ("k", 2)
map_fun succ String.length "abc"  ->  4
map_tree (( * ) 10) t          ->  [10; 20; 30]
map_const succ (Const "unchanged")  ->  Const "unchanged"

For option and result mapping touches the value only when there is one. For a pair it touches one component, which is a choice: a type with two parameters is a functor in each separately. For a function $r\to a$, mapping is composition, applied after the function. The constant functor has no values of the parameter type at all, so its map changes nothing.

A functor is a type constructor $F$ with

satisfying two laws:

The identity law says that mapping the identity changes nothing, so fmap cannot reorder, drop or duplicate elements or change anything else about the shape. The composition law says that mapping twice is the same as mapping once with the composite, so a chain of maps can be fused into one traversal. Neither is checked by a compiler, and plausible-looking definitions break them:

(* A lawful map, and two plausible-looking ones that are not. *)
let good f xs = List.map f xs
let reverses f xs = List.rev (List.map f xs)          (* breaks identity *)
let counts = ref 0
let stateful f xs = incr counts; if !counts mod 2 = 0 then List.map f xs else []  (* breaks both *)
 
let identity_law map xs = map Fun.id xs = xs
let composition_law map f g xs = map (fun x -> g (f x)) xs = map g (map f xs)

good       identity holds   composition holds
reverses   identity fails   composition fails
stateful   identity fails   composition fails

Reversing the list breaks both laws even though it applies $f$ to every element exactly once. A map with hidden state breaks them because two calls with equal arguments give different results.

Uniqueness

For a given type there is at most one fmap that satisfies the identity law. This follows from parametricity: a function polymorphic in the element type can only move elements around, not inspect them^[4], and the identity law then forbids moving them. In Haskell the compiler can derive the instance for that reason (deriving Functor), since there is only one candidate.

list            apply f to every element, in order
option          apply f to the value if there is one
result          apply f to the Ok value; leave Error as it is
pair (e, a)     apply f to the second component
tree            apply f at every node
r -> a          compose: fmap f g = f . g
Lazy.t          apply f when the value is forced
identity        apply f
constant c      ignore f
parser          apply f to what the parser returns
promise         apply f to the value when it arrives

A type constructor is a functor in a parameter when that parameter appears only in covariant positions: as a component, inside another functor, or to the right of a function arrow.

When the parameter appears to the left of an arrow, mapping goes the other way. A predicate $a\to bool$ cannot be turned into a predicate on $b$ by a function $a\to b$, but it can by a function $b\to a$: first convert, then test. Such a type is a contravariant functor:

(* A predicate on 'a cannot be mapped forwards, but it can be pulled back
   along any function into 'a: a contravariant functor. *)
type 'a predicate = 'a -> bool
let contramap (f : 'b -> 'a) (p : 'a predicate) : 'b predicate = fun b -> p (f b)
 
(* Comparisons are contravariant too: compare people by comparing their ages. *)
type 'a order = 'a -> 'a -> int
let contramap_order (f : 'b -> 'a) (cmp : 'a order) : 'b order = fun x y -> cmp (f x) (f y)
 
type person = { name : string; age : int }
let by_age = contramap_order (fun p -> p.age) Int.compare
let adult = contramap (fun p -> p.age) (fun a -> a >= 18)
 
(* Result is a bifunctor: it can be mapped on either side. *)
let bimap f g = function Ok x -> Ok (f x) | Error e -> Error (g e)

List.sort by_age   ->  Quill, Ada, Brom
List.filter adult  ->  Ada, Brom
bimap succ String.uppercase_ascii (Error "no")  ->  Error NO

A type with the parameter on both sides of an arrow, such as $a\to a$, is neither, and is called invariant. A type with two parameters that is a functor in each, such as a pair or result, is a bifunctor. A type contravariant in one parameter and covariant in the other, like the function type $a\to b$ itself, is a profunctor; lenses and prisms can be defined in terms of profunctors^[7].

Functors compose: if $F$ and $G$ are functors then so is $F\circ G$, with ${fmap}_{F\circ G}f={fmap}_F({fmap}_{G}f)$. A list of options maps with List.map (Option.map f).

A natural transformation between two functors is a function $t:\forall a.Fa\to Ga$ that commutes with mapping:

It rearranges or selects the structure without looking at the elements, so it does not matter whether the elements are transformed before or after. Parametricity makes every polymorphic function of that type natural^[4]: List.rev, taking the head of a list, and turning an option into a list all are.

(* Composite functors: a list of options maps with both maps at once. *)
let map_list_option f = List.map (Option.map f)
 
(* Natural transformations: polymorphic functions between functors. For
   any f, map f after t equals t after map f. *)
let head = function x :: _ -> Some x | [] -> None
let to_list = function Some x -> [ x ] | None -> []
 
let natural t map_src map_dst f x = map_dst f (t x) = t (map_src f x)

map_list_option succ [Some 1; None; Some 3]  ->  [Some 2; None; Some 4]
head is natural     ->  true
List.rev is natural ->  true
to_list is natural  ->  true

A category has objects and arrows between them, with identities and an associative composition. A functor $F:\mathcal{C}\to \mathcal{D}$ sends each object $A$ to an object $FA$ and each arrow $f:A\to B$ to an arrow $Ff:FA\to FB$, such that

Types and functions form a category, and a programming functor is an endofunctor on it: the type constructor is the action on objects, and fmap is the action on arrows. Natural transformations are the arrows between functors, so functors from $\mathcal{C}$ to $\mathcal{D}$ themselves form a category^[2]. Eilenberg and Mac Lane introduced both notions in 1945, in order to say precisely what "natural" means in phrases like "the natural isomorphism between a vector space and its double dual"^[1].

Two constructions come up often in programming. For a fixed object $A$, the hom-functor $\mathrm{Hom}(A,-)$ sends $B$ to the set of arrows $A\to B$, which is the function functor above; the Yoneda lemma characterises the natural transformations out of it. And a functor with extra structure is the starting point for the richer abstractions: an applicative functor adds a way to combine independent structures, and a monad a way to sequence dependent ones.

In OCaml a functor is also a module parametrised by another module: a function from structures to structures, checked against signatures. Map.Make and Set.Make take a module with an ordered type and return a module of maps or sets over it^[8].

(* OCaml's other functors: functions from modules to modules. *)
module type ORDERED = sig
  type t
  val compare : t -> t -> int
end
 
module Max (O : ORDERED) = struct
  let of_list = function
    | [] -> None
    | x :: xs -> Some (List.fold_left (fun m y -> if O.compare y m > 0 then y else m) x xs)
end
 
module By_length = struct
  type t = string
  let compare a b = Int.compare (String.length a) (String.length b)
end
 
module Longest = Max (By_length)
module Words = Set.Make (String)

Longest.of_list ["ox"; "heron"; "cat"]  ->  heron
Words.elements (of_list ["b"; "a"; "b"])  ->  [a; b]

The two meanings share only the name, which both take from category theory: a module functor maps modules to modules, and fmap maps functions to functions. Module functors came from Standard ML^[5]. OCaml's are applicative by default, meaning two applications to the same argument produce compatible types; Leroy designed that semantics^[6]. A functor whose parameter list is () is generative instead, and gives new types at every application.

Haskell has a Functor type class with fmap and the operator <$>; being able to abstract over a type constructor rather than a type is what made the class expressible, and Jones's constructor classes introduced that^[3]. Scala's libraries provide the same class, and map on collections, options and futures throughout mainstream languages is the same operation without the name.

The word means something else in several languages. In C++ a functor is a function object, an object with an overloaded operator(). In Prolog it is the name and arity of a compound term, such as point/2.

• ApplicativeAn applicative functor is a functor with pure : a -> f a and an operation that combines independent computations, <*> : f (a -> b) -> f a -> f b, or equivalently a product f a -> f b -> f (a * b), satisfying four laws. It sits between functors and monads: every monad is applicative, but because later steps cannot depend on earlier results, an applicative computation can collect all errors, run its parts in parallel, or be inspected before it runs.
• 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 higher-kinded type is a type constructor, such as Maybe or List, that takes types as arguments, and higher-kinded polymorphism is the ability to abstract over such constructors with type variables, so that Functor f can be instantiated at Maybe or at lists without naming their element types. Kinds classify types the way types classify values: Int has kind Type, Maybe has kind Type → Type. Higher-kinded variables are what make a single Functor or Monad class usable across every container. Haskell and Scala support them directly; OCaml expresses the same abstraction with module functors or an encoding, and Java and Go cannot express it.
• 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.
• LensA lens is a first-class pair of a getter and a setter for one part of a structure, with laws that make them agree: you get back what you set, setting what you got changes nothing, and a second set overwrites the first. Lenses compose, so a path through nested immutable records is one value that can read or update the part at its end. They originated in work on the view-update problem, and in Haskell are usually encoded as functions polymorphic in a functor, which makes composition ordinary function composition.
• FoldableFoldable is the abstraction of a container whose elements can be combined in order: a list, a tree, an option. A fold replaces the constructors of the structure with a function and a starting value, and every summary of the elements, their sum, length, maximum, list of elements or whether any satisfies a predicate, is derived from it. Equivalently, a foldable container maps each element into a monoid and combines the results (foldMap). The universal property of fold characterizes exactly which functions are folds.
• TraversableTraversable is the abstraction of a container that can be rebuilt while an applicative effect is performed on each element in order: traverse : (a -> f b) -> t a -> f (t b). Validating every element, parsing each string, numbering the nodes of a tree and taking cartesian products are all traversals with different applicative functors. traverse subsumes both map (with the identity functor) and foldMap (with a constant functor into a monoid), and it satisfies laws saying it visits every element exactly once.
• AnamorphismAn anamorphism is the generalization of unfold: it builds a value of a recursive data type from a seed, using a function (a coalgebra) that produces one layer of the structure together with new seeds for its recursive positions. It is the categorical dual of the catamorphism, the unique homomorphism from any coalgebra into the final coalgebra of a functor. Anamorphisms can produce infinite structures such as streams, and they are the way to write corecursive programs that are guaranteed to be productive.
• CatamorphismA catamorphism is the generalization of fold from lists to any recursive data type: it replaces each constructor of a value with a function and combines the results bottom up. Formally it is the unique homomorphism from the initial algebra of a functor to any other algebra of that functor. Writing a recursive data type as the fixed point of a base functor lets a single cata function fold every such type, with the recursion written once and each computation reduced to an algebra that handles one layer.
• Dictionary passingDictionary passing is the standard way to implement type classes. Each class becomes a record type whose fields are its methods, each instance becomes a value of that record type, and each function with a class constraint receives the record, the dictionary, as an extra argument, which the compiler supplies at every call site after resolving which instance applies. An instance that itself has a context, such as equality on lists given equality on elements, becomes a function from dictionaries to a dictionary, and a superclass becomes a field. The same technique written by hand is the usual way to get type-class-like overloading in OCaml, with records, first-class modules or functors.
• Free monadThe free monad on a functor F is the monad whose values are trees of F-shaped instructions with results at the leaves: Pure a | Free (F (Free F a)). It adds exactly the monad structure and nothing else, so a program written in it is a description of a sequence of instructions that different interpreters can run, inspect or transform. Any mapping from F into a monad M extends uniquely to an interpreter from the free monad into M. Left-nested binds take quadratic time, which the Church-encoded form avoids.
• Kleisli compositionKleisli composition composes two functions that return monadic results, f : a → m b and g : b → m c, into a function a → m c, by applying f and binding its result to g. It is written >=> in Haskell. Functions of this shape are the arrows of the Kleisli category of the monad, with return as the identity, and the monad laws are exactly the statement that this composition is associative and has return as a unit on both sides.
• Van Laarhoven lensA van Laarhoven lens is a lens represented as a single function polymorphic over functors: forall f. Functor f => (a -> f a) -> s -> f s. Instantiating the functor gives the operations: the constant functor yields the getter and the identity functor the setter. Lenses in this form compose with ordinary function composition, and replacing Functor with Applicative gives traversals, which compose with lenses the same way. The representation is the basis of Haskell's lens library.

1. [1]S. Eilenberg, S. Mac Lane, “General theory of natural equivalences”, Transactions of the AMS 58 (1945).
2. [2]S. Mac Lane, Categories for the Working Mathematician, Springer (2nd ed., 1998).
3. [3]M. P. Jones, “A system of constructor classes: overloading and implicit higher-order polymorphism”, FPCA (1993).
4. [4]P. Wadler, “Theorems for free!”, FPCA (1989).
5. [5]D. MacQueen, “Modules for Standard ML”, LISP and Functional Programming (1984).
6. [6]X. Leroy, “Applicative functors and fully transparent higher-order modules”, POPL (1995).
7. [7]M. Pickering, J. Gibbons, N. Wu, “Profunctor optics: modular data accessors”, The Art, Science, and Engineering of Programming 1 (2017).
8. [8]The OCaml manual, “Functors”, in the chapter on the module system.

last updated 27 September 2026