Functional Programming in C++ [closed]

You can accomplish a surprising amount of "functional programming" style with modern C++. In fact, the language has been trending in that direction since its' standardization.

The standard library contains algorithms analogous to map, reduce, etc (for_each, transform, adjacent_sum...). The next revision, C++0x, contains many features designed to let programmers work with these in a more functional style (lambda expressions, etc.).

Look into the various Boost libraries for more fun. Just to illustrate that standard C++ contains plenty of functional goodness, here's a factorial function in continuation-passing style in standard C++.

#include <iostream>

// abstract base class for a continuation functor
struct continuation {
    virtual void operator() (unsigned) const = 0;
};

// accumulating continuation functor
struct accum_cont: public continuation {
    private:
        unsigned accumulator_;
        const continuation &enclosing_;
    public:
        accum_cont(unsigned accumulator, const continuation &enclosing)
            : accumulator_(accumulator), enclosing_(enclosing) {}; 
        virtual void operator() (unsigned n) const {
            enclosing_(accumulator_ * n);
        };
};

void fact_cps (unsigned n, const continuation &c)
{
    if (n == 0)
        c(1);
    else
        fact_cps(n - 1, accum_cont(n, c));
}

int main ()
{
    // continuation which displays its' argument when called
    struct disp_cont: public continuation {
        virtual void operator() (unsigned n) const {
            std::cout << n << std::endl;
        };
    } dc;

    // continuation which multiplies its' argument by 2
    // and displays it when called
    struct mult_cont: public continuation {
        virtual void operator() (unsigned n) const {
            std::cout << n * 2 << std::endl;
        };
    } mc;

    fact_cps(4, dc); // prints 24
    fact_cps(5, mc); // prints 240

    return 0;
}

Ok, I lied a little bit. It's a factorial functor. After all, closures are a poor man's objects... and vice versa. Most of the functional techniques used in C++ rely on the use of functors (i.e. function objects)---you'll see this extensively in the STL.

Update August 2014: This answer was posted in 2009. C++11 improved matters considerably for functional programming in C++, so this answer is no longer accurate. I'm leaving it below for a historical record.

Since this answer stuck as the accepted one - I'm turning it into a community Wiki. Feel free to collaboratively improve it to add real tips on function programming with modern C++.

You can not do true functional programming with C++. All you can do is approximate it with a large amount of pain and complexity (although in C++11 it's a bit easier). Therefore, this approach isn't recommended. C++ supports other programming paradigms relatively well, and IMHO should not be bent to paradigms it supports less well - in the end it will make unreadable code only the author understands.

UPD Dec 2018

I've created a comprehensive list of materials where you can find articles, talks, screencasts, papers, libraries and showcases:

Functional Programming in C++

Consider my 4 research projects:

• Functional and Declarative Design in C++. (GitHub) (Slides (Rus)) (Talk (Rus))

This project is a working prototype of 'Amber' game. The code demonstrates many of major functional concepts: immutability, lambdas, monads, combinators, pure functions, declarative code design. It uses Qt C++ and C++11 features.

For a quick example, see how tasks can be chained into one big task that will modify the Amber's world when it's applied:

const AmberTask tickOneAmberHour = [](const amber::Amber& amber)
{
    auto action1Res = magic::anyway(inflateShadowStorms, magic::wrap(amber));
    auto action2Res = magic::anyway(affectShadowStorms, action1Res);
    auto action3Res = magic::onFail(shadowStabilization, action2Res);
    auto action4Res = magic::anyway(tickWorldTime, action3Res);
    return action4Res.amber;
};

• Lenses in C++. (GitHub) (Slides (Eng)) (Talk (Rus))

This is a showcase of generic functional lenses in C++. The implementatoin is built with using of Variadic Templates, some intresting (and valid) C++ hacks to make lenses composable and neat-looking. The library is just a demo for the talk and thus it provides only a few of most important combinators, namely: set(), view(), traverse(), bind(), infix literal combinator to, over() and other.

(Note that there exist the 'C++ Lenses' project: but it's not about real 'lenses', it's about class properties with getters and setters in sense of C# or Java properties.)

Quick example

Car car1 = {"x555xx", "Ford Focus", 0, {}};
Car car2 = {"y555yy", "Toyota Corolla", 10000, {}};

std::vector<Car> cars = {car1, car2};

auto zoomer = traversed<Car>() to modelL();

std::function<std::string(std::string)> variator = [](std::string) { return std::string("BMW x6"); };
std::vector<Car> result = over(zoomer, cars, variator);

QVERIFY(result.size() == 2);
QVERIFY(result[0].model == "BMW x6");
QVERIFY(result[1].model == "BMW x6");

• Functional 'Life': parallel celullar automata and comonads. (GitHub) (Slides (Eng)) (Talk (Rus))

You have probably heard about monads. Monads are everywhere in talks about functional programming now. It's a buzzword. But what about comonads? I presented 1D and 2D celullar automata with the concept of comonads under the hood. The aim was to show how easy it is to move from the single-flow code to the parallel one using std::future as a Par monad. The project also benchmarks and compares two these approaches.

Quick example

template <typename A, typename B>
UUB fmap(
    const func<B(UUA)>& f,
    const UUUUA& uuu)
{
    const func<UB(UUUA)> f2 = [=](const UUUA& uuu2)
    {
        UB newUt;
        newUt.position = uuu2.position;
        newUt.field = fp::map(f, uuu2.field);
        return newUt;
    };

    return { fp::map(f2, uuu.field), uuu.position };
}

• Pure functional Software Transactional Memory (STM) library that is called cpp_stm_free. (GitHub) (Slides (Eng)) (Talk (Rus)) (Tutorial (Eng)) (Dining Philosopher sample).

This library is based on Free monad and some other advanced ideas of Functional Programming. Its interface is similar to Haskell's native STM library. Transactions are monadically composable, pure functional, and there is a lot of useful monadic combinators to make designing of concurrent model more convenient and powerful. I've implemented the Dining Philosophers problem using the library, and it works well. Here is a sample of some transaction for taking of forks by a philosopher:

STML<Unit> takeFork(const TFork& tFork) {
    return withTVar<Fork, Unit>(tFork, [=](const Fork& fork) {
       if (fork.state == ForkState::Free) {
           return writeTVar<Fork>(tFork, Fork {fork.name, ForkState:Taken});
       }
       else {
           return retry<Unit>();
       }
    });
}

STML<Unit> takeForks(const TForkPair& forks) {
    STML<Unit> lm = takeFork(forks.left);
    STML<Unit> rm = takeFork(forks.right);
    return sequence(lm, rm);
}