09 Sep 2012
In Chapter 10 of Real World Haskell, the authors explain how to write a parser for a PGM file.
They start with a very direct and verbose solution. Along the chapter they perform abstractions that allows code reuse. Then, they end up with a much concise and legible solution.
Part of the abstraction makes use of functors, and it’s about them that we’ll talk briefly in this post. Since functors also exists in C++, we’ll talk about them too, even though they represent different concepts in each of these languages.
You’re probably acquainted with maps. Nevertheless, let’s see an example in Haskell:
map (+1) [1,2,3]
A map receives a function that transform an element of type
a in a element in
b and a list of elements of type
a. We can see this by checking the its type on ghci:
What if we want to apply a function to the elements of other structures beside lists?
Let’s start with the
Maybe datatype already defined on Prelude:
In this case, the example
map (+1) (Just 1) will not work. So, let’s write a function to apply the function only to the “internal” type of a
A classical example is performing a map over the elements a tree. Let’s define a datatype
Tree representing a binary tree:
To apply a function to its internal elements we can do:
We can test it by doing:
The Prelude allow us to implement a common interface using the typeclass
Thus, we can specify an implementation for
… for our
… and for lists:
We can then use now
fmap to perform mapping on lists,
Note that we can also apply this function recursively to perform mappings into inner types, for example:
The idea of functors is to perform mappings over the internal elements of datatype, but without affecting its structure.
For instance, a function that receives a
(Just 1) and returns
Nothing, is not preserving the
Maybe structure. The same can be said about any function that changes the topology of a
So, functors are expected to satisfy two properties: identity and composability.
The identity property says that
(fmap id) is equivalent to
id. Since we’re not changing the internal elements neither the structure of a datatype, we are not changing the datatype at all.
The composability means that
(fmap f) . (fmap g) is equivalent to
fmap (f . g)
For further details, this subject is pretty well explained in  and .
In C++ we also have the concept of functors, but it has a different meaning. Here a functor is an object that acts as a function.
Basically, C++ functors are classes that define the
operator(). Here’s an example:
What’s the difference between overloading the
operator() and using any other method instead? For instance, one could define a method
apply() and use it like this:
The answer to the question is that, besides the syntax sugar (i.e. calling
f() instead of
f.apply()), overloading the
operator() allows functors and function pointers to be used alike with templates. Consider the following example,
f() and an instance of
Functor can be passed as parameter to
callFunction(). This is pretty much like the STL
The advantage of functors over regular functions is that they can have internal state, like the example below.
Sure, one could achieve the same behavior with functions using global variables, but with functors we get more encapsulation.