Warning: The following post is longer than some PhD dissertations, read when you have free time!

So I was playing with Haskell and wrapping my head around typeclasses.
I came across the work of Bartosz Milewski and I really like the way he can seamlessly translate between C++ and Haskell.

So, I decided to do something similar with the Functor typeclass.

1. The low-down
Functors are things which can be mapped over. This means if you have a function f , you can apply map it over the functor to get a new functor with f applied to it.

Lists are functors. You can map a function over a list to get a new list with that function applied to it:

fmap (+1) [1,2,3,4]
=> [2,3,4,5]

fmap (+1) []
=> []

The function fmap takes a function (in this case (+1)), and a functor (our list) and maps that function over the functor to produce a new functor. Mapping a function over the empty list gives you the empty list, because there's nothing to do!

2. Uncertainty
Lists aren't the only things that are functors. The Maybe type is also a functor. Maybe is a type that can have either a value of Nothing or Just T, where T can be anything, an int, a char, whatever.

Here's a definition of Maybe in Haskell:

data Maybe a = Nothing | Just a

Let's translate that to C++:

template<typename T>
struct Maybe
{
    bool isNothing;
    T just;
};

So now, we can have a Maybe<int>. When isNothing is true, variables of this type contain Nothing, otherwise, they contain some data in the just field. Let's write some functions to make it easier to create values of this type:

template<typename T>
Maybe<T> Nothing()
{
    Maybe<T> r;
    r.isNothing = true;
    return r;
}

template<typename T>
Maybe<T> Just(T x)
{
    Maybe<T> r;
    r.isNothing = false;
    r.just = x;
    return r;
}

So now, we can do things like this:

Maybe<int> m = Just(5);
Maybe<int> n = Nothing<int>();

Maybe<bool> nb = Nothing<bool>();

Maybe<Maybe<int> > double_maybe = Just(Nothing<int>());

We need an easy way to display these values, so let's overload the << operator:

template<typename T>
ostream& operator<<(ostream& out, Maybe<T> m)
{
    if (m.isNothing) {
        out << "Nothing";
    } else {
        out << "Just " << m.just;
    }

    return out;
}

Simple, right? If our Maybe is a Nothing, we print "Nothing", otherwise we print "Just <value>".
That's about all there is to know about Maybe in the context of C++. It's really useful when a function can return a value or nothing.

3. Mapping stuff over Maybe
So how is Maybe a functor? In order for it to be a functor, there needs to be a function, fmap, that we can use to map functions over values of type Maybe.

In Haskell:

fmap (+1) (Just 5)
=> Just 6

fmap (+1) Nothing
=> Nothing

Just like in the list example, mapping (+1) over Just 5 gives us a new Maybe with the value Just 6.

Notice that mapping a function over Nothing gives us Nothing because there's nothing to do, just like in the case of the empty list.

Well, that's awesome and everything, but how do we define fmap. Let's look at how Haskell does it:

The type signature of fmap for Maybe looks like this:

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

And the implementation is like so:

instance Functor Maybe where
    fmap f Nothing  = Nothing
    fmap f (Just x)  = Just (f x)

We can see from the definition that mapping a function over Nothing yields Nothing, and that mapping a function over Just x will first apply that function to x and then produce a Maybe out of the result.

Let's translate this into C++:

template<typename A, typename B>
Maybe<B> fmap(B (*f)(A), Maybe<A> a)
{
    if (a.isNothing) {
        return Nothing<B>();
    }

    return Just(f(a.just));
}

Our fmap takes a function pointer and a Maybe<A> and returns a Maybe<B>. Naturally, the function f must take an A and return a B. The implementation is the same as in Haskell. If a is Nothing then the result is Nothing, otherwise we apply f to the value contained in a and wrap the result in a Just.

4. Obeying the law
All functors have to obey two laws in order for fmap to make sense.

1. fmap(id, F) == id(F). Where id is the identity function and F is a functor.
2. fmap(fDotg, F) == fmap(f, fmap(g, F)). Where f and g are functions, and fDotg is f(g(x)).

The identity function is simply a function that returns its parameter without doing anything, it looks like this in Haskell and C++:

Haskell:
id x = x

C++:
template<typename T>
T id(T x) { return x; }

Naturally, mapping id over, say, Just 5 will give us Just 5. An applying id to Just 5 will also give us Just 5.

Does our C++ definition obey this law? Try the following code

int (*idfn)(int) = id;

Maybe<int> m = Just(5);

Maybe<int> l = fmap(idfn, m);
Maybe<int> n = id(m);

cout << l << endl; // => Just 5
cout << n << endl; // => Just 5

The output for both l and n is Just 5. This means they are equal, so our implementation of fmap definitely obeys the first law.

The second law of functors (you do not talk about functors!) is that when you take two functions and compose them together into a third function and map it over the functor, that should give you the same result as first mapping the first function over the functor, and them mapping the second one.

Let's define some stuff:

int f(int x) { return x * x; }
int g(int x) { return 2 * x; }
int h(int x) { return f(g(x)); }

Now we can test our code like so:

Maybe<int> m = Just(5);

cout << fmap(f, m) << endl; // => Just 25
cout << fmap(g, m) << endl; // => Just 10

cout << fmap(h, m) << endl; //=> Just 100
cout << fmap(f, fmap(g, m)) << endl; // => Just 100

The interesting parts are the calls to fmap(h, m) and fmap(f, fmap(g, m)).
The first call maps h (which is just f(g(x)) over m. The second one first maps g over m and then maps f over the result. As you can see, the resulting value in both cases is Just 100, showing that the two calls are equal. This means that our implementation also obeys the second law.

The second law tells us that composing functions and then mapping the composition over a functor is exactly the same as composing calls to fmap, each with a single function.

In Haskell, this lets you do awesome stuff like:

fmap ((^2) . (*2)) (Just 5)
=> Just 100

The code above first applies the function (*2) to 5, producing 10, and then applies (^2) to 10, squaring it, to produce 12, and then wraps that up in a Just and gives it back to us.

5. Conclusion
C++ is a twisted language with a crazy template system that can let you do some cool things.
Today we implemented the Maybe type and showed how it behaves as a functor by implementing fmap and demonstrating the two laws.

Next time, if there is a next time, we'll discuss Applicative Functors, they're even cooler than functors, and Maybe happens to be one of them!

Feel free to ask questions or flame me for this exceedingly long post.