Wiki
Clone wikifn / Home
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 pairfn::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 asfn::map
, butf
gets called on thefirst
member of the value type. The result is astd::pair
consisting of the mapped first component (as returned byf
) and the original second component.fn::mapValues(range, f)
: Same asfn::map
, butf
gets called on thesecond
member of the value type. The result is astd::pair
consisting of the original first component and the mapped second component (as returned byf
).fn::filterKeys(range, f)
: Same asfn::filter
, butf
gets called on thefirst
member of the value type.fn::filterValues(range, f)
: Same asfn::filter
, butf
gets called on thesecond
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).
Updated