It's interesting how the term **functor** means completely different things in various programming languages. Take **C++** for example. Everyone who has learned at least a little bit of advanced C++ knows that you call a class that implements `operator()`

a functor. Now take **Standard ML**. In ML functors are mappings from structures to structures. Now **Haskell**. In Haskell functors are just homomorphisms over containers. And in **Prolog** functor means the atom at the start of a structure. They all are different. Let's take a closer look at each one.

## Functors in C++

Functors in C++ are short for "**function objects**." Function objects are instances of C++ classes that have the `operator()`

defined. If you define `operator()`

on C++ classes you get objects that act like functions but can also store state. Here is an example,

```
#include <iostream>
#include <string>
class SimpleFunctor {
std::string name_;
public:
SimpleFunctor(const char *name) : name_(name) {}
void operator()() { std::cout << "Oh, hello, " << name_ << endl; }
};
int main() {
SimpleFunctor sf("catonmat");
sf(); // prints "Oh, hello, catonmat"
}
```

Notice how I was able to call `sf()`

in the `main`

function, even though `sf`

was an object? That's because I defined `operator()`

in `SimpleFunctor`

's class.

Most often functors in C++ are used as predicates, fake closures or comparison functions in STL algorithms. Here is another example. Suppose you have a list of integers and you want to find the sum of all even ones, and the sum of all odd ones. Perfect job for a functor and `for_each`

algorithm.

```
#include <algorithm>
#include <iostream>
#include <list>
class EvenOddFunctor {
int even_;
int odd_;
public:
EvenOddFunctor() : even_(0), odd_(0) {}
void operator()(int x) {
if (x%2 == 0) even_ += x;
else odd_ += x;
}
int even_sum() const { return even_; }
int odd_sum() const { return odd_; }
};
int main() {
EvenOddFunctor evenodd;
int my_list[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
evenodd = std::for_each(my_list,
my_list+sizeof(my_list)/sizeof(my_list[0]),
evenodd);
std::cout << "Sum of evens: " << evenodd.even_sum() << "\n";
std::cout << "Sum of odds: " << evenodd.odd_sum() << std::endl;
// output:
// Sum of evens: 30
// Sum of odds: 25
}
```

Here an instance of an `EvenOddFunctor`

gets passed to `for_each`

algorithm. The `for_each`

algorithm iterates over each element in `my_list`

and calls the functor. After it's done, it returns a copy of `evenodd`

functor that contains the sum of evens and odds.

## Functors in Standard ML

Vaguely talking in object-oriented terms, functors in ML are generic implementations of interfaces. In ML terms, functors are part of ML module system and they allow to compose structures.

Here is an example, suppose you want to write a plugin system and you want all the plugins to implement the required interface, which, for simplicity, includes only the `perform`

function. In ML you can first define a signature for plugins,

```
signature Plugin =
sig
val perform : unit -> unit
end;
```

Now that we have defined an interface (signature) for plugins, we can implement two Plugins, let's say `LoudPlugin`

and `SilentPlugin`

. The implementation is done via structures,

```
structure LoudPlugin :> Plugin =
struct
fun perform () = print "DOING JOB LOUDLY!\n"
end;
```

And the SilentPlugin,

```
structure SilentPlugin :> Plugin =
struct
fun perform () = print "doing job silently\n"
end;
```

Now we get to functors. Remember functors in ML take structures as their arguments, so we can write one that takes `Plugin`

as its argument,

```
functor Performer(P : Plugin) =
struct
fun job () = P.perform ()
end;
```

This functor takes `Plugin`

as `P`

argument, and uses it in the `job`

function, that calls `P`

plugin's `perform`

function.

Now let's use the `Performer`

functor. Remember that a functor returns a structure,

```
structure LoudPerformer = Performer(LoudPlugin);
structure SilentPerformer = Performer(SilentPlugin);
LoudPerformer.job ();
SilentPerformer.job ();
```

This outputs,

DOING JOB LOUDLY! doing job silently

This is probably the simplest possible example of Standard ML functors.

## Functors in Haskell

Functors in Haskell is what real functors are supposed to be. Haskell functors resemble mathematical functors from category theory. In category theory a functor F is a mapping between two categories such that the structure of the category being mapped over is preserved, in other words, it's a homomorphism between two categories.

In Haskell this definition is implemented as a simple type class,

```
class Functor f where
fmap :: (a -> b) -> f a -> f b
```

Looking back at ML example, a type class in Haskell is like a signature, except it's defined on types. It defines what operations a type has to implement to be an instance of this class. In this case, however, the `Functor`

is not defined over types but over type constructors `f`

. It says, a `Functor`

is something that implements the `fmap`

function that takes a function from type `a`

to type `b`

, and a value of type `f a`

(a type constructed from type constructor `f`

applied to type `a`

) and returns a value of type `f b`

.

To understand what it does, think of `fmap`

as a function that applies an operation to each element in some kind of a container.

The simplest example of functors is regular lists and the `map`

function that maps a function to each element in the list.

Prelude> map (+1) [1,2,3,4,5] [2,3,4,5,6]

In this simple example, the `Functor`

's `fmap`

function is just `map`

and type constructor `f`

is `[]`

- the list type constructor. Therefore the `Functor`

instance for lists is defined as

```
instance Functor [] where
fmap = map
```

Let's see if it really is true by using `fmap`

instead of `map`

in the previous example,

Prelude> fmap (+1) [1,2,3,4,5] [2,3,4,5,6]

But notice that Functor definition does not say anything about preserving the structure! Therefore any sensible functor must satisfy the functor laws, which are part of the definition of the mathematical functor, implicitly. There are two rules on `fmap`

:

fmap id = id fmap (g . h) = fmap g . fmap h

The first rule says that mapping the identity function over every element in a container has no effect. The second rule says that a composition of two functions over every item in a container is the same as first mapping one function, and then mapping the other.

Another example of Functors that illustrate them the most vividly is operations over trees. Think of a tree as a container, then `fmap`

maps a function over tree values, while preserving the tree's structure.

Let's define a Tree first,

```
data Tree a = Node (Tree a) (Tree a)
| Leaf a
deriving Show
```

This definition says that a `Tree`

of type `a`

is either a `Node`

of two `Tree`

s (left and right branches) or a `Leaf`

. The `deriving Show`

expression allows us to inspect the Tree via `show`

function.

Now we can define a `Functor`

over `Tree`

s,

```
instance Functor Tree where
fmap g (Leaf v) = Leaf (g v)
fmap g (Node l r) = Node (fmap g l) (fmap g r)
```

This definition says, that `fmap`

of function `g`

over a `Leaf`

with value `v`

is just a `Leaf`

of `g`

applied to `v`

. And `fmap`

of `g`

over a `Node`

with left `l`

and right `r`

branches is just a `Node`

of `fmap`

applied to the values of left and right branches.

Now let's illustrate how fmap works on trees. Let's construct a tree with String leaves and map the length function over them to find out the length of each leaf.

Prelude> let tree = (Node (Node (Leaf "hello") (Leaf "foo")) (Leaf "baar")) Prelude> fmap length tree Node (Node (Leaf 5) (Leaf 3)) (Leaf 4)

Here I constructed the following tree,

* / \ / \ * "baar" / \ / \ / \ / \ "hello" "foo"

And mapped `length`

function over it, producing,

* / \ / \ * 4 / \ / \ / \ / \ 5 3

Another way of saying what `fmap`

does is that is `lifts`

a function from the "normal world" into the "`f`

world."

In fact Functor is the most fundamental type class in Haskell because Monads, Applicatives and Arrows are all Functors. As I like to say it, Haskell starts where the functors start.

If you want to learn more about Haskell type classes, start with the excellent article Typeclassopedia (starts at page 17).

## Functors in Prolog

Finally, functors in Prolog. Functors in Prolog are the simplest of all. They refer to two things. The first is the atom at the start of the structure. Here is an example, given an expression,

```
?- likes(mary, pizza)
```

the functor is the first atom - `likes`

.

The second is built-in predicate called `functor`

. It returns the arity and the functor of a structure. For example,

```
?- functor(likes(mary, pizza), Functor, Arity).
Functor = likes
Arity = 2
```

That's it for functors in Prolog.

## Conclusion

This article demonstrated how a simple term like functor can refer to completely different things in various programming languages. Therefore when you hear a the term functor, it's important to know the context it's being mentioned in.