In Functional Programming, what is a functor?

Question

I've come across the term 'Functor' a few times while reading various articles on functional programming, but the authors typically assume the reader already understands the term. Looking around on the web has provided either excessively technical descriptions (see the Wikipedia article) or incredibly vague descriptions (see the section on Functors at this ocaml-tutorial website).

Can someone kindly define the term, explain its use, and perhaps provide an example of how Functors are created and used?

Edit: While I am interested in the theory behind the term, I am less interested in the theory than I am in the implementation and practical use of the concept.

Edit 2: Looks like there is some cross-terminoligy going on: I'm specifically referring to the Functors of functional programming, not the function objects of C++.

Solution 1

The word "functor" comes from category theory, which is a very general, very abstract branch of mathematics. It has been borrowed by designers of functional languages in at least two different ways.

• In the ML family of languages, a functor is a module that takes one or more other modules as a parameter. It's considered an advanced feature, and most beginning programmers have difficulty with it.

  As an example of implementation and practical use, you could define your favorite form of balanced binary search tree once and for all as a functor, and it would take as a parameter a module that provides:

  • The type of key to be used in the binary tree

  • A total-ordering function on keys

  Once you've done this, you can use the same balanced binary tree implementation forever. (The type of value stored in the tree is usually left polymorphic—the tree doesn't need to look at values other than to copy them around, whereas the tree definitely needs to be able to compare keys, and it gets the comparison function from the functor's parameter.)

  Another application of ML functors is layered network protocols. The link is to a really terrific paper by the CMU Fox group; it shows how to use functors to build more complex protocol layers (like TCP) on type of simpler layers (like IP or even directly over Ethernet). Each layer is implemented as a functor that takes as a parameter the layer below it. The structure of the software actually reflects the way people think about the problem, as opposed to the layers existing only in the mind of the programmer. In 1994 when this work was published, it was a big deal.

  For a wild example of ML functors in action, you could see the paper ML Module Mania, which contains a publishable (i.e., scary) example of functors at work. For a brilliant, clear, pellucid explanation of the ML modules system (with comparisons to other kinds of modules), read the first few pages of Xavier Leroy's brilliant 1994 POPL paper Manifest Types, Modules, and Separate Compilation.

• In Haskell, and in some related pure functional language, Functor is a type class. A type belongs to a type class (or more technically, the type "is an instance of" the type class) when the type provides certain operations with certain expected behavior. A type T can belong to class Functor if it has certain collection-like behavior:

  • The type T is parameterized over another type, which you should think of as the element type of the collection. The type of the full collection is then something like T Int, T String, T Bool, if you are containing integers, strings, or Booleans respectively. If the element type is unknown, it is written as a type parameter a, as in T a.

    Examples include lists (zero or more elements of type a), the Maybe type (zero or one elements of type a), sets of elements of type a, arrays of elements of type a, all kinds of search trees containing values of type a, and lots of others you can think of.

  • The other property that T has to satisfy is that if you have a function of type a -> b (a function on elements), then you have to be able to take that function and product a related function on collections. You do this with the operator fmap, which is shared by every type in the Functor type class. The operator is actually overloaded, so if you have a function even with type Int -> Bool, then

    fmap even
    

    is an overloaded function that can do many wonderful things:

    • Convert a list of integers to a list of Booleans

    • Convert a tree of integers to a tree of Booleans

    • Convert Nothing to Nothing and Just 7 to Just False

    In Haskell, this property is expressed by giving the type of fmap:

    fmap :: (Functor t) => (a -> b) -> t a -> t b
    

    where we now have a small t, which means "any type in the Functor class."

  To make a long story short, in Haskell a functor is a kind of collection for which if you are given a function on elements, fmap will give you back a function on collections. As you can imagine, this is an idea that can be widely reused, which is why it is blessed as part of Haskell's standard library.

As usual, people continue to invent new, useful abstractions, and you may want to look into applicative functors, for which the best reference may be a paper called Applicative Programming with Effects by Conor McBride and Ross Paterson.

Solution 2

Other answers here are complete, but I'll try another explanation of the FP use of functor. Take this as analogy:

A functor is a container of type a that, when subjected to a function that maps from a→b, yields a container of type b.

Unlike the abstracted-function-pointer use in C++, here the functor is not the function; rather, it's something that behaves consistently when subjected to a function.

Solution 3

There are three different meanings, not much related!

• In Ocaml it is a parametrized module. See manual. I think the best way to grok them is by example: (written quickly, might be buggy)

  module type Order = sig
      type t
      val compare: t -> t -> bool
  end;;
  
  
  module Integers = struct
      type t = int
      let compare x y = x > y
  end;;
  
  module ReverseOrder = functor (X: Order) -> struct
      type t = X.t
      let compare x y = X.compare y x
  end;;
  
  (* We can order reversely *)
  module K = ReverseOrder (Integers);;
  Integers.compare 3 4;;   (* this is false *)
  K.compare 3 4;;          (* this is true *)
  
  module LexicographicOrder = functor (X: Order) -> 
    functor (Y: Order) -> struct
      type t = X.t * Y.t
      let compare (a,b) (c,d) = if X.compare a c then true
                           else if X.compare c a then false
                           else Y.compare b d
  end;;
  
  (* compare lexicographically *)
  module X = LexicographicOrder (Integers) (Integers);;
  X.compare (2,3) (4,5);;
  
  module LinearSearch = functor (X: Order) -> struct
      type t = X.t array
      let find x k = 0 (* some boring code *)
  end;;
  
  module BinarySearch = functor (X: Order) -> struct
      type t = X.t array
      let find x k = 0 (* some boring code *)
  end;;
  
  (* linear search over arrays of integers *)
  module LS = LinearSearch (Integers);;
  LS.find [|1;2;3] 2;;
  (* binary search over arrays of pairs of integers, 
     sorted lexicographically *)
  module BS = BinarySearch (LexicographicOrder (Integers) (Integers));;
  BS.find [|(2,3);(4,5)|] (2,3);;
  

You can now add quickly many possible orders, ways to form new orders, do a binary or linear search easily over them. Generic programming FTW.

• In functional programming languages like Haskell, it means some type constructors (parametrized types like lists, sets) that can be "mapped". To be precise, a functor f is equipped with (a -> b) -> (f a -> f b). This has origins in category theory. The Wikipedia article you linked to is this usage.

  class Functor f where
      fmap :: (a -> b) -> (f a -> f b)
  
  instance Functor [] where      -- lists are a functor
      fmap = map
  
  instance Functor Maybe where   -- Maybe is option in Haskell
      fmap f (Just x) = Just (f x)
      fmap f Nothing = Nothing
  
  fmap (+1) [2,3,4]   -- this is [3,4,5]
  fmap (+1) (Just 5)  -- this is Just 6
  fmap (+1) Nothing   -- this is Nothing
  

So, this is a special kind of a type constructors, and has little to do with functors in Ocaml!

• In imperative languages, it is a pointer to function.

Solution 4

You got quite a few good answers. I'll pitch in:

A functor, in the mathematical sense, is a special kind of function on an algebra. It is a minimal function which maps an algebra to another algebra. "Minimality" is expressed by the functor laws.

There are two ways to look at this. For example, lists are functors over some type. That is, given an algebra over a type 'a', you can generate a compatible algebra of lists containing things of type 'a'. (For example: the map that takes an element to a singleton list containing it: f(a) = [a]) Again, the notion of compatibility is expressed by the functor laws.

On the other hand, given a functor f "over" a type a, (that is, f a is the result of applying the functor f to the algebra of type a), and function from g: a -> b, we can compute a new functor F = (fmap g) which maps f a to f b. In short, fmap is the part of F that maps "functor parts" to "functor parts", and g is the part of the function that maps "algebra parts" to "algebra parts". It takes a function, a functor, and once complete, it IS a functor too.

It might seem that different languages are using different notions of functors, but they're not. They're merely using functors over different algebras. OCamls has an algebra of modules, and functors over that algebra let you attach new declarations to a module in a "compatible" way.

A Haskell functor is NOT a type class. It is a data type with a free variable which satisfies the type class. If you're willing to dig into the guts of a datatype (with no free variables), you can reinterpret a data type as a functor over an underlying algebra. For example:

data F = F Int

is isomorphic to the class of Ints. So F, as a value constructor, is a function that maps Int to F Int, an equivalent algebra. It is a functor. On the other hand, you don't get fmap for free here. That's what pattern matching is for.

Functors are good for "attaching" things to elements of algebras, in an algebraically compatible way.

Solution 5

In OCaml, it's a parameterised module.

If you know C++, think of an OCaml functor as a template. C++ only has class templates, and functors work at the module scale.

An example of functor is Map.Make; module StringMap = Map.Make (String);; builds a map module that works with String-keyed maps.

You couldn't achieve something like StringMap with just polymorphism; you need to make some assumptions on the keys. The String module contains the operations (comparison, etc) on a totally ordered string type, and the functor will link against the operations the String module contains. You could do something similar with object-oriented programming, but you'd have method indirection overhead.

View more solutions

Comments

[Vlad the Impala]

See also: adit.io/posts/…

[toraritte]

Pretty good answer too: stackoverflow.com/a/45149475/1498178

[Richard Gomes]

If you are more interested in the practical implementation and usage than on the stratospheric terminology and theory behind the concept, you just need a one liner: a functor exposes a "map" function.

[Ludovic Kuty]

@RichardGomes IMHO I think it reduces the role of a functor to a simple Java-like interface, which it is not. A functor transforms stuff, it builds new types from existing ones (in Haskell) which means that the types are mapped too. fmap maps the functions. There is two kind of mappings involved. That way of seeing things will help to understand category theory (which is more general). I mean it's interesting to understand basic category theory to help us with all the category theory stuff in Haskell (functor, monads, ...).

[Ludovic Kuty]

@VladtheImpala The blog post is fantastic but, even if it helps a lot, I like to keep in mind that a functor builds (maps to) another type. I particularly like the sentence "A functor F takes each type T and maps it to a new type FT" in Monads are like burritos. IMHO it is not just a context (a box) around a value even if that proves practical to see things like this (Haskell PoV vs category theory PoV ?)

[Erik Forbes]

I got that from the ocaml website - but I don't understand what the use of a parameterized module would be.

[Kevin Gauthier]

There is a specific FP concept of a functor (from category theory), but you're right that the same word is also used for other things in non-FP languages.

[Tobu]

@Kornel Yeah, what I described is an OCaml concept. The other concept is just “functional value”, which is nothing particular in FP. @Erik I expanded slightly, but the reference docs are slow to load.

[Tobu]

No, those functors aren't the type theory notion that is used by FP languages.

[Jörg W Mittag]

I can kind of see how one could prove that FunctorClass fulfils the first Functor Law, but could you sketch out a proof for the second Law? I don't quite see it.

[Jörg W Mittag]

Are you sure that function pointers are Functors? I don't see how function pointers fulfil the two Functor Laws, especially the Second Functor Law (preservation of morphism composition). Do you have a proof for that? (Just a rough sketch.)

[Wei Hu]

I understand both ML-functors and Haskell-functors, but lack the insight to relate them together. What's the relationship between these two, in a category-theoretical sense?

[Norman Ramsey]

@Wei Hu: Category theory has never made any sense to me. The best I can say is that all three notions involve mapping.

[paul]

According to this Haskell wiki: en.wikibooks.org/wiki/Haskell/Category_theory , it's like this: A category is a collection of objects and morphisms (functions), where the morphisms are from objects in a category to other objects in that category. A functor is a function which maps objects and morphisms from one category to objects and morphisms in another. Least that's how I understand it. What that means exactly for programming I have yet to understand.

[imz -- Ivan Zakharyaschev]

Shouldn't <q>map</q> in the last 3 lines of this comment be indeed <q>fmap</q>?

[Dawn Chen]

Bah, you guys are right. I took a stab at solving the "web has provided exceedingly technical descriptions" and overshot, trying to avoid, "In the ML family of languages, a functor is a module that takes one or more other modules as a parameter." This answer, however, is, well, bad. Oversimplified and underspecified. I'm tempted to ragedelete it, but I'll leave it for future generations to shake their heads at :)

[amindfv]

"The practical use of a functor is in a monad" -- not only. All monads are functors, but there are lots of uses for non-monad functors.

[sea-rob]

I'm glad you left the answer and comments, because it helps frame the problem. Thank you! I'm having trouble in that most of the answers are written in terms of Haskell or OCaml, and to me that's a little like explaining alligators in terms of crocodiles.

[Ncat]

@WeiHu Pretty late to the game and I really don't know ML at all, but here's an answer which might elucidate the matter a bit: stackoverflow.com/a/23236777/1455582

[Ram Rajamony]

@norman-ramsey, have you looked at Conceptual Mathematics by Lawvere and Schanuel? I am a total novice to the area but the book is eminently readable and - dare-I-say - enjoyable. (Loved your explanation.)

[Marco Faustinelli]

I'd say that studying monads to use functors is like saving for a Rolls to go buy groceries.

[Wildcard]

Your balanced binary search tree is the only practical example of a functor I have encountered thus far that actually completely makes sense to me. :) I wonder if there is a similarly excellent description of "monads" on this site that someone might link to from here...?

[Qqwy]

With the side note that 'object' should be taken very broadly and just means 'something'. For OOP-languages, for instance, substitute object for class. One could say 'a functor is a class that implements the Functor interface' (Of course, this interface might not be physically there, but you could lift the 'map' logic out to that interface, and have all of your mappable classes share it -- as long as your type system allows typing things this general, that is).

[soundyogi]

I find Classes super confusing to be honest, on one side they are just a blueprint for something concrete / but they may also have methods (static stuff) and can behave like objects. Does the Class implement the interface or the instance it creates?

[Qqwy]

Yes, they can be confusing. But: Classes implement interfaces (they 'fill in' the blanks that were given in the interfaces methods. In other words: They turn the abstract guidelines of the interface in a concrete guideline that can be instantly (forgive the pun) instantiated). As to 'classes behave like objects': In truly OOP-languages like Ruby, Classes are instances of the 'Class' Class. It's turtles all the way down.

[Qqwy]

A container of type b means "the same kind of container as the input container, but now filled with b's". So if we have a list of bananas, and we map a function that takes a banana and outputs a fruit salad, we now have a list of fruit salads. Likewise, if we had a tree of bananas, and we map the same function, we now would have a tree of apples. Etc. tree and list are two Functors here.

[Dmitri Zaitsev]

"A functor is a container of type a that, when subjected to a function" -- it is actually the other way around -- the function (morphism) is subject to a functor, to be mapped into another morphism

[Dmitri Zaitsev]

Actually "function object" is not a correct description of a functor. E.g. Array is a functor, but Array(value) only gives 1-element arrays.

[Dmitri Zaitsev]

Array type construct defines a single functor. Its instances are also called "arrays" but they are not functors. The description here should be made more precise.

[Admin]

I have always read that functors are containers - but this is just a poor simplification. Your answer finally provided the missing link: Functors are a type class (type constraint) for parameterized types (type constructors). It's that simple!

[problemofficer - n.f. Monica]

then you have to be able to take that function and product a related function on collections Did you mean produce instead of product?

[chepner]

Re: category theory, you can think of the collection of types in a langauge as being the objects in a category, with functions being the arrows connecting objects. A functor in category theory maps types to other types, and functions between two types to functions between two mapped types. So in Haskell, for example, [] + fmap is a functor: [] maps types like Int to [Int], while fmap maps functions like Char -> Int to [Char] -> [Int]. The tricky part (for me) was that the mapped types don't really have names independent of the functor that maps to them.

[soundyogi]

@DmitriZaitsev Could you elaborate? So what you are saying is that instances are not functors? I dont see the sence in that since you get a new functor by mapping over one.

[Dmitri Zaitsev]

@soundyogi To have a simpler example, a number is an instance of both addition and multiplication group. So you cannot define the inverse of a number, unless you specify the operation. Similarly, to map an instance over a function, you need to know the complete functor, not just the instance.

[Dmitri Zaitsev]

Also your definition is incorrect because you don't mention the functor laws.

[soundyogi]

Yes it is not the most complete answer, but I found its simplicity intruiging. I will have to read about what you mentioned. I think I see what you mean. Thanks.

[Dmitri Zaitsev]

@soundyogi 'Not the most complete' is not the same as incorrect :). Simplicity is only good when it helps, not obscures.

[Ludovic Kuty]

Interesting answer. I wish to complement it with Monads are like burritos (funny answer to Abstraction, intuition, and the “monad tutorial fallacy”) and his sentence "A functor F takes each type T and maps it to a new type FT" aka a type constructor. Functional Programming and Category Theory - Categories and Functors was useful too.