Implementing the Maybe Monad in C++.

Update: See "fmap in C++" for a wider look on functors (like Maybe).

I decided to take the day off and write this little post about implementing Haskell's Maybe in C++. Haskell is not a requirement, though I will be showing some source code, so some familiarity may help. Those who already know know it may note my code examples for fmap and >>= aren't exactly the same as Haskell's. All of the following code is completely hypothetical and overly simplifies so we can just focus on the concepts.

I have come to see a few Maybe implementations in C++ around the net, but Maybe by itself is entirely useless. It doesn't really do anything on its own. In Haskell, it exists inside an ecosystem of other functions it operates well with. Outside of Haskell, it's quite bare. Let's look at some examples of Maybe:

    x = Just 2
    y = Nothing
    z = fromJust x -- 2

    -- Defin a function, g, that returns a string.
    let g m = case m of
        Just _ -> "Has a value"
        Nothing -> "Has none."

    g x -- has a value
    g y -- has none


All very simple stuff here. Make a Maybe, extract a value. A small observation: A Maybe has a value, but also has a boolean "is" or "isn't" property to it. There's something in C and C++ that acts almost exactly like this. (Try and guess before reading on.)

The Maybe types

Pointers. "x = Just 2" in C++ would be "unique_ptr<int> x = new int(2);". A pointer either points to null (Nothing) or something (Just). A bool with a value! Now let's look at a really silly example of a Maybe implementations that ignores this similarity.

template< class X > struct Maybe {
    X x;
    bool valid;

    Maybe( const X& x ) : x(x), valid(true) { }
    Maybe() : valid(false) { }
};

template< class X > Maybe<X> Just( const X& x ) {
    return Maybe<X>(x);
}

template< class X > Maybe<X> Nothing() { return Maybe<X>(); }

...

auto a = Just(1); // Maybe<int>
auto b = Nothing<int>();

This works fine, and avoids the allocation so it's more efficient, but the problem comes when we write fromJust. We could return x if valid==true, but what when valid==false? You see, another interesting property of Maybes that this ignores: for any value, x, Just x != Nothing. If fromJust returns x with no checks, then fromJust(Just(x)) == fromJust(Nothing()), which seems to violate the above rule. The other option is to throw an exception, but i generally like to avoid that.

This is assuming X is default constructible. It may not be, or it may have an expensive initialization. The above may simply not work for some types. Simply choosing a different implementation seems most obvious to me, so let's try this:

template< class X >
using Maybe = std::unique_ptr<X>; // C++11 syntax

template< class X > Maybe<X> Just( const X& x ) {
    return Maybe<X>( new X(x) );
}

template< class X > Maybe<X> Nothing() { return Maybe<X>(nullptr); }

template< class X > const X& fromJust( const Maybe<X>& m ) {
    return *m;
}

The fromJust problem is solved, and no value Just(x) equals Nothing. fromJust on a null pointer will fail, like fromJust on a Nothing in Haskell. What's more is that we can get rid of the fromJust which makes the unsafeness of the action more obvious. I can think of at least one improvement, but this will do for now.

Motivation

So far, we have not done a single thing useful with Maybe, but Maybe in Haskell works inside an ecosystem, so let's implement a part of it.

/*
 * fmap f (Just x) = Just (f x)
 * fmap f Nothing = Nothing
 */
template< class F, class X,
    // decltype and declval are good to know if you don't already.
    class R=decltype( declval<F>()(declval<X>()) ) >
std::unique_ptr<R> fmap( const F& f, const Maybe<X>& m ) {
    return m ? Just( f(*m) ) : Nothing<R>();
}


int plus_two( int x ) { return x + 2; }
int minus_two( int x ) { return x - 2; }

...


fmap( plus_two, Just(2) ); // Just 4
fmap( minus_two, fmap(plus_two, Just(2)) ) // Just 2
fmap( minus_two, fmap(plus_two, Nothing<int>()) ) // Nothing

 When I learned of fmap, things suddenly started to make more sense. I have a Maybe Int value and want the Int part transformed through various functions to produce some arbitrary value that gets wrapped in a Maybe. I don't have to constantly check whether the value is valid or not, that happens automatically.

Where code used to look like...

void f() {
    X* x = return_some_pointer();
    if( x ) {
        Y* y = new Y(transform_value(*x));
        if( y ) {
            // do something
        }
    }
}

it can now be rewritten

void f() {
    fmap (
        [](... y){ /*do something*/ },
        fmap( transform_value, return_some_pointer() )
    );
}

Certainly more concise, although whether this reads more clearly might be a little subjective. Now that we have fmap, I want to also implement a monadic operation on Maybe values.

// Just x >>= f = f x -- where f returns a Maybe.
// Nothing >>= f = Nothing
template< class X, class F, class MR=decltype( declval<F>()(declval<X>()) ) >
MR operator>>= ( const Maybe<X>& a, const F& f ) {
    return a ? f(*a) : MR();
}

int twoOver( int x ) { return 2/x; }

Maybe<int> twoOver( int x ) { return x ? Just(2/x) : Nothing<int>(); }

...

Maybe<int> x = Just(2);
fmap( plus_two, x >>= twoOver ); // Just 3

Here, x >>= twoOver returns Just(2/2=1), then fmap applies +2 on it to get 3. We can use fmap to apply normal functions and >>= to apply Maybe-returning functions. One might think of fmap as an operation lifting functions into the Maybe category and >>= working on functions already there. (Though, nothing actually stops us from using >>= to apply non-Maybe returning functions, except the honor system ;)

Here's some code i wrote at one point for an attempt at a Webkit-based internet browser.

     WebKitWebFrame* frame        = webkit_web_view_get_main_frame( web_view );

    WebKitWebDataSource* source  = webkit_web_frame_get_data_source( frame );
    GString*             content = webkit_web_data_source_get_data( source );
  
    WebKitWebDataSource* reSource   = webkit_web_frame_get_provisional_data_source( frame );
    GString*             reContents = reSource? webkit_web_data_source_get_data( reSource ) : 0;

I could theoretically rewrite that...

    WebKitWebFrame* frame = web_view >>= webkit_web_view_get_main_frame;

    GString* content = frame >>= webkit_web_frame_get_data_source
                              >>= webkit_web_data_source_get_data;
   
    GString* reContents = webkit_web_frame_get_provisional_data_source
        >>= webkit_web_data_source_get_data;


More practical examples come from using >>= and fmap together. Haskell provides a really handy operator, <$>, that aliases as an fmap. Take a look at this line:

(+2) . read <$> getLine >>= print

This first gets the line as a string, calls read which converts it to an int, then adds 2 and calls print. The dot operator between (+2) and read represents a function composition, g(str) = plus_two(atoi(str)). That is also not difficult to implement in C++, but maybe another day.

Unfortunately, we are more limited to our expressiveness with symbolic operators in C++. We have to choose from, at least the fallowing: ^ << <<= % || && | & * / + -, which all have either mathematical or logical meaning. Whether being able to create arbitrary symbolic operators would benefit or harm C++ code is an interesting topic for debate. It can certainly be difficult to justify the use of an operator for a non-standard function because of our limited options.

Conclusions

I hope I have demonstrated at least one thing successfully here: Maybe, on its own, is useless. The truly interesting aspects of it only come out in conjunction with other functional operations. fmap and >>= make a good start, there's also >>, liftA2, ap, function composition, and a whole slue of useful tools that can be used on pointers, but also arbitrary data structures for which they make sense. One interesting thing to note is that Haskell doesn't as easily allow for functions that take a variable number of arguments, so we can do some things more generically than in Haskell. (For example, liftA could be a var-arg funcion; perhaps even fmap.)

Now, remember that I said there was one improvement on implementing Maybe to make? I use the Maybe concept in my library, Pure, and what I do differently is that I do not actually implement it! Instead, I use tag dispatching to determine if something's a Maybe type, and implement generic versions of fmap and >>= (which i call mbind). Even defining Maybe as an std::unique_ptr like above restricts fmap from working on std::shared_ptrs, and regular pointers--we have a rich variety of ways in expressing possible values in C++.


Further reading

http://www.generic-programming.org/languages/cpp/techniques.php#tag_dispatching
A good technique for template specialization.

http://members.chello.nl/hjgtuyl/tourdemonad.html
A good (short) list of important monad functions.