Follow me on Twitter for my latest adventures!

It's interesting how the term "**functor**" means completely different things in various programming languages. Take **C++** for example. Everyone who has mastered 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 wish 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 wish 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 wish 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.

## Comments

Very nice article! It's sad that other popular languages doesn't implement operator()-like

Keep up good work Pete!

why? I think it's good thing, using () only produces mess in code. When I see bomb.explode() I now I should expect the object bomb to explode. But bomb() doesn't say me anything. Worst thing, the requirements for () changes, old comment stays and i can find something like:

// this operator explodes the bomb

operator()() { /* explode() */ save_the_world(); }

Python does - you just need to implement the __call__ method:

All functions in Javascript are implicitly C++-functors, but defined in a reverse order.

Each run will increment the value and print the new version, but you can also alter that property however and whenever you like, so in Javascript you tend to use real closures for holding state, instead:

or you can define objects to instantiate if you need more than one:

Scala also has "()":

In Pascal you can at least override the []-operator for classes

C++ function explanation was very clear.

You should put down accumulate instead of for_each in your C++ example as for_each is not required to pass the previous functor's state to the next call. That is, you could wind up with even == 0 and odd == 1 instead of 25 and 30.

How would it lose the state? The doc clearly states that for_each(first, last, f) applies

fto the result of dereferencing every iterator in the range [first, last).The standard just requires a copy of

`f`

to be returned. This means that, for instance, the following implementation is perfectly legal:This is a typical gotcha for C++ beginners.

(There are also other small oversights in the code, but this is the main one.)

PS: Also, I think that

standard-wisethe only occurrence of the term "functor" I've seen is in the draft specification forunique_ptr(but I'd have to check if it's still there; if so it ought probably be replaced by "function object"). But of course it's a term in common usage, sometimes referring to classes, sometimes to objects (instances).Oops, I forgot to stick to

input iterators, sorry. It should of course be:Thanks for your explanation. I've recently been programming a lot in Ruby, where you have Procs, Blocks and lambda closures and while working with C++ I really missed the dynamics of these concepts. I think the biggest lack of C++ is that it does not support anonymous function objects. You always have to define a class and override the operator().

C++'s functors are, in my opinion, also not powerful enough for full object oriented use. It is not easy to create a functor for a method call on an object. In Ruby this is solved using Method Objects:

Jan, Python, at least, implements this with the __call__(self,*args) method on objects.

See also http://stackoverflow.com/questions/2030863/in-functional-programming-what-is-a-functor/2031421#2031421

Nice post. I think the concept of functor originated in mathematics and it would be appropriate for this article to make mention of it. Functors in math: http://en.wikipedia.org/wiki/Functor

The Haskell approach pretty much is the mathematical approach. And the nice thing about Haskell is that while it's extremely faithful to the pure math, but it's also a very powerful programming language, easily as powerful as C++.

I'd recommend the classic intro to Haskell to start with, or Real World Haskell if you prefer something more practical. Once you've got a few working programs under your belt, here's a pretty readable intro to category theory.

Just to add a bit: C++ functors would typically inherit from std::unary_function or std::binary_function.

In the example in the article it doesn't matter much, but for other cases it does.

It is explained a bit more here:

Benefits of letting functors inherit from std::unary_function...

In Python any object with a

__call__()method may be called using function-call syntax. So any function are objects, just like strings, numbers, lists, and so on is afunctor.So what you did was show the idioms for implementing functors in three languages, and how c++'s mutability makes it possible to break the mathematical contract and still do useful things.

I don't think you're correct when you say "functors" aren't equivalent in all three languages.

For Prolog though, you really need to think in a different vocabulary. You show the functor predicate unifying F and A with a term. I'm sure there's an idiom for functor usage on par with ML, but I'm not enough of a Prolog wizard to know what it is:)

Very interesting read. Thanks.

A brief comment on your section on Prolog functors:

You say that functors in Prolog "refer to two things". This is a bit weird to say. Clearly, the second thing is just a convenience predicate that Prolog provides for analyzing structures/terms.

This convenience predicate isn't some separate notion of a functor any more than the =.. operator is. The fact that the predicate is called 'functor' shouldn't be taken too seriously. It could just as well have been called 'analyze'.

A functor in Prolog is the atom at the beginning of a structure. It is defined by its name and its arity.

(BTW, the =.. operator is used to decompose structures into lists. e.g. f(1, 2) =.. [f, 1, 2]. is a true statement.)

@Will: No.

"Functor" means so many different things i thought it strange to base an article

on the word.

No what?

No there's not a way to use functors in Prolog that is comparable to their usage in ML? That would be sad.

No functors aren't equivalent in all three mentioned programming languages, ignoring mutability concerns? Well, maybe Haskell enforces some extra constraints, but there's no reason you couldn't conform if you actually needed the mathematical properties that entails.

I think you've misunderstood.

Peter's post was about how four different languages have things they call 'functor' that are completely different. He then went on to explain them. None of the things called 'functor' in the post are related except in that they share the same name. 'Functor' is one of these things that, in computing has radically different meanings depending on context.

Back to Prolog though. Prolog has things called 'atom', essentially symbolic identifiers. Prolog allows you to specify the relationship between various atoms, thus the term 'foo(bar, baz)' states that atoms 'bar' and 'baz' have a relationship symbolised by the atom 'foo'. Prolog calls the atom in a term that symbolises the relationship between its arguments the 'functor', though something like 'predicate' would likely have been a less confusing choice.

you should consider to get rid of Egyptian brackets. the code will be better to read. and those one.liner are even worst.

don't want to annoy you, just a remark from a random programmer who admires your work!

How about you worry about how to write, since you are apparently unable to spell very simple words.

>> fmap id = id

I think the above identity is not quite right. It has different types on either side of the "=" sign. And I think that's a consequence of the fact that a functor maps the identity of the morphisms of one category to that of another - the two identities belong to different categories, not the same as the above identity indicates.

In the case of lists probably the right identity is

map id = [id]. If I check the types for the list identity

map id :: [b] -> [b]

[id] :: [a -> a]

I'm not quite sure if this makes sense, but it feels right. (I'm a Haskell novice.)

And I have no idea how to express this for general functors.

It is correct.

Nice discourse on the C++ functors, which I am currently getting back up to speed on, particularly on retaining functor states. A lot of useful things on this site, so thanks for posting.

Thanks a lot for your useful script regarding to C++. I´m a fan of C++ since I took part in a C++ Workshop. Therefore I like to learn new things about it.

So thanks again.

## Leave a new comment