Saturday, October 27, 2012

Monads in C++

In my last two articles, I discussed fmap in C++. At the end, I implemented it with a solution of tag dispatch and a type class, calling it type-class dispatch. Today I want to talk about the next step: monads. Familiarity with fmap is required, but not monads or Haskell. I will be using the same type-class dispatch code here as in the last post, but without explanation.

struct sequence_tag {};
struct pointer_tag {};

template< class X >
X category( ... );

template< class S >
auto category( const S& s ) -> decltype( std::begin(s), sequence_tag() );

template< class Ptr >
auto category( const Ptr& p ) -> decltype( *p, p==nullptr, pointer_tag() );

Monads are scary. Or at least they seem scary. People talk about them like they are. In reality, they are not much more complicated than Functors, being very similar. Previously, the problem was that we have a function f and a Functor, F(x). fmap simply allowed us to apply f to the data inside the Functor. Monads do the same thing, except that f is monad-aware and returns a monad of the correct type. For example, with fmap we might write

std::unique_ptr<int> p( new int(5) );
auto f = []( int x ) { return -x; };
std::unique_ptr<int> q = fmap( f, p );

and we know that (*q) = -(*p). What if f knew that we wanted to have a unique_ptr returned? Well, then we could use the monad's version of fmap, which I'll refer to as mbind (monad bind).

std::unique_ptr<int> p( new int(5) );
auto f = []( int x ) { 
  return std::unique_ptr<int>( new int(-x) ); 
};
std::unique_ptr<int> q = mbind( f, p );

So what is a Monad? Almost the same as what a Functor is!

    If fmap(f,F(x)) = F(f(x)),
        then mbind(f,M(x)) = f(x), or something like that.

Monads can be std::vectors or std::unique_ptrs, std::pairs; the limit is your imagination.

Monads have one more ability: to construct a type, M(x), given an x, with a function called return. But return means two different things in Haskell and C++, so I'll use the term mreturn. This is a pretty simple concept--we can rewrite the above example like so:

std::unique_ptr<int> p( new int(5) );
auto f = []( int x ) { return mreturn(-x); };
std::unique_ptr<int> q = mbind( f, p );

In this example, mreturn is a function that takes an int and returns an std::unique_ptr<int>.

And so we have two basic operations:

    auto m = mreturn<M>(x); // creates an M<X>
    mbind( f, m ); // Applies f to x.

And we know

    auto p = mreturn<unique_ptr>(3); // will create a unique_ptr<int>.
    mbind( f, p ); // is equivalent to f(*p)

And we'll consider, for the moment, that a Monad is a type for which this operation is defined.

I'll implement this much the same way I did fmap. We start with a free function, mbind, which maps to the static member function Monad::mbind, and mreturn which maps to Monad::mreturn.

template< class ... > struct Monad;

template< class F, class M, class Mo=Monad<Cat<M>> >
auto mbind( F&& f, M&& m )
    -> decltype( Mo::mbind(std::declval<F>(),std::declval<M>()) )
{
    return Mo::mbind( std::forward<F>(f), std::forward<M>(m) );
}

// The first template argument must be explicit!
template< class M, class X, class Mo = Monad<Cat<M>> >
M mreturn( X&& x ) {
    // We have to forward the monad type, too.
    return Mo::template mreturn<M>( std::forward<X>(x) );
}

One might notice that the above example using mreturn and this definition don't match. Instead of calling mreturn(-x), it should call mreturn<std::unique_ptr<int>>(-x). However, the int part is redundant, so let's overload mreturn using a template template parameter so we only have to supply std::unique_ptr.

template< template<class...>class M, class X, 
          class Mo = Monad<Cat<M<X>>> >
M<X> mreturn( const X& x ) {
    return Mo::template mreturn<M<X>>( x );
}

Now, we can write that example like so:

std::unique_ptr<int> p( new int(5) );
auto f = []( int x ) { 
  return mreturn<std::unique_ptr>(-x); 
};
std::unique_ptr<int> q = mbind( f, p );

The pointer monad.

template< > struct Monad< pointer_tag > {
    template< class F, template<class...>class Ptr, class X,
              class R = typename std::result_of<F(X)>::type >
    static R mbind( F&& f, const Ptr<X>& p ) {
        // Just like fmap, but without needing to explicitly return the correct type.
        return p ? std::forward<F>(f)( *p ) : nullptr;
    }


    template< class M, class X >
    static M mreturn( X&& x ) {
        // All smart pointers define element_type.
        using Y = typename M::element_type; 
        return M( new Y(std::forward<X>(x)) );
    }
};

This may not be the most exciting code, but we can use it to translate a small Haskell function into C++.

    -- Haskell
    addM a b = do
        x <- a -- Extract x from a
        y <- b -- and y from b.
        return (x+y) -- Return a new monad with the value (x+y)

If we supplied two unique_ptrs, we'd get one back holding the value x+y. The first line, x <- a, syntactically means "what fallows is a function of x." This is addM with do notation; another way to write it:

    addM a b = a >>= (\x -> b >>= (\y -> return (x+y)) )

Here, >>= denotes a bind and (\x->...) denotes a lambda that takes x. The inner-most function, (\y -> return (x+y)) returns the actual value as a monad. It gets called when we extract the value from b with (\x -> b >>= ... ). The x came from a >>= (\x -> ... ). So it extracts x from a, then y from b, and constructs a new monad with the value x+y.

// C++
template< class M >
M addM( const M& a, const M& b ) {
    return mbind (
        [&]( int x ) {
            return mbind ( 
                [=]( int y ) { return mreturn<M>(x+y); },
                b
            );
        }, a

    );
}

Yuck! This is a literal translation, but Haskell handles scope automatically with do notation and it implicitly returns the last statement, while we write return mreturn<M>.  We can rewrite this to use fmap([=](int y){return x+y;},b) and that solves the return problem, but not the scoping one. We can alleviate that by defining an operator overload for mbind, and why not use the very same operator as in Haskell?

template< class M, class F >
auto operator >>= ( M&& m, F&& f )
    -> decltype( mbind(std::declval<F>(),std::declval<M>()) )
{
    return mbind( std::forward<F>(f), std::forward<M>(m) );
}

template< class M >
M addM( const M& a, const M& b ) {
    return a >>= []( int x ) {
        return fmap( [=]( int y ){ return x+y }, b );
    };
}

It's hard to justify the use of operator overloads in C++, but this one rarely gets any use. It won't change the behavior of basic types; given some int x, x >>= 2, this still means you with to shift the bits by two. If this gives one an uncomfortable feeling, it can be put in its own namespace so that in order to make use of the operator overload, the user would have to write using namespace monad; or whatever before writing >>=.

Monadic sequences.

Remember, fmap(f,seq) took a regular function and made a new sequence by applying f to seq. What will mbind(f,seq) do? This time, f is monad-aware, so it already returns a sequence. Does mbind return a sequence of sequences? That would be very confusing. It actually returns the concatenation of every sequence produced by f(x). So, if f(x)={-x,x}, then mbind(f,{1,2}) = {-1,1,-2,2}.

template< > struct Monad< sequence_tag > {
    template< class F, template<class...>class S, class X,
              class R = typename std::result_of<F(X)>::type >
    static R mbind( F&& f, const S<X>& xs ) {
        R r;
        for( const X& x : xs ) {
            auto ys = std::forward<F>(f)( x );
            std::move( std::begin(ys), std::end(ys), std::back_inserter(r) );
        }
        return r;
    }

    template< class S, class X >
    static S mreturn( X&& x ) {
        return S{ std::forward<X>(x) }; // Construct an S of one element, x.
    }
};
std::move from <algorithm>

What implications does this have on our addM function? If v={1,2} and w={3,4}, what does addM(v,w) return? Try it!

int main() {
    std::vector<int> v={1,2}, w={3,4};
    auto vw = addM(v,w);

    std::cout << "v+w = { ";
    std::copy (
        std::begin(vw), std::end(vw),
        std::ostream_iterator<int>(std::cout, " ")
    );
    std::cout << '}' << std::endl;
}

Just in case you didn't actually run the code, it prints { 4 5 5 6 }. Does this sequence seem odd? It's { 1+3 1+4 2+3 2+4 }. Basically, it applied the addition function on every pair of elements from v and w. That means add(v[0],w[0]) then add(v[0],w[1]) then add(v[1],w[0]) then add(v[1],w[1]).

This is the magic of monads. The functionality of addM changed appropriately to how its arguments changed. It did so without us even thinking about how it might. And now, every type that can hold an int that one specialized mbind for works with addM, too!


In conclusion:

Monads are often talked about as mysterious, tricky, and hard to understand. They are none of these. It is of little importance to know concretely what a monad is. mbind is a simple function that applies some function, f, to some object M(x), where f returns M(y). mreturn is a simple function that constructs an object of type, M(x), given an x.

Note that Haskell also has a Monad function, >>, or mdo as I call it (though I can't remember why). mdo is not always as obvious as mbind, however I did implement it in the gist (see below).

In full, the monadic operations are:

    a >> b ; //  see the gist
    a >>= f ; // Apply the value(s) in a to f.
    mreturn<M>(x) ; // Create an M<X>.

There are a few helpful properties of this:

    mreturn<M>(x) >>= f == f(x)
    m >>= mreturn<M> == m 
    m >>= (\x -> k x >>= h) == (m >>= k) >>= h


Here's the code I wrote for this article: https://gist.github.com/3965514 (It contains a few extra examples.)
Monads in Haskel: http://www.haskell.org/ghc/docs/latest/html/libraries/base/Control-Monad.html#t:Monad

Friday, October 26, 2012

fmap in C++

Previously, I went over an introduction and explanation of fmap and a plausible implementation in C++, but couldn't achieve the same level of usefulness as in Haskell. Today I want to implement a much more generally useful fmap. This post assumes a working knowledge of fmap, but not of Haskell.

Just to review: fmap is a general way of saying "apply f to the value(s) of F(x)", where F, or Functor, might be an std::vector or std::unique_ptr or some user-defined type. For example fmap(f,ptr) means "apply f to the value ptr contains".

The problem was that we wanted one fmap that worked on all STL-like containers, and one that worked on all smart pointers, but the two functions had the same signature and it wouldn't compile.

template< class F, template<class...>class S, class X,
          class R = typename std::result_of<F(X)>::type >
S<R> fmap( F&& f, const S<X>& s ) {
    S<R> r;
    std::transform( std::begin(s), std::end(s),
                    std::back_inserter(r),
                    std::forward<F>(f) );
    return r;
}

template< class F, template<class...>class Ptr, class X,
          class R = typename std::result_of<F(X)>::type >
Ptr<R> fmap( F&& f, const Ptr<X>& p )
{
    return p != nullptr
        ? Ptr<R>( new R( std::forward<F>(f)(*p) ) )
        : nullptr;
}

A C++03 or TR1 programmer might first think to use std::enable_if and invent some solution that deduces to std::true_type on sequences and std::false_type on non-sequences; and ditto for pointers. This works, but we also want fmap to work on functions.

template< class F, class G, class C = Composition<F,G> >
C fmap( F f, G g ) {
    C( std::move(f), std::move(g) );
}

The std::enable_if for this would have to check that G is not a sequence nor a pointer. If one added another definition of fmap, the general case would again have to check for this. So I will not go over this solution.

A partial solution is to use decltype, which can be used as an std::enable_if at times.

template< class F, template<class...>class S, class X,
          class R = typename std::result_of<F(X)>::type >
auto fmap( F&& f, const S<X>& s )
    // Enable if std::begin(s) is defined.
    -> decltype( std::begin(s), std::declval<S<R>>() )
{
    S<R> r;
    std::transform( std::begin(s), std::end(s),
                    std::back_inserter(r),
                    std::forward<F>(f) );
    return r;
}

template< class F, template<class...>class Ptr, class X,
          class R = typename std::result_of<F(X)>::type >
Ptr<R> fmap( F&& f, const Ptr<X>& p )
    // Enable if p can be checked for null and dereferenced.
    -> decltype( *p, p==nullptr, std::declval<Ptr<R>>() )
{
    return p != nullptr
        ? Ptr<R>( new R( std::forward<F>(f)(*p) ) )
        : nullptr;
}


The problem still remains with the base case, composition. For that, even with decltype, one would have to fall back on disabling it for sequences and pointers, and any further types you specialize.


Tag Dispatch

Before std::enable_if, there was tag dispatch. The idea was you start with your tags.

struct sequence_tag {};
struct pointer_tag {};
struct other_tag {};

And then you define a traits class that defines the category of that type as a tag.

template< class X > struct fmap_traits {
    typedef other_tag category;
};

template< class X > struct fmap_traits< std::vector<X> > {
    typedef sequence_tag category;
};

template< class X > struct fmap_traits< std::unique_ptr<X> > {
    typedef pointer_tag category;
};

Now, rather than specializing fmap, we specialize fmap_impl which takes an extra argument, the category

template< class F, template<class...>class S, class X,
          class R = typename std::result_of<F(X)>::type >
S<R> fmap_impl( F&& f, const S<X>& s, sequence_tag ) {
    S<R> r;
    std::transform (
        std::begin(s), std::end(s),
        std::back_inserter(r),
        std::forward<F>(f)
    );
    return r;
}

template< class F, template<class...>class Ptr, class X,
    class R = typename std::result_of<F(X)>::type >
Ptr<R> fmap_impl( F&& f, const Ptr<X>& p, pointer_tag )
{
    return p != nullptr
        ? Ptr<R>( new R( std::forward<F>(f)(*p) ) )
        : nullptr;
}

The job of fmap is now to dispatch to the appropriate fmap_impl.

template< class F, class Functor,
          class C = typename fmap_traits<Functor<X>>::category >
auto fmap( F&& f, const Functor& fnct )
    -> decltype( fmap_impl( std::declval<F>(), fnct, C() ) );
{
    return fmap_impl( std::forward<F>(f), fnct, C() );
}

This technique originally allowed STL algorithms to choose the most efficient implementation based on whether an iterator supported random access (it+n) or whether it allowed for assignment (it2=it1) or not. The only problem is that we have to specialized fmap_traits for every single type on top of fmap_impl for each tag, though this is significantly less difficult than specializing fmap_impl for every type. Still, we can do better.


Type class dispatch.

First, instead of writing an fmap_traits class, we can use the decltype trick above to overload a function, category, that returns the correct tag, and just echos the type otherwise. We don't need to actually define it; a declaration will do.

struct sequence_tag {};
struct pointer_tag {};

template< class X >
X category( ... );

template< class S >
auto category( const S& s ) -> decltype( std::begin(s), sequence_tag() );

template< class Ptr >
auto category( const Ptr& p ) -> decltype( *p, p==nullptr, pointer_tag() );

Notice that if we supply category and int, it'll return an int, but if we give it a function pointer, it'll return pointer_tag! Why is that? Well, a function pointer is a pointer! You can dereference it and test it against null, so for this to work we have to add one extra layer of specialization.

template< class T > struct Category {
    using type = decltype( category<T>(std::declval<T>()) );
};

template< class R, class ... X > struct Category< R(&)(X...) > {
    using type = R(&)(X...);
};

template< class T >
using Cat = typename Category<T>::type;

category called on a function might return pointer_tag, but Cat<F>::type will be F.

Finally, instead of writing fmap_impl we will make a class called Functor that will implement fmap as a static member function. All we are doing is moving fmap_impl to Functor::fmap. fmap will then just call Functor::fmap.

template< class... > struct Functor;

template< class F, class FX, class Fun=Functor< Cat<FX> > >
auto fmap( F&& f, FX&& fx )
    -> decltype( Fun::fmap( std::declval<F>(), std::declval<FX>() ) )
{
    return Fun::fmap( std::forward<F>(f), std::forward<FX>(fx) );
}

// General case: composition
template< class Function > struct Functor<Function> {
    template< class F, class G, class C = Composition<F,G> >
    static C fmap( F f, G g ) {
        C( std::move(f), std::move(g) );
    }
};

template<> struct Functor< sequence_tag > {
    template< class F, template<class...>class S, class X,
              class R = typename std::result_of<F(X)>::type >
    static S<R> fmap( F&& f, const S<X>& s ) {
        S<R> r;
        std::transform( std::begin(s), std::end(s),
                        std::back_inserter(r),
                        std::forward<F>(f) );
        return r;
    }
};

emplate<> struct Functor< pointer_tag > {
    template< class F, template<class...>class Ptr, class X,
              class R = typename std::result_of<F(X)>::type >
    static Ptr<R> fmap( F&& f, const Ptr<X>& p )
    {
        return p != nullptr
            ? Ptr<R>( new R( std::forward<F>(f)(*p) ) )
            : nullptr;
    }
};

struct UserDefined { /* ... */ };
template<> struct Functor< UserDefined > {
    /* ... */
};

int main() {
    auto neg = [](int x){return -x;};
    std::unique_ptr<int> p( new int(5) );
    p = fmap( neg, fmap( neg, p ) );
    std::cout << "-5 = " << *p << std::endl;

    std::vector<int> w = { 1, 2, 3 };
    w = fmap( neg, w );
    std::copy( std::begin(w), std::end(w),
               std::ostream_iterator<int>(std::cout," ") );
    std::cout << std::endl;
}

It is very important that Functor<T>::fmap is static, or this will not work. One advantage is that we can still further specialize fmap for different types. For example, we can't call our fmap on an std::array since it has no member function push_back(). Instead, we can specialize fmap for std::array inside Functor<sequence>. A Functor specialization can overload as many or as few versions of fmap as it pleases.

At last, we not only have an fmap that works generically on STL containers, and all smart pointers, we have a technique that brings a different kind of polymorphism to C++. One that allows us to add specializations without modifying the previous ones. It's also surprisingly similar to the Haskell definition of Functor.

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

This is as if we had declared fmap like so:


template< class F, template<class...>class Fnct, class X,
          class R = typename std::result_of<F(X)>,
          class Fun=Functor< Cat<Fnct<X>> > >
Fnct<R> fmap( F&& f, const Fnct<X>& fx ) {
    return Fun::fmap( std::forward<F>(f), fx );
}



This is slightly less generic, however. A given fmap implementation might decide not to return a Fnct<R>. But just like how we instantiate template specializations, Haskellers create fmap instances, too!

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

Our Functor<pointer_tag> is defined quite similarly to this! This form of specialization works equally well for other Haskell type classes like Monad (next article), Monoid, Applicative, Alternative, you name it! 


The complete final source code for this article can be found here: https://gist.github.com/3960343
Learn more about type classes: http://en.wikipedia.org/wiki/Type_class
Take a tour of some of Haskell's type classes: http://www.haskell.org/haskellwiki/Typeclassopedia

I've been using the same reference for tag dispatch for five years: http://www.generic-programming.org/languages/cpp/techniques.php

Thursday, October 25, 2012

fmap in C++ (Part 1)

Note: What fallows is not what I would call a "correct" or complete implementation of fmap in C++. It's only the start. This article is intended to be introductory to those unfamiliar with Haskell and inspirational for those who are (though you may prefer to skim). If you already have an idea of what fmap would look like in C++, skip to the next post.

fmap is an incredibly simple and useful part of Haskell, but it doesn't exist in C++. To explain it simply, you have some function, f, and some value, x, and you want the value f(x), but there's one problem: x is hidden from view! It has been trapped in a Functor, F(x).

What might this monster, this Functor, which hides the values of things be? In C++, maybe an std::unique_ptr, or an std::vector, or even an std::pair. fmap is a function that takes f and F(x) and somehow applies x to f. But wait: if F is an std::unique_ptr, then x=*ptr. If F is an std::vector, then x is the value of every element of it. Pairs have two values!

What does fmap return? F(f(x)), of coarse! More concretely, if you give fmap an std::unique_ptr, you get one back. If you throw in an std::vector, you get one back. But if you give it a vector of std::string's and f takes an std::string and produces an int (like if f=std::string::size), then fmap(f,strVec) would return a vector of lengths.

So how does fmap extract the values and construct the return? Let's take a step back and consider how fmap should work with specific types.

fmap on std::unique_ptr:

Let's start with the assertion that fmap( f, p ) = f(*p), but also we know that if p==nullptr that this operation isn't safe. As I have written previously, a pointer in C++ seems similar to a Maybe value in Haskell; Haskell defines fmap on Nothing values as returning Nothing, which is similar to nullptr, so we will say that fmap( f, p ) returns either f(*p) or nullptr.

template< class F, class X, 
          class R = typename std::result_of<F(X)>::type,
          class U = std::unique_ptr<R> >
U fmap( F&& f, const std::unique_ptr<X>& p ) 
{
    return p != nullptr 
        ? U( new R( std::forward<F>(f)(*p) ) )
        : nullptr;
}

int main() {
    std::unique_ptr<int> p( new int(5) );
    auto q = fmap( [](int x){return -x;}, p );
    std::cout << "-5 = " << *q << std::endl;
}


Creating a new std::unique_ptr may not be necessary if p is an rvalue and f(x) returns the same type p holds, but that is too detailed a discussion to have here. The same optimization could apply to many fmap specializations. 

fmap on std::vector.

This was that scary case where the x from F(x) is actually many values, but f only takes one and returns one. fmap here will take every value from the vector and return a new vector. Mathematically, we could say:

    If w = fmap(f,v), wi = f( vi ) 
        -- If w equals fmap(f,v), the I'th w equals f of the I'th v.

If that doesn't make sense, don't worry. Ignore it. It's nothing new. In Haskell or even Python, this would be equivalent to map. In C++, this is actually equivalent to std::transform.

template< class F, class X,
          class R = typename std::result_of<F(X)>::type,
          class V = std::vector<R> >
V fmap( F&& f, const std::vector<X>& v ) {
    V r;
    r.reserve( v.size() );
    std::transform( std::begin(v), std::end(v),
                    std::back_inserter(r),
                    std::forward<F>(f) );
    return r;
}

int main() {
    std::vector<int> v = { 1, 2, 3 };
    auto w = fmap( [](int x){return -x;}, v );
    std::copy( std::begin(w), std::end(w),
               std::ostream_iterator<int>(std::cout," ") );
    std::cout << std::endl;
}


One might expect fmap to work the same way on other types like std::list, but how to write a more generic is discussed in the next article.

fmap and threads?

I won't go over any code about multi-threading in C++ since I do nill-to-none of it, regularly, but I still want to go over a few plausible uses. One might think to implement fmap of an std::thread, but this doesn't make sense since applying a function to a thread is what the constructor does! 

What about an std::future? The obvious way to apply f to a future, fu, is f( fu.get() ), but this doesn't return an std::future, does it? Perhaps:


// Pseudo code
std::future<R> fmap( F f, const std::future<X>& fu ) {
    // Apply f to fu.get(), but do so in another thread.
    return std::async( []( F f, const std::future<X>& fu ) {
        return f( fu.get() );
    });
}



This is similar to a continuation (do fu, then do f). It's basically function composition for futures. The new thread waits for the value, then applies f. One then waits on the future of that.


fmap on whatever you like!

So let's say we have this really annoying friend, that always blurts out everything s/he picks up.

template< class X > struct LoudMouth { X x; };

Looks harmless?


template< class F, class X,
          class R = typename std::result_of<F(X)>::type,
          class L = LoudMouth<R> >
L fmap( F&& f, const LoudMouth<X>& v ) {
    L r = { std::forward<F>(f)(v.x) };
    std::cout << "I got a " << r.x << '!' << std::endl;
    return r;
}

int main() {
    fmap( [](int x){return -x;}, LoudMouth<int>{5} );
}



Just a silly example, but the point is that the limit is our imagination. fmap applies f to F(x), no matter how x is retrieved or where it goes . Any time you have a type, F, that you want to modify by a function, fmap is a generic way to do so. Any time you have a function, but don't know what containers might supply its value(s), fmap may be applicable. But also, just any time you have a type and have a general way of applying a function to it, you can use this.

For example, std::valarray has a member called apply(), which applies whatever function you supply to its elements. What if std::vector had such a function? There might be no need for std::transform! But if every single type had apply() in it, then there would be no reason for fmap. By externally defining operations like std::transform and fmap, we end up doing less work. If apply() were a member of every STL container, there would be many implementations of apply(). Instead there is one std::transform.

So there should only be one fmap, right? Let's say that we wrote one generic fmap that worked an any STL-like container.


template< class F, template<class...>class S, class X,
          class R = typename std::result_of<F(X)>::type >
S<R> fmap( F&& f, const S<X>& s ) {
    S<R> r;
    std::transform( std::begin(s), std::end(s),
                    std::back_inserter(r),
                    std::forward<F>(f) );
    return r;
}



This actually does work. Now, what about all STL smart pointers?


template< class F, template<class...>class Ptr, class X,
          class R = typename std::result_of<F(X)>::type >
Ptr<R> fmap( F&& f, const Ptr<X>& p )
{
    return p != nullptr
        ? Ptr<R>( new R( std::forward<F>(f)(*p) ) )
        : nullptr;
}

Oops, it won't compile anymore! This type of template specialization is a trick you can only do once.

What have we gained so far?

The real power of fmap can't be captured by the code examples above because they are not general enough. fmap should be more general than any function currently in C++. Still, we do have a good start. One could get away with specializing just for the types one needs and be all the happier.

In some cases, we have the eradication of code duplication. For example, when dereferencing a pointer, one should generally check that it isn't null first. So if we had to write

std::uniqie_ptr<int> p;
...
if( p ) {
    auto x = f(*p);
    return g(x);
}
We could instead write:

std::unique_ptr<int> p;
...
return fmap( g, fmap(f,p) );
Although, this might be slightly less efficient, for this simple example it would be absolutely trivial.

We also have cases where fmap is just syntactically nicer. It is, for example, more terse than std::transform.

Mostly, we have a very clean and simple interface for expressing the application of just some generic function on something we call a Functor. A class of types, kinda; or a category. Casually, one could say a Functor is any type that can be used as an argument to fmap

The one thing I haven't gone over is fmap on functions themselves! fmap(f,f)? Well actually, I have. Haskell defines fmap on functions as the composition of two functions. 

template< class F, class G, class C = Composition<F,G> >
C fmap( F f, G g ) {

    C( std::move(f), std::move(g) );

}

I think this post has gone on quite long enough! In the next post, I will to do a follow up on how to write a much more generic and extensible fmap. I'll be discussing the technique I used in writing Pure. It was mentioned recently by Scott Meyers in a talk, so the curious can watch that and not gain anything from reading any further.