What is fn?

fn is a C++ header-only template library which brings some of Haskell's higher order functions to C++. With this library you can give your source code a functional touch. Some lines of code say more than a thousand words:

// filter, foldl:
std::vector<int> numbers = { 1, 2, 3, 4, 5 };
std::vector<int> evenNumbers = fn::filter(numbers, fn::divisibleBy(2));
int product1 = fn::foldl(evenNumbers, std::multiplies<int>());
int product2 = fn::product(evenNumbers); // equivalent

// map:
std::vector<int> hundreds = fn::map(numbers, fn::multiply(100));

// map with member function:
std::vector<std::string> names = { "Alice", "Bob", "Carol", "Dave" };
std::vector<int> nameLengths = fn::map(names, &std::string::length);

// filter with member function:
std::vector<std::string> ugly = { "", "foo", "", "bar", "" };
std::vector<std::string> nice = fn::filter(ugly, &std::string::length, fn::notEqualTo(0));

The interface style of fn functions

Note that in contrast to the Haskell equivalents, fn functions take the range (the data structure to operate on) as their first argument. This maps to the interfaces of the STL algorithms, except you don't have to explicitly query the begin and end iterators. If you want fn functions to operate on sub-ranges, you can simply wrap the iterator pair in a fn::makeRange(begin, end) and pass this to the fn function.

The typical usage of fn functions is:

fn::algorithm(range, arguments...);            // algorithms working on one range
fn::algorithm(range1, range2, arguments...);   // algorithms working on two ranges

Overview of fn

The current version of fn defines the following subset of Haskell's prelude in C++. The Haskell's equivalent is written besides.

Algorithms

The following algorithms are lazy (see below).

• fn::filter(range, f) = filter f range
• fn::map(range, f) = map f range
• fn::zip(range1, range2) = zip range1 range2
• fn::zipWith(range1, range2, f) = zipWith f range1 range2

The following algorithms are currently evaluated when called immediately. In future versions, they might become lazy, too.

• fn::foldl(range, initial, f) = foldl f initial range
• fn::foldr(range, initial, f) = foldr f initial range
• fn::foldl(range, f) = foldl1 f range (asserts non-empty range)
• fn::foldr(range, f) = foldr1 f range (asserts non-empty range)

Special folds on ranges are also defined for convenience:

• fn::sum(range) = sum range
• fn::product(range) = product range
• fn::all(range) = all range
• fn::any(range) = any range
• fn::min(range) = min range
• fn::max(range) = min range

Ranges (lists)

• fn::makeRange(begin, end) to construct an fn compatible range from a random-access iterator pair
• fn::head(range) = head range
• fn::tail(range) = tail range

Arithmetic

fn provides the following unary functor constructors which bind one argument to an arithmetic operator, but not the second. This is useful for good-looking code without the overhead of C++ lambda code. Note that fn uses the normal C++ operators behind the scenes, so adding strings for example will concatenate them, since the operator has been overloaded accordingly. Note also that the type of the missing argument doesn't have to be of the same type than the bound value.

Binding the second parameter of an arithmetic operation:

• fn::plus(x) = (+x)
• fn::minus(x) = (-x)
• fn::multiplies(x) = (*x)
• fn::divides(x) = (/x)
• fn::modulus(x) = (`mod`x)

Binding the first parameter of an arithmetic operation (this is just the reverse order):

• fn::addedTo(x) = (x+)
• fn::subtractedFrom(x) = (x-)
• fn::multipliedTo(x) = (x*)
• fn::dividedFrom(x) = (x/)
• fn::modulusFrom(x) = (x`mod`)

For relational operators, fn provides unary functors binding the second parameter only:

• fn::equalTo(x) = (==x)
• fn::notEqualTo(x) = (/=x)
• fn::greater(x) = (>x)
• fn::less(x) = (<x)
• fn::greaterEqual(x) = (>=x)
• fn::lessEqual(x) = (<=x)

To test for divisibility, the following functors are provided for convenience:

• fn::divisibleBy(x) = (\a -> a `mod` x == 0)
• fn::indivisibleBy(x) = (\a -> a `mod` x /= 0)

The following functors don't bind any argument and provide unary operations:

• fn::identity() = id
• fn::negate() = negate
• fn::logicalNot() = not
• fn::bitwiseNot()
• fn::dereference()
• fn::reference()

Associative containers

The higher order functions of fn supports associative containers of either of these two interfaces:

• STL-style: The value type of the container (and the iterator) is a pair holding both the key and value.
• Qt-style: The container has a value type and key type. The iterator returns the value when dereferenced and there is a key() member returning the key.

Qt-style containers are transparently "converted" to an STL-style associative container by silently calling fn::makeRange() when passed to one of the higher order functions of fn. The result can again be written to either an STL- or a Qt-style container, independently of the input. fn internally always uses STL-style iterators.

QMap<int,QString> bar = ...;
QMap<int,QString> foo = fn::map(bar, [](std::pair<int,QString> e){ ... });

Since a functor passed to a map or filter function very often only operates on either the key or the value instead of both, fn provides convenience functions for these use cases:

• fn::mapKeys(range, f): Same as fn::map, but f gets called on the first member of the value type. The result is a std::pair consisting of the mapped first component (as returned by f) and the original second component.
• fn::mapValues(range, f): Same as fn::map, but f gets called on the second member of the value type. The result is a std::pair consisting of the original first component and the mapped second component (as returned by f).
• fn::filterKeys(range, f): Same as fn::filter, but f gets called on the first member of the value type.
• fn::filterValues(range, f): Same as fn::filter, but f gets called on the second member of the value type.

Lazy evaluation

Some of the higher order functions are evaluated lazily. The result of the functions is only an adaptor object, which "remembers" what you want to do with the input range(s). As soon as you assign the result to any container supported as targets by fn, they get converted to a new instance of the target type, which is finally move-assigned to the target variable.

This has some caveats. If you use the C++11 auto keyword, the result of such a function is not evaluated, since you store the adaptor into a variable. This isn't problematic if you pass this to another fn higher order function, since the adaptor provides a classic iterator interface with .begin() and .end() being implemented. This makes it also possible to be used in range-based loops:

for (int x : fn::filter(numbers, fn::less(10))) {
    ...
}

However, keep in mind that the functor passed to such function calls is only evaluated when the result is used (as this is how lazy evaluation works).