Computer Science Canada

[C++ tut] Functional Zen and C++
Author:  wtd [ Sat Nov 26, 2005 5:06 am ]
Post subject:  [C++ tut] Functional Zen and C++
Disclaimer: this assumes a decent knowledge of C++. In particular, understanding namespaces, objects, and operator overloding. Knowledge of templates will also come in handy.

The defining feature of functional programming languages is higher-order functions that can be passed around the way any variable can be in a procedural/imperative language. Combining this with partial function application, and function composition gives us a really unique way of applying operations to data.

For instance, let's say we have a list of integers.

In Haskell:

Haskell:
foo = [1..5]


And let's say we want to add 1 to each of these, and put the result into a new list. Well, first we need a function which adds one to an integer. Partial function application makes this a snap.

Haskell:
addOne = (1 +)


And then we can pull it together with map.

Haskell:
foo = [1..5]
bar = map addOne foo
addOne = (1 +)


And if we use literals in the call to map:

Haskell:
foo = [1..5]
bar = map (1 +) foo


That's pretty concise, isn't it?

Now, let's consider a straightforward C++ implementation that's roughly equivalent.

c++:
int main()
{
   int foo[5] = {1, 2, 3, 4, 5},
       bar[5];
       
   for (int i = 0; i < 5; ++i)
   {
      bar[i] = foo[i] + 1;
   }
   
   return 0;
}


The clumsiness here has nothing to do with the braces. It's just all of that darn "i" stuff. Can we make this look more like the Haskell code?

Yes, we can, and in the process we get to see some interesting parts of the standard template library.

First, let's cut it down to basics.

c++:
int main()
{
   int foo[5] = {1, 2, 3, 4, 5},
       bar[5];
   
   return 0;
}


Now, in the Haskell code, we needed a function that would add one to an integer. We can easily create such a function in C++.

c++:
int add_one(int a)
{
   return a + 1;
}


The + operator works on lots of different types besides integers, so we'll use templates.

c++:
template <typename T>
T add_one(T a)
{
   return a + 1;
}


But we didn't have to write out anything nearly so verbose in Haskell. We just used the existing + operator and applied one to it. This gave us a new function which adds one to its argument.

Fortunately, we can get the "plus" function via the "functional" header.

c++:
plus<int>()


Then we can bind a value to one of its arguments using the "bind1st" function.

c++:
bind1st(plus<int>(), 1)


And we get a new function... sort of. C++ doesn't have higher order functions, but it does have objects which can have an overloaded () operator, which allows them to act just like functions.

So, now we have a 1 + function (object). How can we apply it to the "foo" array, and store the result in the "bar" array? Well, that's where the transofmr function from the "algorithm" header comes in.

c++:
#include <functional>
#include <algorithm>

using namespace std;

int main()
{
   int foo[5] = {1, 2, 3, 4, 5},
       bar[5];
   
   transform(foo, foo + 5, bar,
      bind1st(plus<int>(), 1));
   
   return 0;
}


Doesn't that look nice?

And yet, we still haven't talked about function composition.

Let's say we want to multiply each number by three, then add one. Now there are two functions involved.

Let's look at the Haskell code.

Haskell:
foo = [1..5]
bar = map ((1 +) . (3 *)) foo


Here we can see two partial function applications which represent the two functions at work. Multiplying by three, and adding one.

But how can we do this in C++?

c++:
#include <functional>
#include <ext/functional>
#include <algorithm>

using namespace std;

int main()
{
   int foo[5] = {1, 2, 3, 4, 5},
       bar[5];
       
   using __gnu_cxx::compose1;
   
   transform(foo, foo + 5, bar,
      compose1(
         bind1st(plus<int>(), 1),
         bind1st(multiplies<int>(), 3)));
   
   return 0;
}


The new function here is the "compose1" function. As with Haskell's dot operator for composition, it takes two functions and turns them into a single function.

This function is not strictly part of the C++ standard but instead it's an extension to the Standard Template Library, and thus in GCC is not part of the "std" namespace. Rather it's part of the "__gnu_cxx" namespace.

Using these tools, we can roughly duplicate the elegance of functional programming in C++.

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy