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 Trees (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 Trees,
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.