The Gang of Four book introduced many a C++

programmer to the world of patterns. Those patterns are mostly

based on everyday examples, although there are a few more abstract

ones like Strategy. In Haskell (and other functional languages)

most patterns are very abstract. They are often based on

mathematical constructs; category theory being a major source of

ideas.

Arguably it's easier to grok terms like Factory, Facade, or

Visitor from the GoF book than the ones from the Haskell arsenal,

like Monad, Monoid, or Applicative Functor.

You might not know that, but some of the best C++ programmers

use functional abstractions in their work. Alexander Stepanov used

many functional patterns in designing the C++ Standard Template

Library -- his education in mathematics was no doubt a big factor

in this groundbreaking work. I'll show you some of these patterns

later.

In my previous blog I described a functional approach

to asynchronicity in C++ based on the Haskell's Continuation Monad.

For many readers that might have been too big of a jump -- not only

is the Monad pattern unfamiliar in the imperative world, but the

Continuation Monad is one of the hardest to wrap your brain around.

This is why I decided to back off a little and write a few posts

that will introduce functional patterns more gradually. As a bonus,

these patterns will expose some interesting aspect of asynchronous

programming.

Here's the plan: In this installment I will introduce the

Functor pattern (the real "functor," not the misnomer for a

function object). More posts on Functors, Applicative Functors,

Monads, and Monoids will follow. I promise to stay away from

category theory.

Type Constructors

Let's start looking for some hidden patterns. The first one is

called a type constructor. In every programming language you have

some basic types like integers, doubles, etc.; and then you have

ways of defining new types. Type constructors create new types from

old types.

There are some built-in type constructors in C++. For instance,

by adding an asterisk to any type, you create a pointer to that

type (well, never say always in C++: there are always

exceptions to every rule). You can have a pointer to

int, as in int *), a pointer to bool, a pointer to a pointer, a pointer to a function,

etc. Give me any type (except for a few outliers) and I'll create a

pointer to that type. Pointer is a type constructor.

You can create even more type constructors using templates.

Generalizing a built-in pointer type constructor, we have the smart

pointer type constructors, such as

uniqueptr<T> or sharedptr<T>. Again, these type constructors work for any type T (with the above caveat).

Arrays are another example of a built-in type constructor. You

can define array types by adding square brackets to almost any

type, as in int[].

Generalizing arrays, we have user-defined containers. All

containers in STL are type constructors. For instance, take almost

any type T and you can create a std::vector<T>.

Function types are also created using a built in type

constructor. Take any type and append a pair of parentheses to it

and you get a function type (a function returning that type, as in

int()).

Again, we can generalize function types to function objects, in particular the STL std::function template, which is, you guessed it, also a type constructor.

In general type constructors can take more than one type as

input, or no type at all (nullary type constructors). They are just

like functions that operate on types rather than values.

In what follows I will concentrate on unary type constructors,

because they are the building blocks of functors. An n-ary type

constructor can always be turned into a unary one by providing

concrete types for n-1 of its inputs. For instance,

pair<A,B> can give rise to unary type constructors pair<A,int> or pair<double *,B>.

There is another way of looking at type constructors: An object

of the constructed type hides a value (or values) of the original

type. That's easy to see with pointer types: a pointer to

int hides an int. You can access that int by dereferencing the pointer. The same goes for

smart pointers. A container hides multiple values of its basic

type. A vector<float> contains floating point

values. They can be accessed through indexing or through

iterators.

Functions are an interesting type. They are not containers but

they, too, can "hide" a value -- the value they return. This value

can be accessed by executing the function. When you call a function

of the type int(), it returns a value of the type int, etc. We'll talk more about function types later.

Functors

Now that you can recognize the Type Constructor pattern, let's

look for some more structure. As I said, type constructors may be

thought of as encapsulating values of their input types. You can

work on those values by first exposing them, applying some

transformation, and then hiding them back. But this is tedious and

it breaks encapsulation. What if you had a way of transforming

hidden values without exposing them to the public. That's exactly

what a functor does. It's a combination of a unary type constructor

and a prescription for applying functions to hidden values.

Let's try it with some of the type constructors we've seen so

far. For simplicity, I'll pick one particular transformation: It

takes a string and returns an int. Let's represent it by a function length. We want to apply this transformation, which turns strings to ints, to various encapsulations of strings, and obtain the corresponding encapsulations of ints.

Pointers

Let's try first doing that for a uniqueptr. We are given a uniqueptr<string> and we want to get a uniqueptr<int>, which

contains the length of the string. This new transformation which

transforms uniqueptrs is often called the lifting of the original transformation. In other

words, we are lifting a function acting on input types to a

function acting on output types of the type constructor.

Let's try it:

We did have to expose the value hidden in the unique_ptr in the implementation of the lifting, but the client can use liftedLength and similar functions

without breaking the encapsulation. (By the way, I'm not worrying

about null pointers here -- that's a different pattern

altogether.)

Now replace length with any other function f from A to B. It's very

easy to generalize our lifting formula. The lifting function is

traditionally called fmap:

Equipped with fmap we can, for instance, trim a string inside unique_ptr:

We can also compose lifted functions:

The notation is awkward, but the idea is simple.

The type constructor unique_ptr<T> and the above lifting function, fmap, form a Functor.

Containers

Now let's do the same thing with a vector of strings. The lifting of length should take such a vector and return a vector of ints. Piece of cake:

I used indexing to access both vectors because that's what I said

about accessing values hidden inside vectors. Alex Stepanov would

probably shudder seeing this code. That's because he provided a

very general way of lifting any function to containers. First of

all, he abstracted access to all containers using iterators, and

then created the std::transform algorithm which lifts

any function to the level of iterators. So here's the lifting of

length the STL way:

Obviously, this code can be generalized to lift any function f taking A and returning B:

The vector<T> type constructor with its corresponding fmap form a Functor.

A little Haskell digression

So far these have been pretty straightforward examples. Even

though they were simple, expressing them in C++ produced quite a

bit of syntactic noise. This noise will get increasingly louder

with more complex examples. So we need a better way of expressing

functional pattern in order to make progress. As I argued previously, knowing Haskell is a great

help in designing and understanding more advanced patterns in C++.

So let's take a little break and see what the last example would

look like in Haskell.

The canonical equivalent of a C++ vector is a Haskell list. Just like vector in C++, list is a type constructor in Haskell. A list of values of type a (type variables are lower-case in Haskell) has type [a]. The version of fmap for lists is defined in the standard Haskell library called Prelude, and is called map.

Here's the signature of map:

Let me translate it: map is a function of two arguments, the first being itself a function a->b that takes an a and returns a b. The second argument, [a], is a list of a. The

result -- the thing after the last arrow -- is of type

[b], a list of b. The lifting of the function length would be expressed in Haskell like this:

The first line (it is optional because Haskell has a powerful type

inference system) shows the type of the lifted function: from lists

of strings to lists of integers. The second line defines the

function liftedLength that takes a str and applies map to the function length and the string str. (In Haskell you don't use

parentheses around function arguments, neither in the definition

nor in the application.)

Interestingly, because of currying (see the Appendix), the signature of map can be rewritten as (pay attention to parentheses):

which can be read as map being a function that takes a function a->b and returns a function [a]->[b]. In fact the definition of liftedLength can be simplified to:

which defines one function in terms of another (curried)

function. Now the whole "lifting" thing starts making sense. We

start with the function length :: String->Int and lift it to a function liftedLength :: [String]->[Int]. The lack of currying in C++ makes such simple things difficult to express.

You can lift any function, not only length, this way. Just look at the signature of map, which is

exactly what you'd for the general lifting function

fmap for lists. So map is the fmap for lists:

Let's go back to some more C++ examples.

Function Objects

This is a little tricky, but the ability to think of functions

as first class citizens is an essential skill in programming, and

practically all imperative languages learned to recognize this

fact. In general, a function type constructor takes one type for

the return value and zero or more types for arguments. For

simplicity, let's first consider nullary functions. Given any type

T we can construct a function-type T() or, more generally, std::function<T()>: a function that takes no arguments and returns T. The generalized function object, std::function, not only

deals with regular functions, but also with function objects

(objects that overload operator()), lambdas, closures, methods, etc.

How can we lift the function length to operate on

functions? The lifted function must accept a function returning

string and produce a function returning int:

In order to return a function, we have to generate it on the

fly. In C++11 we can do that with lambdas. Here,

liftedLength should return a function that extracts the string from fStr and applies length

to it. Remember, extracting a value for a function means simply

executing it. Here it is:

Notice that the returned function is really a closure -- it captures fStr. This anonymous function/closure is converted into std::function object upon return.

This formula can be easily generalized to lifting an arbitrary function:

For many C++ programmers this might be the first encounter with

higher order functions that take functions as arguments and also

return functions. In Haskell this is standard fare.

We conclude that the nullary function constructor and the corresponding fmap form a Functor. In itself, this

particular functor might not seem very useful, but it is a stepping

stone toward much more interesting cases, like continuations,

threads, or asynchronous calls.

Back to Haskell

In Haskell, which shuns side effects, a function that takes no

arguments is not very interesting. So let's generalize the above

example slightly: we'll look at functions taking some fixed type,

c, with no restrictions on the return type a. Let's call such functions "readers" because they

can only read c, not modify it. You might think of values of type

c as, say, some configuration data that's passed around.

Here's the type constructor:

I have defined a new data type, Reader parameterized by two types c and a. The

right hand side of the definition says that I can create a

Reader from any function c->a that takes c and returns a. It also says, in

the same breath, that in order to extract that function later, I'll

have to pattern-match a Reader object using the pattern (Reader f). Trust me, that's what it says.

The major reason for extracting a function from a reader is to apply it to some value of type c. Let's define a separate helper function to do just that:

The first (optional) line shows the type signature of run: It's a function that takes a reader and some config, and returns a value of type a. The second line is the implementation. The first argument to run is pattern matched to (Reader f). This way we gain access to the function f that was encapsulated in the reader argument. The second argument is config cfg. In the body of the definition we apply f to cfg.

The lifting of length is now pretty straightforward:

We have to return a new function (encapsulated in the Reader constructor): the lambda that takes an argument cfg and returns the result of length acting on the result of fStr applied to cfg. You might want to read this description a few times before it clicks.

The generalization to fmap is straightforward -- just replace length with f:

Back to C++

What does a Reader look like in C++? The type

constructor is a function-type constructor that is parameterized by

two types, A and C:

We'll keep C fixed and vary only A (we

are in fact currying the type constructor when we provide concrete

type for C). Here's the definition of fmap (notice: the same C throughout):

After seeing the Haskell code, that was pretty easy, right?

Unfortunately things are never easy in C++ so in the next blog post

I'll show you a more careful implementation of Reader, as well as Async from my previous blog. For now, let us conclude that Reader together with the corresponding fmap is a Functor. We have a type

constructor and a prescription for applying functions to its

"hidden" value.

Again, the Reader functor doesn't seem like it

would be very useful in C++. Why would anyone carry around some

configuration data if it's easier to make them global? Hmm... What

about many different configurations? Access them by key? What about

passing the key then? And what if you change the word

"configuration" to "credentials"? Would you still want to make them

global?

Functor as a Haskell typeclass

In C++ we'll just work with the functor pattern without

abstracting it further. But in Haskell such patterns can be

generalized using type classes. The closest thing to type classes

in C++ were concepts, which didn't make it into the C++11 Standard.

A Haskell type class describes a whole family of types that have

something in common. In the case of functors, this common thing is

the presence of the lifter: the function fmap. But a

Functor doesn't just describe a type, it describes a type

constructor -- a particular mapping from types to types. So a

Functor type class unifies a whole class of type constructors. Here's the definition of a Functor in its full glory:

You can read it as: A type constructor f is a Functor if there is a function fmap with the type signature:

Notice that f is applied to types a and b. That's how we know that f is a

type constructor. In fact this is how the Haskell compiler knows

that f is a type constructor. It looks at the usage.

Having defined a type class we can now tell Haskell which type constructors are Functors. We do that by declaring

instances of the type class. For example, I told you that a list

constructor [] is a functor. Here's how I tell that to Haskell:

The instance definition must provide the implementation of the

associated function (or functions, plural, in general). Here we

define fmap in terms of an existing function, map.

Would any implementation of fmap work for a Functor? Not really. There are two additional functor laws which unfortunately cannot be enforced by Haskell.

The first law states that the lifting of the identity function (called id in Haskell) must also be identity:

In other words if you apply identity to the values hidden in your

type constructor, nothing will change.

The second law states that lifting a composition of two functions is the same as composing the lifted functions.

The dot means the application of one function to the result of

another.

It's good to know about these laws, but in most practical cases

they are trivially true. And, when a type constructor is a good

functor candidate, there usually is only one obvious way to

implement fmap, as I demonstrated in the examples above.

Conclusion

The Functor pattern is ultimately about code reusability and

composability -- two major pillars of programming. Whenever you

create a new way of encapsulating data of arbitrary type, that is a

type constructor, you should ask yourself the question:

How can I reuse my existing libraries on data that is encapsulated through this type constructor?

I'm talking about libraries that contain functions like length, which don't know how to work on a unique_ptr<string> or a vector<string>.

The naive approach would be to expose the encapsulated data in

an ad hoc manner and apply library functions to it. For a multitude

of reasons, this is not a good solution, and it gets really hairy

when you're dealing with function-type constructors. The Functor

pattern allows you to accomplish all this without breaking the

encapsulation, simply by defining one template function,

fmap.

The Functor pattern is especially powerful when working with

function types. A function does not contain a value (unless it's a

constant function) -- it is a "promise" to create a value when

executed. A functor allows you to arbitrarily compose operations

on (the results of) those functions without immediately

executing them. This is the basis of the general approach to

asynchronous APIs I described in my previous post and will

elaborate on in my next post.

Acknowledgments

I'd like to thank Eric Niebler for many valuable comments on the draft of this post.

Appendix: Currying

Many people find function syntax in Haskell confusing because

there are no parentheses around, or commas between, arguments. It

takes some getting used to to interpret the following pattern:

as a call to the function produced by ex1 with arguments produced by ex2 and ex3 (the exs stand for arbitrary expressions). It's even more

confusing when the expressions themselves are parenthesized, as in

this made up example:

This syntax makes perfect sense in Haskell, where currying is a

national sport. In other languages, when you call a two argument

function with one argument you get an error: Not enough arguments.

In Haskell you get a curried function. It's a new function that

takes one (remaining) argument. The only way you can do it in C++

is by using a (somewhat awkward) template function

bind. For instance, this is what you'd do if you wanted to curry a two-argument function concat, passing it "Hello, " as the first argument:

Here's the equivalent code in Haskell (where, incidentally, concat is an infix operator ++):

Now the type signatures of two-argument functions start making sense:

This means that the function f takes two arguments of types a and b and returns c; or, equivalently, that it takes one argument of type a and returns a function b->c.

It's all the same, you see, and right associativity of the arrow

-> makes the use of parentheses redundant (here's the equivalent parenthesized version: f :: a -> (b -> c)). [twitter-follow screen_name='BartoszMilewski']