FTL - The Functional Template Library

C++ template library for fans of functional programming. The goal of this project is to implement a useful subset of the Haskell Prelude (and a couple of other libraries) in C++. Presently, this subset is small, but rapidly growing. Note, however, that the library and its API are still in heavy flux and the interface of any data type or concept may yet change without notice.

To use the FTL, you need a compiler that implements at least as much of C++11 as gcc-4.7. As of this time, that's more or less gcc-4.7+, as well as clang-3.2+. Both of these are regularly run against the included set of unit tests and should work. MSVC, including the recent 2013 preview, is unfortunately incompatible as of yet.

The full API reference can be found here.

Tutorials

Showcases

A couple of quick showcases of some rather neat things the FTL gives you.

Curried Function Calling

One of the typically functional conventions brought to C++ by FTL is support for curried functions and function objects. A curried function is an n-ary function that can be invoked one argument at a time; each step returning a new function object of arity n-1. Once enough parameters have been applied (when n reaches 0), the actual computation is performed and the result is returned. One of the uses of this is to achieve very convenient partial function application. For example:

auto plus = ftl::curry(std::plus<int>);
auto addOne = plus(1);

auto x = addOne(2); // x = 3
auto y = addOne(x); // y = 4

As mentioned, all of the function objects provided by FTL are curried by default and do not require an ftl::curry call first. Partial application is thus in many cases extremely concise and clean. Note, however, that without, for instance, a wrapping lambda function, it is not possible to partially apply parameters other than in the exact order they appear. For example, the following are all valid:

auto f = curriedTernaryFn(1);
auto g = curriedTernaryFn(1,2);

f(2)(3) == f(2,3) && f(2,3) == g(3); // true

But it is not possible to "skip" a parameter or leave a placeholder, as in:

using std::placeholders::_1;
auto f = std::bind(ternaryFn, _1, 2, 3);

Currying by itself is a very nice thing to have, but what truly makes it shine is when used in combination with e.g. higher order functions. See for instance applicative style coding, which is not nearly as nice without currying.

Expanding The Standard Library

One of the nice things about FTL is that it does not try to replace or supercede the standard library, it tries to expand it when possible. These expansions include giving existing types concept instances for e.g. Functor, Monad, Monoid, and others. For example, in FTL, std::shared_ptr is a monad. This means we can sequence a series of operations working on shared pointers without ever having to explicitly check for validity—while still being assured there are no attempts to access an invalid pointer.

For example, given

shared_ptr<a> foo();
shared_ptr<b> bar(a);

We can simply write

shared_ptr<b> ptr = foo() >>= bar;

Instead of

shared_ptr<b> ptr(nullptr);
auto ptra = foo();
if(ptra) {
    ptr = bar(*ptra);
}

Which would be the equivalent FTL-less version of the above.

Monadic code may perhaps often look strange if you're not used to all the operators, but once you've got that, reading it becomes amazingly easy and clear. operator>>= above is used to sequence two monadic computations, where the second is dependant on the result of the first. Exactly what it does varies with monad instance, but in the case of shared_ptr, it essentially performs nullptr checks and either aborts the expression (returning a nullptr initialised shared_ptr), or simply passes the valid result forward.

Other types that have been similarly endowed with new powers include: std::future, std::list, std::vector, std::forward_list, std::map, std::unordered_map, std::set, and more.

Applying Applicatives

Adding a bit of the Applicative concept to the mix, we can do some quite concise calculations. Now, if we are given:

int algorithm(int, int, int);
shared_ptr<int> getSomeShared();
shared_ptr<int> getOtherShared();
shared_ptr<int> getFinalShared();

Then we can compute:

/* ftl::operator% is short for ftl::fmap, basically the classic "map" function
 * of functional programming.
 * Similarly, ftl::operator* is short for ftl::aapply, the work horse function of
 * applicative programming style. It basically applies a function (the left hand
 * side) to one argument at a time (the right hand side).
 */
auto result = curry(algorithm) % getSomeShared() * getOtherShared() * getFinalShared();

And of course the equivalent plain version:

std::shared_ptr<int> result;
auto x = getSomeShared(), y = getOtherShared(), z = getFinalShared();
if(x && y && z) {
    result = make_shared(algorithm(*x, *y, *z));
}

If algorithm had happened to be wrapped in an ftl::function, or else be one of the built-in, curried-by-default function objects of FTL, then the curry call could have been elided for even cleaner code.

Transformers

No, not as in Optimus Prime! As in a monad transformer: a type transformer that takes one monad as parameter and "magically" adds functionality to it in the form of one of many other monads. For example, let's say you want to add the functionality of the maybe monad to the list monad. You'd have to create a new type that combines the powers, then write all of those crazy monad instances and whatnot, right? Wrong!

template<typename T>
using listM = ftl::maybeT<std::list<T>>;

Bam! All the powers of lists and maybes in one! What exactly does that mean though? Well, let's see if we can get an intuition for it.

// With the inplace tag, we can call list's constructor directly
listM<int> ms{ftl::inplace_tag(), ftl::value(1), ftl::maybe<int>{}, ftl::value(2)};

// Kind of useless, but demonstrates what's going on
for(auto m : *ms) {
    if(m)
        std::cout << *m << ", ";
    else
        std::cout << "nothing, ";
}
std::cout << std::endl;

If run, the above would produce:

1, nothing, 2,

So, pretty much a list of maybes then, what's the point? The point is, the new type listM is a monad, in pretty much the same way as std::list is, except we can apply, bind, and map functions that work with Ts. That is, given the above list, ms, we can do:

auto ns = [](int x){ return x-1; } % ms;

// Let's say this invokes the same print loop as before
print(ns);

Same deal, but if ms was a regular, untransformed list of maybe:

auto ns = [](maybe<int> x){ return x ? maybe<int>((*x)-1) : return x; } % ms;

print(ns);

Output (in both cases):

0, nothing, 1,

So, basically, this saves us the trouble of having to check for nothingness in the elements of ns (coincidentally—or not—exactly what the maybe monad does: allow us to elide lots of ifs).

Right, this is kinda neat, but not really all that exciting yet. The excitement comes when we stop to think a bit before we just arbitrarily throw together a couple of monads. For instance, check out the magic of the either-transformer on top of the function monad in the parser generator tutorial part 2.

Yet More Concepts

In addition to the above concepts, FTL contains several more of the classic Haskell type classes: Monoids, Foldables, and Orderables. These all express nice and abstracted interfaces that apply to many types, both built-in, standard library ones, and user defined ones (assuming one adds a concept instance). For instance, the code below uses the fact that an ordering is a Monoid to sort a vector of MyType by first one of its properties, then another.

using namespace ftl;
std::sort(vec.begin(), vec.end(),
    asc(comparing(&MyType::someProperty) ^ comparing(&MyType::anotherProperty))
);

The equivalent version without FTL might look a bit like this:

std::sort(vec.begin(), vec.end(), [](const MyType& lhs, const MyType& rhs){
    return lhs.someProperty() == rhs.someProperty()
        ? lhs.anotherProperty() < rhs.anotherProperty()
        : lhs.someProperty() < rhs.someProperty();
});

Personally, I find the former a lot cleaner and easier to read. The sort order is explicitly stated (asc), and then it just straight up says that we sort by comparing first someProperty and then anotherProperty. Fewer chances of subtle typos, less chance of screwing up the comparisons, much easier to extend, what's not to like?

jaredgrubb/ftl