*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

*future*s. 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.
You may be interested in taking a look at the following:

ReplyDeletehttp://fpcomplete.com/the-functor-pattern-in-c/

http://fpcomplete.com/functional-patterns-in-c/

I am well aware of fpcomplete, but thanks for the link. "The Functor Patter in C++" actually ends where my next article begins! (Generalizing fmap as a type class.)

DeleteGreat, sounds interesting!

Deletebest post related to fmap I've seen

ReplyDelete