kuniga.me > NP-Incompleteness > Functors

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 `a`

type `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 `Maybe`

:

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 `Functor`

:

Thus, we can specify an implementation for `Maybe`

:

… for our `Tree`

datatype:

… and for lists:

We can then use now `fmap`

to perform mapping on lists, `Maybe`

or `Tree`

:

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 `Tree`

.

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 [2] and [3].

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,

Here, both `f()`

and an instance of `Functor`

can be passed as parameter to `callFunction()`

. This is pretty much like the STL `sort`

function.

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.