Nerd wannabe

lazy weblog

(basic) functional programming in C++

leave a comment »

(update: simplified expression)

So I’m (re) learning C++. And would like to point out some functional language features found “out of the box” – although using boost::lambda or boost::bind you could get nicer ones, or waiting for C++0x would be another option…

This came to me while reading the wikipedia article on functional programming , which basically gives this example (in python I think):

# functional style
# FP-oriented languages often have standard compose()
compose2 = lambda F, G: lambda x: F(G(x))
target = map(compose2(F,G), source_list)

And the tag-line:

In contrast to the imperative style that describes the steps involved in building target, the functional style describes the mathematical relationship between source_list and target.

To begin, let’s have a look at an imperative version that I coded in C++:

vector<string>& imperative_version (vector<string>& source_list)
{
    vector<string> *target = new vector<string> ();
    string trans1, trans2;

    for (vector<string>::iterator item = source_list.begin ();
        item != source_list.end (); item++) {
            trans1 = G (*item);
            trans2 = F (trans1);
            target->push_back (trans2);
    }

    return *target;
}

Pretty long, isn’t it? Besides defining type for the elements of the ‘list’ (I used a vector), and allocating memory, you can see the ugliness of the iterator type and.. well.. the imperative for loop with calls to the F and G functions.What I did was that I shortened everything down to:

vector<string> target = map<string>(source_list, compose (F, G));

What this code does is to call a function named map() that receives a vector and a function, calls the function on each element of the vector and returns a new vector with the results.Exactly like in the functional programming example, the functions F and G are composed so that the actual transformation is target[i] = F(G(source[i])).Let’s look at another example:

vector<int>target_int = map<int>(source_list, compose (len, F));

So, how is this implemented? compose2 is a functor: it is actually an object that has the () operator overloaded. And here’s the class definition for it:

template <typename input_type, typename intermediate_type, typename return_type>
class compose2 {
private:
    return_type (*f)(intermediate_type);
    intermediate_type (*g) (input_type);
public:
    compose2( return_type (*F)(intermediate_type), intermediate_type (*G) (input_type))    :f(F), g(G) {}
    return_type operator() (input_type input)
    {
        return (f(g(input)));
    }
};

What it does is that it requires two functions when the constructor is called and, upon calling the () operator, evaluates them.We cannot use compose2 directly without specifying the input type for the G function, the input type of the F function and last, the return type of the F(G()) function.

But we can make the compile infer them by wrapping everything in a function template, that has the ability to better deduce the type arguments:

template <typename input_type, typename intermediate_type, typename return_type>
compose2<input_type,intermediate_type,return_type> compose (return_type (*F)(intermediate_type), intermediate_type (*G) (input_type))
{
    return compose2<input_type,intermediate_type,return_type> (F, G);
}

The compose2<>() statement is a call to the compose2’s constructor. It returns a compose2 instance ready to replace a function.

Then there’s the map() function that applies a function to a vector, using the transform() algorithm:

template <typename out_type, typename in_type, typename functype>
vector<out_type>& map (vector<in_type>& in, functype f)
{
        vector<out_type> *target = new vector<out_type> (in.size ());
        transform (in.begin (), in.end (), target->begin (), f);
        return *target;
}

The out_type has to be specified because it cannot be inferred.(tested with MSVC 2005 and g++ 3.4.5 (mingw) and g++ 4.1.5)

Next time, an example with Boost or with TR1;)

Advertisements

Written by vlad

January 31, 2008 at 4:07 pm

Posted in trivia

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: