Highlights from the current ISO proposals.

I thought I'd take some time to highlight some of the interesting proposals I read today after having stumbled on a link to them:

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/#mailing2012-11

I've been waiting over four years for Concepts to become standard. It started to feel like Stroustrup had given up on the idea, but luckily N3351 (pdf) by him and Sutton shows there has been progress. It's not honestly the most fascinating read, but when concepts are finally approved, they will improve on tag dispatch. Since a lot of my code currently uses this technique, I look forward to being able to replace it.

Really, really looking forward to it. We are forced to invent such witty ways of expressing generic functions with enable_ifs and partial template specialization, delayed instantiation, but we could just define some abstract principles about types and use those, abondoning all of it. (I do want to point out that ConceptGCC and ConceptClang do exist.)

N3418 (pdf) talks about polymorphic lambdas and N3386 talks about using auto as the return type for regular functions. The latter contains this line, which I think says it all:

    "template <class T> auto g(T t) { return t; } // return type is deduced at instantiation time"

N3328 talks about "Resumable Functions" (continuations) and introduces a few new keywords to facilitate the tricky syntax.

The Boost::option library is attempting to get in via N3406. The idea of Boost's option is very like that of Maybe in Haskell.

N3449 proposes a "Open and Efficient Type-Switch". Since this is a really foreign concept to C++, it'll be interesting to see what comes of it.

N3404 and N3505, both by a Mike Spertus, show some impressive "tidbits" with tuples and templates. The latter especially spoke to me; he shows an example of a templateted type, Foo, holding a function, F, and the example includes this:

    Foo<???>( []{ ... } )

What's the type of F? Lambdas have implementation-defined types, so we just don't know. He argues that the compiler can deduce the type here. We should be able to write Foo([]{...})!

I'd like to extend this idea. If I wrote a function g(f,x)=f(x,x), then I'd like g(Foo,x) to equal Foo(x,x) and g(std::pair,x)=std::pair(x,x). As it is, I end up writing a function that constructs a Foo and call it foo.

Unpacking tuples into functions (i.e. apply(f,tuple(1,2,3))=f(1,2,3)) has had some interesting discussion over the past few months. Solutions currently include constructing a variadic type of indexes and std::get. N3326 asks why not do something much more general? I really don't want to do it injustice by trying to explain. It's a great read!


There is plenty more I'm not mentioning: parallel programming, filesystem library, reflection, URI's, std::range, and modules. The proposals of today seem very different than the proposals of when I started programming. C++ feels like a language with a much stronger foundation, which lends itself to expansion, inspiration, and innovation. What will this round of standardization bring?

Understanding Monads

Monads can be a stumbling block, even for Haskell programmers. While I have gotten little feedback that people need help in understanding, I thought it unlikely they didn't. I thought I would suppose that a lot of people didn't get it and post some resources to help out.

The easiest way to learn is probably to pick up Haskell. It's a weird language, but if you can read LISP, you'll recognize is as syntactically similar, but without everything being in polish prefix notation. Learn You a Haskell helped me get a good start earlier this year.

Learning a new language to grasp monads isn't quite necessary. The difficulty is that very little has been written in this direction in C++. There's FC++ which has been around for at least over a decade. Also, FACT!. And finally, my own library (from which most of these articles come). Unfortunately, there does not seem to have been much interest in functional programming in general in C++. fpcomplete has several articles definitely worth mentioning, such as the one on the continuation monad and a three-part video on the functor pattern.

The easiest way to learn monads is exposure, practice, and experience, which builds an intuition about how and why they work. This is difficult in a language where so few examples exist. In other languages, we have the wonderfully written introduction in Javascript (I don't know Javascript, but I found it very easy to understand.) and You Could Have Invented Monads.

It's also a really good idea to study the foundations. Category theory (wiki) is not about Haskell or monads in particular; it's a highly programming-relevant field of mathematics. Monads (wiki) are mathematical concept within category theory. (See also Category Theory for Computer Scientists (pdf))

I do not expect one to read through each link since that might take weeks! But different people learn different ways, so one source may be more helpful than another. Good luck!

The Election Monad

 auto fourMoreYears = std::make_pair(Obama(),Romney()) >>= americanElection;

Rethinking std::binary_function.

Update: I have expanded on this concept: http://yapb-soc.blogspot.com/2012/11/generic-function-objects-or.html

Before the word "lambda" could be found in almost any C++ coder's vocabulary, the standardizing committee had stuffed <functional> with a bunch of operator functions (plus, minus, equal_to, etc), and they were very helpful. But everything else from C++03 in that file became deprecated in C++11. Things like bind1st, pointer_to_unary_function, mem_fun (not mem_fn), etc.. Even std::unary_function and std::binary_function are now deprecated.

They used to be helpful because they defined typedefs like result_type and argument_type. When you wrote a function object, you could inherit from unary_ or binary_function and get these typedefs for free. Now that we have std::result_of and decltype to do the same thing so these aren't helpful any more; but we can also do more with functions than in the past. We can partially apply them without knowing what arguments or return types the functions will give until we call them. We can also create variadic versions. We can combine, compose, and build them from other functions.

The core idea of having your function objects inherit from a base type that offers extended functionality isn't a bad idea.

Rethinking std::binary_function.

What can we do with a binary function, f(x,y)? We can partially apply them (g(y) = f(x,y)) or chain them arbitrarily (g(x,y,z) = f(f(x,y),z)). So let's do that! To implement it, I'll use the curiously recurring template pattern.

template< class Derr > struct Binary {
    // One argument: curry.
    template< class X >
    constexpr auto operator () ( X x ) -> PartialApplication<Derr,X> {
        return closet( Derr(), std::move(x) );
    }

    template< class X, class Y >
    using Result = typename std::result_of< Derr(X,Y) >::type;

    // Three arguments: unroll.
    template< class X, class Y, class Z >
    constexpr auto operator () ( X&& x, Y&& y, Z&& z ) 
        -> Result<Result<X,Y>,Z> 
    {
        return Derr()( 
            Derr()( std::forward<X>(x), std::forward<Y>(y) ), 
            std::forward<Z>(z)
        );
    }

    template< class X, class Y, class ...Z >
    using Unroll = typename std::result_of <
        Binary<Derr>( Result<X,Y>, Z... )
    >::type;

    // Any more? recurse.
    template< class X, class Y, class Z, class H, class ...J >
    constexpr auto operator () ( X&& x, Y&& y, Z&& z, H&& h, J&& ...j ) 
        -> Unroll<X,Y,Z,H,J...> 
    {
        // Notice how (*this) always gets applied at LEAST three arguments.
        return (*this)( 
            Derr()( std::forward<X>(x), std::forward<Y>(y) ), 
            std::forward<Z>(z), std::forward<H>(h), std::forward<J>(j)... 
        );
    }
};

constexpr struct Add : public Binary<Add> {
    using Binary::operator();

    template< class X, class Y >
    constexpr auto operator () ( X&& x, Y&& y ) 
        -> decltype( std::declval<X>() + std::declval<Y>() )
    {
        return std::forward<X>(x) + std::forward<Y>(y);
    }
} add{};

Note that Add must include the line using Binary::operator() for it to inherit Binary's overloads.

Now, we can create a partially applied addition

    constexpr auto plusTwo = add(2);
    constexpr auto five = plusTwo(3);

And we can string arbitrarily long additions in one function.

    constexpr int sum = add(1,2,3,4,5); 
    std::string helloWorld = add( std::string("Hello"), ' ', "world!" );

Note how for helloWorld's add, the first argument is a string, the second a char, the third a char*. The most sensible way to do this with the standard plus would be to instantiate it as an std::plus<std::string>, which would require converting the char and char* to a string before calling. Luckily, in the future, we may be able to use the syntax std::plus<> (N3421), and its behaviour would allow for mixed-type arguments, but not currying or chaining.

Moving on, we can define Subtract, Multiply, and all of the other binary <functional> types in this way. It might not be useful for all functions. For example, if you wrote a function, find(x,xs), taking a value and a sequence and returning an iterator, then it might not be helpful to chain. find(x,xs,ys) would check ys for the iterator of the item found in xs, which is probably not what we want. But find(x) would return a function that looks for x in any container and that could easily be desirable behaviour.

A note on efficiency.

I am a big fan of constexpr. There is no optimization greater than skipping the whole computation and inlining the result. So when I checked out the assembly generated for the line,

    std::cout << add(1,2,3,4,5) << std::endl;

imagine my surprise when I found out GCC had neither computed the result at compile time nor inlined the call to add! However, when I made the following change:

    constexpr int x = add(1,2,3,4,5);
    std::cout << x << std::endl;

it basically converted it to

    std::cout << 15 << std::endl;

This is very exciting technology, but perhaps too new to work perfectly.  I expect GCC, and compilers in general, to improve over time, but for the moment, they can be fickle. Subtle changes in the code can cause drastic changes in the assembly.

Could we go further?

There are other operations that might make sense on binary function; their arguments can be swapped (or flipped), one could apply only the second argument, and we could find interesting ways of composing them. As always, the limit is our imagination. I think this is a good start. Features that extend beyond overloading () require the calling code to "know" that its function object is a Binary, and so it's less generally useful. Why write a member named Binary::flip() when one could write a function called flip that worked on function pointers, too?

Are there operations on unary functions that might make sense? What about ternary functions?

The lesson here isn't so much that one thing should be a feature over another, but when defining function objects, do not forget about using inheritance to limit code duplication!


The source: https://gist.github.com/4024658
(Oops, I forgot to post it this time!)

Monadic IO in C++

Previously, I covered Functors (fmap), and Monads (mbind, mreturn), and today, IO. Whether or not monadic IO is desirable in C++, I cannot say. But it represents a significantly more difficult monad to conceptualize and implement, and many of Haskell's monads are similar (StateT, Reader, etc.), so if nothing else, this is good practice. It's also good practice for implementing contiuations.

I neglected (by mistake) to discuss Monads in full, mainly do and fail. In Haskell, fail takes a string, some error message, and returns a failure which, for a pointer, might be null, for a sequence, an empty one. More useful today will be do. Since this should have been in the Monads article, I will explain that first, and then how it's relevant to IO.

do simply takes two monads and returns the second. It's symbolically noted >> like bind's >>=. If integers were monads, 1 >> 2 would equal 2. For pointers p and q, p >> q would equal q, but only if p. By that, I mean if p = null, then p >> q = null. If q is null, then p >> q is null regardless. For sequences, Haskell defines s >> t as t appended to itself for every element of s.

    [a,b] >> [x,y] = [x,y,x,y]
    [a] >> [x,y] = [x,y]
    [] >> [x,y] = []

It should be fairly intuitive how to write this, so I will continue to IO.

IO<X>

So far, we have always made a few implicit assumption about monads. They hold a value and exactly the type in the angle-brackets. In a functional sense, input is a mechanism that somehow produces a value, but it comes out of thin air from some unseen external force. Output is a device that makes seen values disappear. An IO is either a value-producing machine, or a value-taking one. So an IO monad is a function! A function with IO decoration, that is. 

What does an IO<int> contain? It must contain a function that produces an int! IO<void>? A function that outputs some value. But since it's actually a function, wouldn't it be more like IO<int(*)()>? Or IO<MyFuncType>? Well, the IO monad can be implemented with std::function, and that allows us to keep our assertions about monadic types, as you will soon see.

So Monads aren't just containers. One might have heard they are also computations. That's just an obfuscated way of saying they're functions.

Hello World

Let's first define IO<X> as an object holding an std::function.

template< class X > struct IO {
    using function = std::function<X()>;
    function f;

    template< class F >
    IO( F&& f ) : f(std::forward<F>(f)) { }

    X operator () () const {
        return f();
    }
};

template< class F, class R = typename std::result_of<F()>::type >
IO<R> io( F f ) {
    return IO<R>( std::move(f) );
}

And now, a few examples:

IO<int> readInt = io( []{ int x; std::cin >> x; return x; } );
IO<std::string> readStr = io( []{ std::string s; std::cin >> s; return s; } );
IO<int> constant = io( []{ return 5; } );

And that's input. We'll have to specialize IO for output.

template< > struct IO<void> {
    using function = std::function<void()>;
    function f;

    IO( function f ) : f(std::move(f)) { }

    void operator () () const {
        f();
    }
};

IO<void> hello = io( []{ std::cout << "Hello world." << std::endl; } );
IO<void> doNothing = io( []{} );

Now, let's try and imagine some operation on IO.

IO<void> hello2 = hello >> hello

do is a lot like bind, except that it does not pass the result of the previous expression to the next. When we do two IO monads, we get a third back. No IO has yet been executed. hello2 is the function that actually executes the IO.

I wanted to go over IO<X> because it is easier to reason about than IO<F>, and much more Haskell-like. However, C++ is about zero-overhead abstractions and this ends up being less efficient because of the tricks std::function uses in order to work. To see the std::function implementation, check out the gist.

IO<F>

This version is initially much simpler to implement.

template< class F > struct IO {
    using function = F;
    F f;

    constexpr IO( function f ) : f(std::move(f)) { }

    constexpr decltype(f()) operator () () {
        return f();
    }
};

template< class F, class _F = typename std::decay<F>::type >
constexpr IO<_F> io( F&& f ) {
    return std::forward<F>(f);
}

But now what should the type of hello2 be? Well, it'll basically be executing hello, twice, so it's a sort of composition, but with two void functions. Let's define a type to represent this composition: Incidence.

template< class F, class G > struct Incidence {
    F a;
    G b;

    constexpr Incidence( F a, G b )
        : a(std::move(a)), b(std::move(b))
    {
    }&;

    // Execute a and b coincidentally.
    auto operator () () const 
        -> typename std::result_of<G()>::type
    {
        a();
        return b();
    }
};

template< class F, class G, class I = Incidence<F,G> >
constexpr I incidence( F f, G g ) {
    return I( std::move(f), std::move(g) );
}

What will mreturn do? An IO is just a function, so it'll take some x and make a function that just returns x. To do this, we'll define another type, Identity.

template< class X > struct Identity {
    using value_type = X;
    value_type x;

    template< class Y >
    Identity( Y&& y ) : x( std::forward<Y>(y) ) { }

    constexpr value_type operator () () { return x; }
};

template< class X, class D = typename std::decay<X>::type >
Identity<D> identity( X&& x ) {
    return Identity<D>( std::forward<X>(x) );
}

It may make more sense to have Identity return a reference or const reference to x, but since we are dealing strictly with values, this would complicate things. Any decltype or result_of involving an Identity would have to remove the reference.

Now we can write things like:

    auto getFive = mreturn<IO>( 5 );
    int five = getFive();

and all is good. Next is mbind.

    auto someIO = readInt >>= []( int x ) { return mreturn<IO>(x + 5); }

Here, we have our IO called readInt which gets an int from std::cin. It passes the int to our lambda, which adds 5 and returns a new IO. No integer has been read from std::cin yet, nor the five added; we have merely composed readInt with our continuation to create a new function, a new IO.

This part might be a little mind boggling. Let's say we call someIO; what happens? We know it'll return an int with 5 added to it. It starts by calling readInt. Then the number gets passed to our lambda. It adds five and returns a new IO<Identity<int>>. If we stopped here, we wouldn't have our value, so we then execute the Identity IO. We'll implement DoubleCall to express the pattern of constructing the IO with the first call and running it with the second. We'll also expand Incidence to handle the case where it needs to pass the value (from readInt) to the continuation.

template< class T, class R >
using EVoid = typename std::enable_if< std::is_void<T>::value, R >::type;
template< class T, class R >
using XVoid = typename std::enable_if< !std::is_void<T>::value, R >::type;

// Incidental.
template< class F, class G, class R = typename std::result_of<F()>::type >
constexpr auto incidentallyDo( F&& f, G&& g ) 
    -> XVoid <
        R,
        decltype( std::declval<G>()( std::declval<F>()() ) )
    >
{
    return std::forward<G>(g)( std::forward<F>(f)() );
}

// Co-incidental.
template< class F, class G, class R = typename std::result_of<F()>::type >
constexpr auto incidentallyDo( F&& f, G&& g ) 
    -> EVoid <
        R,
        decltype( std::declval<G>()() )
    >
{
    std::forward<F>(f)();
    return std::forward<G>(g)();
}

// Either an incidence or coincidence.
template< class F, class G > struct Incidence {
    F a;
    G b;

    constexpr Incidence( F a, G b )
        : a(std::move(a)), b(std::move(b))
    {
    }

    using R = decltype( incidentallyDo(a,b) );

    constexpr R operator () () {
        return incidentallyDo( a, b );
    }
};

template< class F, class G, class I = Incidence<F,G> >
constexpr I incidence( F f, G g ) {
    return I( std::move(f), std::move(g) );
}

template< class F > struct DoubleCall {
    F f;

    using F2 = typename std::result_of<F()>::type;
    using result_type = typename std::result_of<F2()>::type;

    constexpr result_type operator () () {
        return f()();
    }
};

template< class F >
constexpr DoubleCall<F> doubleCall( F f ) {
    return { std::move(f) };
}

We may now implement Functor<IO> and Monad<IO> totally in terms of Identity, Incidence, and DoubleCall.

template< class _ > struct Functor< IO<_> > {
    template< class F, class G, class I = Incidence<F,G> >
    constexpr static IO<I> fmap( F f, IO<G> r ) {
        return I( std::move(f), std::move(r.f) );
    }
};

template< class _ > struct Monad< IO<_> > {
    template< class F, class G, 
        class R = typename std::result_of<G()>::type >
    static constexpr auto mbind( F f, IO<G> m ) 
        -> IO< DoubleCall< Incidence<G,F> > >
    {
        // f returns a new IO, so doubleCall the incidence to execute it!
        return doubleCall (
            incidence( std::move(m.f), std::move(f) )
        );
    }

    template< class F, class G >
    static constexpr IO<Incidence<F,G>> mdo( IO<F> f, IO<G> g ) {
        return incidence( std::move(f.f), std::move(g.f) );
    }

    template< class __, class X, class D = typename std::decay<X>::type >
    static constexpr IO<Identity<D>> mreturn( X&& x ) {
        return Identity<D>( std::forward<X>(x) );
    }

    template< class _IO >
    static _IO mfail() {
        return _IO( []{ } );
    }
};

Now, we can string along arbitrary operations in whatever way we'd like, but a sane person might realize that if one lambda reads in an int and another prints it, then we've really just obfuscated this process because we could otherwise we could just do that ourselves. Like any other useful thing, IO requires other useful things to make it useful.

The tools

First, input. We could write a function that read an int and returned it and it would look something like this:

    int readInt() { int x; std::cin >> x; return x; }

Or, we can template read to work on any type. Even better, we can make read a type!

template< class T >
struct ReadT {
    T operator () () const {
        T x;
        std::cin >> x;
        return x;
    }
};

template< class T >
constexpr IO< ReadT<T> > readT() {
    return ReadT<T>();
}

We can read; can we write? Since an IO takes no arguments, anything we want to write has to be held within the IO object. First, we just need some generic functions.

constexpr struct Print {
    template< class X >
    void operator () ( const X& x ) const {
        std::cout << x;
    }
} print{};

template< class X >
static std::string show( const X& x ) {
    static std::ostringstream oss;
    oss.str( "" );
    oss << x;
    return oss.str();
}

static std::string show( std::string str ) {
    return str;
}

static constexpr const char* show( const char* str ) {
    return str;
}

template< class X, class Y, class ...Z >
static std::string show( const X& x, const Y& y, const Z& ...z )
{
    return show(x) + show(y,z...);
}

Now, we want to turn a show/Print combo into an IO. I'll be borrowing my code from "Partial Application in C++" for this.

constexpr struct Echo {
    using F = PartialApplication< Print, std::string >;
    using result_type = IO<F>;

    template< class ...X >
    result_type operator () ( const X& ...x ) const {
        // We don't know if x will still be around when the IO executes, so
        // convert to a string right away!
        return closet( print, show(x...) );
    }
} echo{};

auto newline = io( []{ std::cout << std::endl; } );

We can now write rudimentary IO programs like

    echo("Give me an int!\n") >> (readT<int>() >>= echo) >> newline

Which will, if you've been following along, echo "Give me an int!" to the screen, read one from std::cin, and echo the int back out.

Complications

Remember addM?

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

    );
}

For IO, this should read in two ints and add them, but it won't work since IO<F> >>= []{...} =/= IO<F>! We could wrap the function in a decltype, but not while using lambdas. The challenge is to rewrite this function without lambdas.Looking at the lambda, it takes only one argument, but also captures b. We can replace it with a function that takes f, b, and x. x has to be the last argument because we're going to partially apply f and b, making it a function of x.

template< class M > struct _AddM {
    constexpr auto operator () ( int x, int y ) -> decltype( mreturn<M>(1) )
    {
        return mreturn<M>( x + y );
    }
};

constexpr struct BindCloset {
    template< class F, class X, class M >
    constexpr auto operator () ( F&& f, M&& m, X&& x )
        -> decltype( std::declval<M>() >>=
                     closet(std::declval<F>(),std::declval<X>()) )
    {
        return std::forward<M>(m) >>=
            closet( std::forward<F>(f), std::forward<X>(x) );
    }
} bindCloset{};

template< class M >
constexpr auto addM( const M& a, const M& b )
    -> decltype (
        a >>= closure( bindCloset, _AddM<M>(), b )
              
    )
{
    return a >>= closure( bindCloset, _AddM<M>(), b );
}

When we bind a to the closure, x gets extracted as the last argument. The closure then partially applies x to f and extracts y from b.

The same technique can be used to implement liftM, the two-argument version, or any other function with embedded lambdas.

Conclusions

How powerful is this? We can write almost a whole program in it! Here's the main I used to test IO (using some code from the Monads article).

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

    std::vector<int> v={1,2,3}, w={3,4};

    auto readInt = readT<int>();

    auto program = echo( "Unique pairs of [1,2,3]:\n\t" )
        >> echo( uniquePairs(v) ) >> newline

        >> echo("Unique pairs of Just 5:\n\t")
        >> echo( uniquePairs(p) ) >> newline

        >> echo( "Please enter two numbers, x and y: " )
        >> (
            addM( readInt, readInt ) >>= []( int x ) {
                return echo( "x+y = ", x ) >> newline;
            }
        )

        >> echo("The quadratic root of (1,3,-4) = ")
            >> echo( qroot(1,3,-4) ) >> newline
        >> echo("The quadratic root of (1,0,4) = ")
            >> echo( qroot(1,0,4) ) >> newline;

    program();
}

The variable program is a complex data structure that contains many Incidences made of PartialApplications of Print and std::string. GCC does a very good job of optimizing it, however, if we had written this out normally (no monads), GCC would just insert each item into std::cout. Instead we're creating a structure with Prints and std::strings. GCC optimizes away the Print object and inlines much of the code, which it could not do if it were a regular function (since it would have to maintain a pointer), but it wouldn't ordinarily construct this many std::strings. There is room for optimization--this is not hopelessly inefficient, but be aware of how your objects are constructed and passed along.

Would one ever want to actually use this over vanilla IO in C++? I certainly wouldn't argue it should be prefered. Still, if one was in the situation of needing to pass along a function, this offers a simple way of composing it from simpler objects. Composition itself is a powerful tool.

At first, we may have thought of a monad or functor as a container, but IO disproves this. So monads can be containers or functions? IO is more than just a function, it's a program encoded as data, constructed at run-time. It's hard to point to one sentence that well-describes all monads, but we know they aren't one exact thing over another. It's almost anything!


As always, the source code: https://gist.github.com/3994038
IO implemented with std::function: https://gist.github.com/3994038#file_io_monad.cpp

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

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