Folding is a highly generic operation available through std::accumulate. Paul Keir goes beyond reduction, with the help of C++14’s polymorphic lambdas.
Graham Hutton’s 1999 monograph:
A tutorial on the universality and expressiveness of fold
[
Hutton99
] provides a fascinating and eminently readable analysis of an elementary reduction operator from functional programming:
fold
. Hutton’s tutorial is punctuated by increasingly compelling examples, written in Haskell, of the use of
fold
to implement common list operations, including summation; concatenation; reversal; function composition;
left
folds; and concluding with the Ackermann function. The
fold
combinator is directly comparable to the C++ standard library function:
std::accumulate
. In this article, I focus on the
fold
examples from Hutton, and present equivalent generic C++ incarnations of each; making thorough use of appropriate C++14 library and language features, including polymorphic lambda functions
^{
1
}
.
The fourparameter
accumulate
function constructs a result from the repeated pairwise application of a given binary function, to elements supplied from both an iterator range; and a single “zero” value, having the type of the result. A canonical example is summation; the value returned from the call to
accumulate
in listing 1 is 10.
int xs[]{1,2,3,4}; accumulate(cbegin(xs), cend(xs), 0, plus<>{}); 
Listing 1 
Hutton’s first four examples use
fold
to implement arithmetic and logic operations using builtin functions to specify the relevant binary operations. Similar function objects are provided by the C++ standard library within the
<functional>
header. The example above demonstrates the use of
plus<>
for
operator+
; while
operator*
,
operator&&
, and
operator
correspond to
multiplies<>
,
logical_and<>
, and
logical_or<>
respectively. Note that C++14 conveniently defines a default template argument for such function objects;
std::plus<>
invokes a specialisation which infers the relevant types from its arguments.
Accommodating std::accumulate
A binary operator is said to be
associative
when an expression involving a sequence of its applications produces the same result, regardless of the order of evaluation. The four C++ function objects from the previous section all denote associative operations. Consider addition: both (1 + 2) + 3 and 1 + ( 2 + 3 ) produce the same result; 6. Operator precedence is irrelevant when faced with a ⊕ b ⊕ c; the question is whether to evaluate from the
left
; or from the
right
. In particular, which order does
accumulate
use? It uses a left ordering.
An elementary
nonassociative
binary operation is
subtraction
. The call to
accumulate
in listing 2 would then produce a result equal to (( 0  1)  2 )  3, i.e.  6; evaluating from the left. In contrast, an evaluation ordered from the
right
, say 1 ( 2  ( 3  0 )), produces a result of 2. Alas, the remaining examples from Hutton [
Hutton99
] firmly assume the fold operation evaluates from the
right
.
vector<double> xs{1,2,3}; accumulate(cbegin(xs), cend(xs), 0, minus<>{}); 
Listing 2 
Producing a result from
accumulate
equal to a
right fold
requires two interventions: we need the order of traversal across the container elements reversed;
and
for the order of the arguments given to the binary operation to be switched
^{
2
}
. Listing 3 defines such a wrapper for
accumulate
, called
foldr
. The C++14 functions
crbegin
and
crend
return
const
iterators to the
reverse beginning
and
reverse end
of the container argument
c
. Meanwhile, the
flip
function, uses
std::bind
to reverse the argument order for the binary function object; e.g.
flip(minus<>{})(0,1)
evaluates to 1; not  1.
template <typename F> auto flip(const F &f) { return bind(f,_2,_1); } template <typename F, typename T, typename C> T foldr(const F &f, const T &z, const C &c) { return accumulate(crbegin(c), crend(c), z, flip(f)); } 
Listing 3 
The definition of
foldr
in listing 3 removes the need to call
crbegin
,
crend
and
flip
. It also allows a single container argument to drive the C++
fold
; much as with C++
ranges
[
Niebler15
]. This allows listings here to remain concise; while also facilitating a comparison of the syntactical differences between Haskell and C++. We can now invoke a
right fold
. Assuming `
C
` creates an arbitrary standard sequence container, with inferred value type
^{
3
}
, the call to
foldr
in listing 4 returns the integer 2.
foldr(minus<>{}, 0, C(1,2,3)) 
Listing 4 
Nonreducing folds
Using a
fold
to concatenate two containers first requires a small helper function, which should return a new container, by adding a single element to the front of an existing one. Haskell provides the
(:)
operator for this job. Listing 5 defines this using its traditional Lisp name: “cons”.
auto cons = [=](auto x, auto xs) { decltype(xs) ys{x}; copy(begin(xs), end(xs), back_inserter(ys)); return ys; }; 
Listing 5 
Like
subtraction
, the
cons
function is
nonassociative
; and
noncommutative
.
cons
though, expects two different argument types. Listing 6 provides
foldr
with
cons
as the binary function, and an empty container as the “zero” or starting value; to define an identity
fold
. That is,
id(C(1,2,3))
will return a container object of the same type; with the same 3 elements. Meanwhile, the genericity of C++ allows a similar invocation which only changes the container type:
foldr(cons, list<int>{}, C(1,2,3))
.
auto id = [=](auto xs) { return foldr(cons, decltype(xs){}, xs); }; 
Listing 6 
To append one container to another, listing 7 again uses
cons
for
foldr
’s first argument; while providing the second, a container, as its “zero” value. Note that while the elements of, say,
append(C('a'),C('b'))
and
C('a','b')
are equal, so too are they equal to
append(C<list>('a'),C<vector>('b'))
; as the definition is sufficiently generic.
auto append = [=](auto xs, auto ys) { return foldr(cons, ys, xs); }; 
Listing 7 
Folding with lambda arguments
The three functions
^{
4
}
of listing 8 provide each corresponding
foldr
invocation with a binary lambda function, as, like Haskell, no equivalents exist within the standard library. The
length
function returns the size of its container argument, using a lambda function with unnamed first argument. Both
reverse
and
map
return a container
^{
5
}
; with
map
utilising the closure aspect of lambda expressions to capture
f
.
auto length = [=](auto xs){ return foldr( [=](auto, auto n){ return 1+n; }, 0, xs); }; auto reverse = [=](auto xs){ return foldr( [=](auto y, auto ys) { return append(ys,decltype(xs){y}); }, decltype(xs){}, xs); }; auto map = [=](auto f, auto xs){ return foldr( [=](auto y, auto ys){ return cons(f(y),ys); }, vector<decltype(f(*xs.begin()))>{}, xs); }; 
Listing 8 
Tuples allow a single fold to perform more than one calculation. For example, listing 9 defines a function which returns both the size of a container, and the sum of its elements ^{ 6 } .
auto sumlength = [=](auto xs){ return foldr( [=](auto n, auto p){ return make_pair(n + p.first, 1 + p.second); }, make_pair(0,0), xs); }; 
Listing 9 
Functions from folds
The result of applying the
composition
of two functions
f
and
g
to an argument
x
can be achieved in C++ with the expression:
f(g(x))
. In Haskell an elementary binary operator,
(.)
, can also be used; accepting two functions as arguments, and returning a
new
function representing their composition. In listing 10, the
fold
’s binary function argument is a comparable lambda expression for composition. The result of invoking
compose
with a container of callable elements is a function object representing the chained composition of each function in sequence. The “zero” argument of
foldr
uses a simple lambda identity function; though notice it is wrapped by the type of the container element: an instantiation of
std::function
. Why? While the type of each lambda expression is unique, the type of each container element is the same.
std::function
provides exactly the required homogeneity; each lambda accepting and returning say an
int
, becomes simply
std::function<int(int)>
. The “zero”, meanwhile, needs the same wrapper, as it provides the type of the
fold
’s result.
auto compose = [=](auto fs){ using fn_t = typename decltype(fs)::value_type; return foldr( [=](auto f, auto g) { return [=](auto x){ return f(g(x)); }; }, fn_t([=](auto x){ return x; }), fs); }; 
Listing 10 
One of the most intriguing functions capable of definition by a
right fold
, such as our
foldr
, is a
left fold
. Listing 11 provides such a definition. As before, an identity function is required for the
fold
’s starting value, and again this wild lambda needs the guiding hand of
std::function
; though the type in question is calculated in a different manner. Unlike
compose
, the function object returned by
foldr
is invoked within
foldl
; upon
z
. Our journey has brought us full circle to a
left fold
, akin to
std::accumulate
; an invocation such as
foldl(minus<>{}, 0, C(1,2,3))
will produce 6; much as listing 2.
auto foldl = [=](auto f, auto z, auto xs){ using z_t = decltype(z); using fn_t = std::function<z_t(z_t)>; return foldr( [=](auto x, auto g){ return [=](auto a){ return g(f(a,x)); }; }, fn_t([=](auto x){ return x; }),xs)(z); }; 
Listing 11 
One last comment regarding
left
and
right
folds: should you ever be in the embarrassing situation of being uncertain of the handedness of your
fold
definition, the expression in listing 12 could be useful. Simply replace
fold
with either
foldr
or
foldl
; for a
true
or
false
evaluation respectively.
fold([](auto x, auto){ return x; }, false, C(true)) 
Listing 12 
Our final fold example, and so too in [ Hutton99 ], is Ackermann’s function [ Ackermann28 ]. Ackermann’s function is commonly cited as a recursive function which is not primitive recursive in a firstorder programming language. John Reynolds, however, demonstrated [ Reynolds85 ] that the function is primitive recursive in a higherorder programming language. The C++ implementation in listing 13 includes similar idioms to previous examples, but is given additional treatment to avoid the use of currying seen in Hutton’s definition. While the binary lambda function provided to the innermost fold in the curried original appears unary, λ y → g , the C++ version must be uncurried: λ y as → g(as) . Note too, that these Ackermann folds encode the traditional natural number arguments within the size of the input and output container values.
auto ack = [=](auto xs, auto ys){ using ys_t = decltype(ys); using fn_t = std::function<ys_t(ys_t)>; return [=](auto zs){ return foldr( [=](auto, auto g){ return [=](auto ws){ return foldr( [=](auto, auto as){ return g(as); }, g(ys_t{1}), ws ); }; }, fn_t([=](auto bs){ return cons(1,bs); }), zs ); }(xs)(ys); }; 
Listing 13 
Summary
C++ lambda functions, including the polymorphic variety now available in C++14, allow the generic
fold
operation supported by
std::accumulate
to extend well beyond simple reductions. While a complex
fold
can be less readable or idiomatic than the traditional form, the approach can be refined to construct and transform programs, as well as prove specific program properties; while building on established software engineering principles of reuse and abstraction.
The article places less emphasis on performance considerations, instead focusing on pedagogy and algorithmic aspects; while maintaining parity with the equivalent Haskell, with consistent use of
auto
for type inference.
C++17 will introduce
fold expressions
[
Sutton14
]. Here, a
finite
set of operators, will share the brevity of the
comma
in pack expansion; consider
*
versus
std::multiplies<>{}
. One restriction is the variadic template pack length must be known at compiletime.
Appendix
All examples, along with code for
dropWhile
,
filter
and other folds are available at
https://bitbucket.org/pgk/accumulate
.
References
[Ackermann28] W. Ackermann. Zum Hilbertschen Aufbau der reellen Zahlen Mathematische Annalen, 1928.
[Bird88] R. Bird and P. Wadler. Introduction to Functional Programming Prentice Hall, 1988.
[Gill93] A. Gill, J. Launchbury and S.P. Jones. A Short Cut to Deforestation . ACM Press, 1993.
[Hutton99] G. Hutton. A tutorial on the universality and expressiveness of fold Cambridge University Press, 1999.
[Niebler15] E. Niebler. Working Draft, C++ extensions for Range s. The C++ Standards Committee, 2015.
[Reynolds85] J.C. Reynolds. Three approaches to type structure SpringerVerlag, 1985.
[Sutton14] A. Sutton and R. Smith. Folding expressions . The C++ Standards Committee, 2014.
 Note that most of these fold examples can also be found in [ Bird88 ] or [ Gill93 ].
 This is described as the third duality theorem in [ Bird88 , p68].

Assume a
vector
default; i.e.C(1,2)
becomes:C<vector,int>(1,2)
. 
A definition of
filter
from [ Hutton99 ] appears in the appendix. 
Note that
map
returns avector
object here solely for brevity. 
A similar tuplebased definition of
dropWhile
appears in the appendix.