The Foldable
concept represents data structures that can be reduced to a single value.
Generally speaking, folding refers to the concept of summarizing a complex structure as a single value, by successively applying a binary operation which reduces two elements of the structure to a single value. Folds come in many flavors; left folds, right folds, folds with and without an initial reduction state, and their monadic variants. This concept is able to express all of these fold variants.
Another way of seeing Foldable
is as data structures supporting internal iteration with the ability to accumulate a result. By internal iteration, we mean that the loop control is in the hand of the structure, not the caller. Hence, it is the structure who decides when the iteration stops, which is normally when the whole structure has been consumed. Since C++ is an eager language, this requires Foldable
structures to be finite, or otherwise one would need to loop indefinitely to consume the whole structure.
Foldable
only works for finite structures may seem overly restrictive in comparison to the Haskell definition of Foldable
, a finer grained separation of the concepts should mitigate the issue. For iterating over possibly infinite data structures, see the Iterable
concept. For searching a possibly infinite data structure, see the Searchable
concept.fold_left
or unpack
However, please note that a minimal complete definition provided through unpack
will be much more compiletime efficient than one provided through fold_left
.
hana::map
, hana::optional
, hana::pair
, hana::set
, hana::range
, hana::tuple
Intuitively, for a Foldable
structure xs
, the linearization of xs
is the sequence of all the elements in xs
as if they had been put in a list:
Note that it is always possible to produce such a linearization for a finite Foldable
by setting
for an appropriate definition of []
and prepend
. The notion of linearization is useful for expressing various properties of Foldable
structures, and is used across the documentation. Also note that Iterable
s define an extended version of this allowing for infinite structures.
A compiletime Foldable
is a Foldable
whose total length is known at compiletime. In other words, it is a Foldable
whose length
method returns a Constant
of an unsigned integral type. When folding a compiletime Foldable
, the folding can be unrolled, because the final number of steps of the algorithm is known at compiletime.
Additionally, the unpack
method is only available to compiletime Foldable
s. This is because the return type of unpack
depends on the number of objects in the structure. Being able to resolve unpack
's return type at compiletime hence requires the length of the structure to be known at compiletime too.
In the current version of the library, only compiletime Foldable
s are supported. While it would be possible in theory to support runtime Foldable
s too, doing so efficiently requires more research.
Given a tag S
which is a Sequence
, an object whose tag is a model of the Foldable
concept can be converted to an object of tag S
. In other words, a Foldable
can be converted to a Sequence
S
, by simply taking the linearization of the Foldable
and creating the sequence with that. More specifically, given a Foldable
xs
with a linearization of [x1, ..., xn]
and a Sequence
tag S
, to<S>(xs)
is equivalent to make<S>(x1, ..., xn)
.
Builtin arrays whose size is known can be folded asif they were homogeneous tuples. However, note that builtin arrays can't be made more than Foldable
(e.g. Iterable
) because they can't be empty and they also can't be returned from functions.
A monadic fold is a fold in which subsequent calls to the binary function are chained with the monadic chain
operator of the corresponding Monad. This allows a structure to be folded in a custom monadic context. For example, performing a monadic fold with the hana::optional
monad would require the binary function to return the result as a hana::optional
, and the fold would abort and return nothing
whenever one of the accumulation step would fail (i.e. return nothing
). If, however, all the reduction steps succeed, then just
the result would be returned. Different monads will of course result in different effects.
Variables  
constexpr auto  boost::hana::count 
Return the number of elements in the structure that compare equal to a given value. More...  
constexpr auto  boost::hana::count_if 
Return the number of elements in the structure for which the predicate is satisfied. More...  
constexpr auto  boost::hana::fold = fold_left 
Equivalent to fold_left ; provided for convenience. More...  
constexpr auto  boost::hana::for_each 
Perform an action on each element of a foldable, discarding the result each time. More...  
constexpr auto  boost::hana::fuse 
Transform a function taking multiple arguments into a function that can be called with a compiletime Foldable . More...  
constexpr auto  boost::hana::length 
Return the number of elements in a foldable structure. More...  
constexpr auto  boost::hana::product = see documentation 
Compute the product of the numbers of a structure. More...  
constexpr auto  boost::hana::size = hana::length 
Equivalent to length ; provided for consistency with the standard library. More...  
constexpr auto  boost::hana::sum = see documentation 
Compute the sum of the numbers of a structure. More...  
constexpr auto  boost::hana::unpack 
Invoke a function with the elements of a Foldable as arguments. More...  

constexpr 
#include <boost/hana/fwd/count.hpp>
Return the number of elements in the structure that compare equal to a given value.
Given a Foldable structure xs
and a value value
, count
returns an unsigned integral, or a Constant thereof, representing the number of elements of xs
that compare equal to value
. For this method to be welldefined, all the elements of the structure must be Comparable with the given value.
xs  The structure whose elements are counted. 
value  A value compared with each element in the structure. Elements that compare equal to this value are counted, others are not. 

constexpr 
#include <boost/hana/fwd/count_if.hpp>
Return the number of elements in the structure for which the predicate
is satisfied.
Specifically, returns an object of an unsigned integral type, or a Constant
holding such an object, which represents the number of elements in the structure satisfying the given predicate
.
xs  The structure whose elements are counted. 
predicate  A function called as predicate(x) , where x is an element of the structure, and returning a Logical representing whether x should be counted. 

constexpr 
#include <boost/hana/fwd/fold.hpp>
Equivalent to fold_left
; provided for convenience.
fold
is equivalent to fold_left
. However, it is not tagdispatched on its own because it is just an alias to fold_left
. Also note that fold
can be called with or without an initial state, just like fold_left
:

constexpr 
#include <boost/hana/fwd/for_each.hpp>
Perform an action on each element of a foldable, discarding the result each time.
Iteration is done from left to right, i.e. in the same order as when using fold_left
. If the structure is not finite, this method will not terminate.
xs  The structure to iterate over. 
f  A function called as f(x) for each element x of the structure. The result of f(x) , whatever it is, is ignored. 

constexpr 
#include <boost/hana/fwd/fuse.hpp>
Transform a function taking multiple arguments into a function that can be called with a compiletime Foldable
.
This function is provided for convenience as a different way of calling unpack
. Specifically, fuse(f)
is a function such that
where x...
are the elements in the foldable. This function is useful when one wants to create a function that accepts a foldable which is not known yet.
unpack
instead.

constexpr 
#include <boost/hana/fwd/length.hpp>
Return the number of elements in a foldable structure.
Given a Foldable
xs
, length(xs)
must return an object of an unsigned integral type, or an IntegralConstant
holding such an object, which represents the number of elements in the structure.
Foldable
s are supported in the library right now, length
must always return an IntegralConstant
.

constexpr 
#include <boost/hana/fwd/product.hpp>
Compute the product of the numbers of a structure.
More generally, product
will take any foldable structure containing objects forming a Ring and reduce them using the Ring's binary operation. The initial state for folding is the identity of the Ring's operation. It is sometimes necessary to specify the Ring to use; this is possible by using product<R>
. If no Ring is specified, the structure will use the Ring formed by the elements it contains (if it knows it), or integral_constant_tag<int>
otherwise. Hence,
For numbers, this will just compute the product of the numbers in the xs
structure.
mult
on any two adjacent elements of the structure, which requires each pair of adjacent element to at least have a common Ring embedding. The meaning of "adjacent" as used here is that two elements of the structure x
and y
are adjacent if and only if they are adjacent in the linearization of that structure, as documented by the Iterable concept.sum
to understand why the Ring must sometimes be specified explicitly.

constexpr 
#include <boost/hana/fwd/size.hpp>
Equivalent to length
; provided for consistency with the standard library.
This method is an alias to length
provided for convenience and consistency with the standard library. As an alias, size
is not tagdispatched on its own and length
should be customized instead.

constexpr 
#include <boost/hana/fwd/sum.hpp>
Compute the sum of the numbers of a structure.
More generally, sum
will take any foldable structure containing objects forming a Monoid and reduce them using the Monoid's binary operation. The initial state for folding is the identity of the Monoid. It is sometimes necessary to specify the Monoid to use; this is possible by using sum<M>
. If no Monoid is specified, the structure will use the Monoid formed by the elements it contains (if it knows it), or integral_constant_tag<int>
otherwise. Hence,
For numbers, this will just compute the sum of the numbers in the xs
structure.
plus
on any two adjacent elements of the structure, which requires each pair of adjacent element to at least have a common Monoid embedding. The meaning of "adjacent" as used here is that two elements of the structure x
and y
are adjacent if and only if they are adjacent in the linearization of that structure, as documented by the Iterable concept.This is because sequence tags like tuple_tag
are not parameterized (by design). Hence, we do not know what kind of objects are in the sequence, so we can't know a 0
value of which type should be returned when the sequence is empty. Therefore, the type of the 0
to return in the empty case must be specified explicitly. Other foldable structures like hana::range
s will ignore the suggested Monoid because they know the tag of the objects they contain. This inconsistent behavior is a limitation of the current design with nonparameterized tags, but we have no good solution for now.

constexpr 
#include <boost/hana/fwd/unpack.hpp>
Invoke a function with the elements of a Foldable as arguments.
Given a function and a foldable structure whose length can be known at compiletime, unpack
invokes the function with the contents of that structure. In other words, unpack(xs, f)
is equivalent to f(x...)
, where x...
are the elements of the structure. The length of the structure must be known at compiletime, because the version of f
's operator()
that will be compiled depends on the number of arguments it is called with, which has to be known at compiletime.
To create a function that accepts a foldable instead of variadic arguments, see fuse
instead.
xs  The structure to expand into the function. 
f  A function to be invoked as f(x...) , where x... are the elements of the structure asif they had been linearized with to<tuple_tag> . 
It has been suggested a couple of times that unpack
be called apply
instead, and that the parameter order be reversed to match that of the proposed std::apply function. However, the name apply
is already used to denote normal function application, an use which is consistent with the Boost MPL library and with the rest of the world, especially the functional programming community. Furthermore, the author of this library considers the proposed std::apply
to have both an unfortunate name and an unfortunate parameter order. Indeed, taking the function as the first argument means that using std::apply
with a lambda function looks like
which is undeniably ugly because of the trailing , tuple)
part on the last line. On the other hand, taking the function as a second argument allows one to write
which looks much nicer. Because of these observations, the author of this library feels justified to use unpack
instead of apply
, and to use a sane parameter order.