In Functional Programming, what is a functor?

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.

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.

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.

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.

The best answer to that question is found in "Typeclassopedia" by Brent Yorgey.

This issue of Monad Reader contain a precise definition of what a functor is as well as many definition of other concepts as well as a diagram. (Monoid, Applicative, Monad and other concept are explained and seen in relation to a functor).

http://haskell.org/sitewiki/images/8/85/TMR-Issue13.pdf

excerpt from Typeclassopedia for Functor: "A simple intuition is that a Functor represents a “container” of some sort, along with the ability to apply a function uniformly to every element in the container"

But really the whole typeclassopedia is a highly recommended reading that is surprisingly easy. In a way you can see the typeclass presented there as a parallel to design pattern in object in the sense that they give you a vocabulary for given behavior or capability.

Cheers

There is a pretty good example in the O'Reilly OCaml book that's on Inria's website (which as of writing this is unfortunately down). I found a very similar example in this book used by caltech: Introduction to OCaml (pdf link). The relevant section is the chapter on functors (Page 139 in the book, page 149 in the PDF).

In the book they have a functor called MakeSet which creates a data structure that consists of a list, and functions to add an element, determine if an element is in the list, and to find the element. The comparison function that is used to determine if it's in/not in the set has been parametrized (which is what makes MakeSet a functor instead of a module).

They also have a module that implements the comparison function so that it does a case insensitive string compare.

Using the functor and the module that implements the comparison they can create a new module in one line:

module SSet = MakeSet(StringCaseEqual);;

that creates a module for a set data structure that uses case insensitive comparisons. If you wanted to create a set that used case sensitive comparisons then you would just need to implement a new comparison module instead of a new data structure module.

Tobu compared functors to templates in C++ which I think is quite apt.

Given the other answers and what I'm going to post now, I'd say that it's a rather heavily overloaded word, but anyway...

For a hint regarding the meaning of the word 'functor' in Haskell, ask GHCi:

Prelude> :info Functor
class Functor f where
  fmap :: forall a b. (a -> b) -> f a -> f b
  (GHC.Base.<$) :: forall a b. a -> f b -> f a
        -- Defined in GHC.Base
instance Functor Maybe -- Defined in Data.Maybe
instance Functor [] -- Defined in GHC.Base
instance Functor IO -- Defined in GHC.Base

So, basically, a functor in Haskell is something that can be mapped over. Another way to say it is that a functor is something which can be regarded as a container which can be asked to use a given function to transform the value it contains; thus, for lists, fmap coincides with map, for Maybe, fmap f (Just x) = Just (f x), fmap f Nothing = Nothing etc.

The Functor typeclass subsection and the section on Functors, Applicative Functors and Monoids of Learn You a Haskell for Great Good give some examples of where this particular concept is useful. (A summary: lots of places! :-))

Note that any monad can be treated as a functor, and in fact, as Craig Stuntz points out, the most often used functors tend to be monads... OTOH, it is convenient at times to make a type an instance of the Functor typeclass without going to the trouble of making it a Monad. (E.g. in the case of ZipList from Control.Applicative, mentioned on one of the aforementioned pages.)

Here's an article on functors from a programming POV, followed up by more specifically how they surface in programming languages.

The practical use of a functor is in a monad, and you can find many tutorials on monads if you look for that.

In functional programming, error handling is different. Throwing and catching exceptions is imperative code. Instead of using try/catch block, a safety box is created around the code that might throw an error. this is a fundamental design pattern in functional programming. A wrapper object is used to encapsulate a potentially erroneous value. The wrapper's main purpose is to provide a 'different' way to use the wrapped object

 const wrap = (val) => new Wrapper(val);

Wrapping guards direct access to the values so they can be manipulated safely and immutably. Because we won’t have direct access to it, the only way to extract it is to use the identity function.

identity :: (a) -> a

This is another use case of identity function: Extracting data functionally from encapsulated types.

The Wrapper type uses the map to safely access and manipulate values. In this case, we are mapping the identity function over the container to extract the value from the container. With this approach, we can check for null before calling the function, or check for an empty string, a negative number, and so on.

 fmap :: (A -> B) -> Wrapper[A] -> Wrapper[B]

fmap, first opens the container, then applies the given function to its value, and finally closes the value back into a new container of the same type. This type of function is called a functor.

• fmap returns a new copy of the container at each invocation.

• functors are side-effect-free

• functors must be composable

Put simply, a functor, or function object, is a class object that can be called just like a function.

In C++:

This is how you write a function

void foo()
{
    cout << "Hello, world! I'm a function!";
}

This is how you write a functor

class FunctorClass
{
    public:
    void operator ()
    {
        cout << "Hello, world! I'm a functor!";
    }
};

Now you can do this:

foo(); //result: Hello, World! I'm a function!

FunctorClass bar;
bar(); //result: Hello, World! I'm a functor!

What makes these so great is that you can keep state in the class - imagine if you wanted to ask a function how many times it has been called. There's no way to do this in a neat, encapsulated way. With a function object, it's just like any other class: you'd have some instance variable that you increment in operator () and some method to inspect that variable, and everything's neat as you please.

Functor is not specifically related to functional programming. It's just a "pointer" to a function or some kind of object, that can be called as it would be a function.