16 Jul 2012

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

or *ptr<T>*`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 `string`

s to `int`

s, to various encapsulations of `string`

s, and obtain the corresponding encapsulations of `int`

s.

#### Pointers

Let's try first doing that for a `unique`

. We are given a *ptr*`uniqueptr<string>`

and we want to get a `unique`

, which contains the length of the string. This new transformation which transforms *ptr<int>*`uniqueptr`

s 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:

unique_ptr<int> liftedLength(unique_ptr<string> s) { return unique_ptr<int>(new int(length(*s))); }

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`

:

template<class A, class B> unique_ptr<B> fmap(function<B(A)> f, unique_ptr<A> a) { return unique_ptr<B>(new B(f(*a))); }

Equipped with `fmap`

we can, for instance, trim a string inside `unique_ptr`

:

fmap<string, string>(&trim, unique_ptr<string>(new string(" Hi! ")));

We can also compose lifted functions:

unique_ptr<string> p(new string(" Hi! "));auto np = fmap<string, int>(&length, fmap<string, string>(&trim, move(p)));

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

s. Piece of cake:

```
vector<int> liftedLength(vector<string> strings) {
unsigned size = strings.size();
vector<int> lengths(size);
for (unsigned i = 0; i < ++i)="" lengths[i]="<span" size;="" style="color:#00a">length(strings[i]);
return lengths;
}
```

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:vector<int> liftedLength(vector<string> strings) { vector<int> lengths; transform(strings.begin(), strings.end(), back_inserter(lengths), &length); return lengths; }

Obviously, this code can be generalized to lift any function `f`

taking `A`

and returning `B`

:

template<class A, class B> vector<B> fmap(function<B(A)> f, vector<A> as) { vector<B> bs; transform(as.begin(), as.end(), back_inserter(bs), f); return bs; }

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`

:

map :: (a -> b) -> [a] -> [b]

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:

liftedLength :: [String] -> [Int] liftedLength str = map length strThe 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):

map :: (a -> b) -> ([a] -> [b])

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:

liftedLength :: [String] -> [Int] liftedLength = map length

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:

fmap = map

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`

:

function<int()> liftedLength(function<string()> fStr)

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:

function<int()> liftedLength(function<string()> fStr) { return [fStr]() { return length(fStr()); }; }

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:

template<class A, class B> function<B()> fmap(function<B(A)> f, function<A()> fA) { return [f, fA]() { return f(fA()); }; }

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:

newtype Reader c a = Reader (c -> a)

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:

run :: Reader c a -> c -> a run (Reader f) cfg = f cfg

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:

liftedLength :: Reader c String -> Reader c Int liftedLength rdrStr = Reader (λ cfg -> length (run rdrStr cfg))

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`

:

fmap :: (a -> b) -> Reader c a -> Reader c b fmap f rdA = Reader (λ cfg -> f (run rdA cfg))

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

:

function<A(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):

template<class C, class A, class B> function<B(C)> fmap(function<B(A)> f, function<A(C)> rdA) { return [f, rdA](C cfg) { return f(rdA(cfg)); }; }

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:

class Functor f where fmap :: (a -> b) -> f a -> f b

You can read it as: A type constructor `f`

is a `Functor`

if there is a function `fmap`

with the type signature:

fmap :: (a -> b) -> f a -> f b

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

s. 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:

instance Functor [] where fmap = mapThe 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:

fmap id = idIn 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.

fmap (f . g) = fmap f . fmap gThe 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:

ex1 ex2 ex3as a call to the function produced by

`ex1`

with arguments produced by `ex2`

and `ex3`

(the `ex`

s stand for arbitrary expressions). It's even more confusing when the expressions themselves are parenthesized, as in this made up example:
(getOp "add") (getX n) (getV k m)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:function<string(string)> greet = bind(&concat, "Hello, ", placeholders::_1); cout << greet("Haskell!") << endl;

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

):

greet = (++) "Hello, " greet "Haskell!"

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

f :: a -> b -> c

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']