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.