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.
Awesome lesson Saeid. Keep them coming. Your clarity is stunning.
Something to notice: A maybe is actually a list with at most a single element. That's why the patterns apply to both so well.
You can probably also create a function in C++ that concatenates two other functions.
I am sure however there are higher order stuff that Haskell can do that C++ can't. It's most interesting to check those out.
Thanks for the effort!
You're absolutely right, arithma. Maybe can be implemented as a list with at most one element of type T. The check for Nothingness would then be a check on the list size.

Functors aren't just lists, though. For example, functions are also functors. This means that you can map a function over another function to produce a third function. Sounds a little crazy, but it looks something like this:
fmap (^2) (*2) 5
=> 100
What just happened here? Well, it turns out that mapping a function over another function results in a new function that is the composition of the original two. For functions to be functors, all you need to do is define fmap as function composition!

Mind blown yet? Here's how it obeys all the Functor laws: 
(fmap id (+1)) 1
=> 2

(id (+1)) 1
=> 2

(fmap ((+1) . (+2)) (+3)) 5
=> 11

(fmap (+1) (fmap (+2) (+3))) 5
=> 11

Proof of first law:
fmap id f = (id . f) = \x -> f (id x) = \x -> f x = f
id f = f

Proof of second law:
fmap (f . g) h = (f . g) . h = (f . g . h)
fmap f (fmap g h) = (f . (fmap g h)) = (f . (g . h)) = (f . g . h)
Mapping id over a function will return a new function that is equivalent to the function returned from simply applying id to the original function. It's a Functor!
arithma wroteYou can probably also create a function in C++ that concatenates two other functions.
Absolutely! But it's also tricky, I think I'll make the next post about function composition in C++ before diving into applicative functors, since it's such a fundamental idea.

EDIT: forgot to prove the second law!
You can think of a function as a weird list. A function of an integer (single parameter) is almost exactly like an infinite list (or vector, array, table..).
Mapping over a list returns a list. Mapping a function (g) over a function (y for every x) returns a function too (g(y) for every x) without ever passing in the x itself. Makes perfect sense.

I still had an issue earlier with Monads and binding. I remember I "got it" once. But now it's all slipped and can't find time to dig into it again. And yes, it was worth it. A simple abstraction that allows you to reason away from the clutter. And it's mathematical, what else can you ask for!
4 months later
I finally got around to read this one!

@saeidw, I love the way you present these things! Thank you for a very clear explanation.

I learned today that I was indeed familiar with Functors, but coming from Python I called them iterables.

for fun (and practice), I decided to reimplement your Maybe in Lua. (disclaimer: I know absolutely nothing about Maybe beyond this post).

First I wrote a "test suite":
function id(...)
   return ...
end

function curry(f, g)
   return function(...)
      return f(g(...))
   end
end



function test_law1(maybe)
   return eq(fmap(id, maybe), id(maybe))
end

function test_law2(maybe)
   f = function (x) return x+1 end
   g = function (x) return x*2 end
   return eq(fmap(curry(f, g), maybe), fmap(f, fmap(g, maybe)))
end
eq is a comparison function. I have no idea if Lua supports operator overloading, and the native "==" will compare locations in memory, not values. Here's my first implementation of Maybe, using an approach similar to yours in C++:
function Nothing()
   maybe = {}
   maybe.empty = true

   return maybe
end

function Just(x)
   maybe = {}
   maybe.empty = false
   maybe.just = x

   return maybe
end

--# again no operator overloading. 
function display(maybe)
   if maybe.empty then
      print("Nothing")
   else
      print("Just " .. maybe.just)
   end
end

function fmap(func, maybe)

   local new_maybe = {}

   if not maybe.empty then
      new_maybe.just = func(maybe.just)
   end

   return new_maybe

end

function eq(may1, may2)
   return (may1.empty and may2.empty) or may1.just == may2.just
end
Reading on, arithma had the good idea of simplifying the representation to a simple one-element list. Here's a Lua implementation of it as well:
function Nothing()
   return {}
end

function Just(x)
   return {x}
end

function display(maybe)
   if # maybe == 0 then
      print("Nothing")
   else
      print("Just " .. maybe[1]) --# because Lua indexes start at 1
   end
end

function fmap(func, maybe)
   new_maybe = {}

   for idx, val in ipairs(maybe) do
      new_maybe[idx] = val
   end
end

function eq(may1, may2)
   return # may1 == # may2 == 0 or may1[1] == may2[1]
end
And then you showed that a Functor can be implemented as a function. So it got me thinking and ... here's my implementation of a Maybe, using functions (lambdas)!
function Nothing()
   return function() return nil end
end

function Just(x)
   return function() return x end

function display(maybe)
   a = maybe()
   if a then
      print ("Just " .. a)
   else
      print ("Nothing")
   end
end

function fmap(func, maybe)
   return function()
      return maybe()
   end
end

function eq(may1, may2)
   return may1() == may2()
end
If you want to understand the above code; in Lua functions are created with the keyword function that behaves pretty much like a lambda. The construct function Foo (x) is just syntactic sugar for Foo = function(x).

A few worthy notes:
- I haven't tested the code yet. I only typed it into my editor and really need to get out now. There may be minor problems at run time, but the core idea is there.

- Notice how my third implementation is the most concise one. The truth is, it's a lot easier doing what I do when you use dynamic languages like Lua. But I guess we all agree that something like this should not go anywhere near production without static typing.

- If you want to maximize the rockstar effect, translate my last implementation to Scheme and have all these lambdas/parens combo pop out. (Lua and Scheme are super close. Such a translation should be doable. I'm working on it tonight for practice. If anyone's interested I would gladly post it ><)

EDIT: I originally wanted to write Nothing() as a lambda that doesn't return anything. But because of Lua's special treatment of nil (and namely every variable is nil unless assigned a value) it's easier to have Nothing() return nil. The only downside is that Nothing() == Just(nil). Other languages like Haskell won't have this problem.


One last thing
saeidw wroteThe 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.
??
s/12/100/ ?