Boost.Hana  1.0.2
Your standard library for metaprogramming
Foldable

Description

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.

Note
While the fact that 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.

Minimal complete definition

fold_left or unpack

However, please note that a minimal complete definition provided through unpack will be much more compile-time efficient than one provided through fold_left.

Concrete models

hana::map, hana::optional, hana::pair, hana::set, hana::range, hana::tuple

The linearization of a Foldable

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:

linearization(xs) = [x1, x2, ..., xn]

Note that it is always possible to produce such a linearization for a finite Foldable by setting

linearization(xs) = fold_left(xs, [], flip(prepend))

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 Iterables define an extended version of this allowing for infinite structures.

Compile-time Foldables

A compile-time Foldable is a Foldable whose total length is known at compile-time. In other words, it is a Foldable whose length method returns a Constant of an unsigned integral type. When folding a compile-time Foldable, the folding can be unrolled, because the final number of steps of the algorithm is known at compile-time.

Additionally, the unpack method is only available to compile-time Foldables. 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 compile-time hence requires the length of the structure to be known at compile-time too.

In the current version of the library, only compile-time Foldables are supported. While it would be possible in theory to support runtime Foldables too, doing so efficiently requires more research.

Provided conversion to Sequences

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).

// Copyright Louis Dionne 2013-2016
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
namespace hana = boost::hana;
int main() {
static_assert(hana::to<hana::tuple_tag>(hana::just(1)) == hana::make_tuple(1), "");
BOOST_HANA_CONSTANT_CHECK(hana::to<hana::tuple_tag>(hana::nothing) == hana::make_tuple());
hana::to<hana::tuple_tag>(hana::make_range(hana::int_c<3>, hana::int_c<6>))
==
hana::tuple_c<int, 3, 4, 5>
);
}

Free model for builtin arrays

Builtin arrays whose size is known can be folded as-if 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.

Primer on monadic folds

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.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 well-defined, all the elements of the structure must be Comparable with the given value. More...
 
constexpr auto boost::hana::count_if
 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. More...
 
constexpr auto boost::hana::fold = fold_left
 Equivalent to fold_left; provided for convenience.fold is equivalent to fold_left. However, it is not tag-dispatched 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: More...
 
constexpr auto boost::hana::fold_left
 Left-fold of a structure using a binary operation and an optional initial reduction state.fold_left is a left-associative fold using a binary operation. Given a structure containing x1, ..., xn, a function f and an optional initial state, fold_left applies f as follows. More...
 
constexpr auto boost::hana::fold_right
 Right-fold of a structure using a binary operation and an optional initial reduction state.fold_right is a right-associative fold using a binary operation. Given a structure containing x1, ..., xn, a function f and an optional initial state, fold_right applies f as follows. More...
 
constexpr auto boost::hana::for_each
 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. More...
 
constexpr auto boost::hana::fuse
 Transform a function taking multiple arguments into a function that can be called with a compile-time Foldable. More...
 
constexpr auto boost::hana::length
 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. More...
 
constexpr auto boost::hana::maximum
 Return the greatest element of a non-empty structure with respect to a predicate, by default less.Given a non-empty structure and an optional binary predicate (less by default), maximum returns the greatest element of the structure, i.e. an element which is greater than or equal to every other element in the structure, according to the predicate. More...
 
constexpr auto boost::hana::minimum
 Return the least element of a non-empty structure with respect to a predicate, by default less.Given a non-empty structure and an optional binary predicate (less by default), minimum returns the least element of the structure, i.e. an element which is less than or equal to every other element in the structure, according to the predicate. More...
 
template<typename M >
constexpr auto boost::hana::monadic_fold_left
 Monadic left-fold of a structure with a binary operation and an optional initial reduction state. More...
 
template<typename M >
constexpr auto boost::hana::monadic_fold_right
 Monadic right-fold of a structure with a binary operation and an optional initial reduction state. More...
 
constexpr auto boost::hana::product = see documentation
 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,. More...
 
constexpr auto boost::hana::reverse_fold
 Equivalent to reverse_fold in Boost.Fusion and Boost.MPL.This method has the same semantics as reverse_fold in Boost.Fusion and Boost.MPL, with the extension that an initial state is not required. This method is equivalent to fold_right, except that the accumulating function must take its arguments in reverse order, to match the order used in Fusion. In other words,. More...
 
constexpr auto boost::hana::size = hana::length
 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 tag-dispatched on its own and length should be customized instead. More...
 
constexpr auto boost::hana::sum = see documentation
 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,. More...
 
constexpr auto boost::hana::unpack
 Invoke a function with the elements of a Foldable as arguments.Given a function and a foldable structure whose length can be known at compile-time, 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 compile-time, 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 compile-time. More...
 

Variable Documentation

constexpr auto boost::hana::count

#include <boost/hana/fwd/count.hpp>

Initial value:
= [](auto&& xs, auto&& value) {
return tag-dispatched;
}
constexpr auto value
Return the compile-time value associated to a constant.This function returns the value associated to ...
Definition: value.hpp:54

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 well-defined, all the elements of the structure must be Comparable with the given value.

Parameters
xsThe structure whose elements are counted.
valueA value compared with each element in the structure. Elements that compare equal to this value are counted, others are not.

Example

// Copyright Louis Dionne 2013-2016
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
namespace hana = boost::hana;
int main() {
constexpr auto ints = hana::tuple_c<int, 1, 2, 3, 2, 2, 4, 2>;
BOOST_HANA_CONSTANT_CHECK(hana::count(ints, hana::int_c<2>) == hana::size_c<4>);
static_assert(hana::count(ints, 2) == 4, "");
constexpr auto types = hana::tuple_t<int, char, long, short, char, double>;
BOOST_HANA_CONSTANT_CHECK(hana::count(types, hana::type_c<char>) == hana::size_c<2>);
}
constexpr auto boost::hana::count_if

#include <boost/hana/fwd/count_if.hpp>

Initial value:
= [](auto&& xs, auto&& predicate) {
return tag-dispatched;
}

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.

Parameters
xsThe structure whose elements are counted.
predicateA function called as predicate(x), where x is an element of the structure, and returning a Logical representing whether x should be counted.

Example

// Copyright Louis Dionne 2013-2016
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
#include <type_traits>
namespace hana = boost::hana;
using namespace hana::literals;
auto is_odd = [](auto x) {
return x % 2_c != 0_c;
};
int main() {
constexpr auto ints = hana::tuple_c<int, 1, 2, 3>;
BOOST_HANA_CONSTANT_CHECK(hana::count_if(ints, is_odd) == hana::size_c<2>);
constexpr auto types = hana::tuple_t<int, char, long, short, char, double>;
BOOST_HANA_CONSTANT_CHECK(hana::count_if(types, hana::trait<std::is_floating_point>) == hana::size_c<1>);
BOOST_HANA_CONSTANT_CHECK(hana::count_if(types, hana::equal.to(hana::type_c<char>)) == hana::size_c<2>);
BOOST_HANA_CONSTANT_CHECK(hana::count_if(types, hana::equal.to(hana::type_c<void>)) == hana::size_c<0>);
}
constexpr auto boost::hana::fold = fold_left

#include <boost/hana/fwd/fold.hpp>

Equivalent to fold_left; provided for convenience.fold is equivalent to fold_left. However, it is not tag-dispatched 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:

fold(xs, state, f) == fold_left(xs, state, f)
fold(xs, f) == fold_left(xs, f)

Example

// Copyright Louis Dionne 2013-2016
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
#include <sstream>
#include <string>
namespace hana = boost::hana;
auto to_string = [](auto x) {
std::ostringstream ss;
ss << x;
return ss.str();
};
int main() {
auto f = [=](std::string s, auto element) {
return "f(" + s + ", " + to_string(element) + ")";
};
// with an initial state
hana::fold(hana::make_tuple(2, '3', 4, 5.0), "1", f)
==
"f(f(f(f(1, 2), 3), 4), 5)"
);
// without initial state
hana::fold(hana::make_tuple("1", 2, '3', 4, 5.0), f)
==
"f(f(f(f(1, 2), 3), 4), 5)"
);
}
constexpr auto boost::hana::fold_left

#include <boost/hana/fwd/fold_left.hpp>

Initial value:
= [](auto&& xs[, auto&& state], auto&& f) -> decltype(auto) {
return tag-dispatched;
}

Left-fold of a structure using a binary operation and an optional initial reduction state.fold_left is a left-associative fold using a binary operation. Given a structure containing x1, ..., xn, a function f and an optional initial state, fold_left applies f as follows.

f(... f(f(f(x1, x2), x3), x4) ..., xn) // without state
f(... f(f(f(f(state, x1), x2), x3), x4) ..., xn) // with state

When the structure is empty, two things may arise. If an initial state was provided, it is returned as-is. Otherwise, if the no-state version of the function was used, an error is triggered. When the stucture contains a single element and the no-state version of the function was used, that single element is returned as is.

Signature

Given a Foldable F and an optional initial state of tag S, the signatures for fold_left are

\[ \mathtt{fold\_left} : F(T) \times S \times (S \times T \to S) \to S \]

for the variant with an initial state, and

\[ \mathtt{fold\_left} : F(T) \times (T \times T \to T) \to T \]

for the variant without an initial state.

Parameters
xsThe structure to fold.
stateThe initial value used for folding.
fA binary function called as f(state, x), where state is the result accumulated so far and x is an element in the structure. For left folds without an initial state, the function is called as f(x1, x2), where x1 and x2 are elements of the structure.

Example

// Copyright Louis Dionne 2013-2016
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
#include <sstream>
#include <string>
namespace hana = boost::hana;
auto to_string = [](auto x) {
std::ostringstream ss;
ss << x;
return ss.str();
};
int main() {
auto f = [=](std::string s, auto element) {
return "f(" + s + ", " + to_string(element) + ")";
};
// with an initial state
hana::fold_left(hana::make_tuple(2, '3', 4, 5.0), "1", f)
==
"f(f(f(f(1, 2), 3), 4), 5)"
);
// without initial state
hana::fold_left(hana::make_tuple("1", 2, '3', 4, 5.0), f)
==
"f(f(f(f(1, 2), 3), 4), 5)"
);
}
constexpr auto boost::hana::fold_right

#include <boost/hana/fwd/fold_right.hpp>

Initial value:
= [](auto&& xs[, auto&& state], auto&& f) -> decltype(auto) {
return tag-dispatched;
}

Right-fold of a structure using a binary operation and an optional initial reduction state.fold_right is a right-associative fold using a binary operation. Given a structure containing x1, ..., xn, a function f and an optional initial state, fold_right applies f as follows.

f(x1, f(x2, f(x3, f(x4, ... f(xn-1, xn) ... )))) // without state
f(x1, f(x2, f(x3, f(x4, ... f(xn, state) ... )))) // with state
Note
It is worth noting that the order in which the binary function should expect its arguments is reversed from fold_left.

When the structure is empty, two things may arise. If an initial state was provided, it is returned as-is. Otherwise, if the no-state version of the function was used, an error is triggered. When the stucture contains a single element and the no-state version of the function was used, that single element is returned as is.

Signature

Given a Foldable F and an optional initial state of tag S, the signatures for fold_right are

\[ \mathtt{fold\_right} : F(T) \times S \times (T \times S \to S) \to S \]

for the variant with an initial state, and

\[ \mathtt{fold\_right} : F(T) \times (T \times T \to T) \to T \]

for the variant without an initial state.

Parameters
xsThe structure to fold.
stateThe initial value used for folding.
fA binary function called as f(x, state), where state is the result accumulated so far and x is an element in the structure. For right folds without an initial state, the function is called as f(x1, x2), where x1 and x2 are elements of the structure.

Example

// Copyright Louis Dionne 2013-2016
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
#include <sstream>
#include <string>
namespace hana = boost::hana;
auto to_string = [](auto x) {
std::ostringstream ss;
ss << x;
return ss.str();
};
int main() {
auto f = [=](auto element, std::string s) {
return "f(" + to_string(element) + ", " + s + ")";
};
// with an initial state
hana::fold_right(hana::make_tuple(1, '2', 3.0, 4), "5", f)
==
"f(1, f(2, f(3, f(4, 5))))"
);
// without initial state
hana::fold_right(hana::make_tuple(1, '2', 3.0, 4, "5"), f)
==
"f(1, f(2, f(3, f(4, 5))))"
);
}
constexpr auto boost::hana::for_each

#include <boost/hana/fwd/for_each.hpp>

Initial value:
= [](auto&& xs, auto&& f) -> void {
tag-dispatched;
}

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.

Parameters
xsThe structure to iterate over.
fA function called as f(x) for each element x of the structure. The result of f(x), whatever it is, is ignored.

Example

// Copyright Louis Dionne 2013-2016
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
#include <sstream>
namespace hana = boost::hana;
int main() {
std::stringstream ss;
hana::for_each(hana::make_tuple(0, '1', "234", 5.5), [&](auto x) {
ss << x << ' ';
});
BOOST_HANA_RUNTIME_CHECK(ss.str() == "0 1 234 5.5 ");
}
constexpr auto boost::hana::fuse

#include <boost/hana/fwd/fuse.hpp>

Initial value:
= [](auto&& f) {
return [perfect-capture](auto&& xs) -> decltype(auto) {
return unpack(forwarded(xs), forwarded(f));
};
}
constexpr auto unpack
Invoke a function with the elements of a Foldable as arguments.Given a function and a foldable struct...
Definition: unpack.hpp:79
constexpr auto capture
Create a function capturing the given variables.
Definition: capture.hpp:45

Transform a function taking multiple arguments into a function that can be called with a compile-time Foldable.

This function is provided for convenience as a different way of calling unpack. Specifically, fuse(f) is a function such that

fuse(f)(foldable) == unpack(foldable, f)
== f(x...)

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.

Note
This function is not tag-dispatched; customize unpack instead.

Example

// Copyright Louis Dionne 2013-2016
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
namespace hana = boost::hana;
auto tie = [](auto& ...vars) {
return hana::fuse([&vars...](auto ...values) {
// Using an initializer list to sequence the assignments.
int dummy[] = {0, ((void)(vars = values), 0)...};
(void)dummy;
});
};
int main() {
int a = 0;
char b = '\0';
double c = 0;
tie(a, b, c)(hana::make_tuple(1, '2', 3.3));
BOOST_HANA_RUNTIME_CHECK(a == 1 && b == '2' && c == 3.3);
}
constexpr auto boost::hana::length

#include <boost/hana/fwd/length.hpp>

Initial value:
= [](auto const& xs) {
return tag-dispatched;
}

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.

Note
Since only compile-time Foldables are supported in the library right now, length must always return an IntegralConstant.

Example

// Copyright Louis Dionne 2013-2016
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
namespace hana = boost::hana;
int main() {
BOOST_HANA_CONSTANT_CHECK(hana::length(hana::make_tuple()) == hana::size_c<0>);
BOOST_HANA_CONSTANT_CHECK(hana::length(hana::make_tuple(1, '2', 3.0)) == hana::size_c<3>);
BOOST_HANA_CONSTANT_CHECK(hana::length(hana::nothing) == hana::size_c<0>);
BOOST_HANA_CONSTANT_CHECK(hana::length(hana::just('x')) == hana::size_c<1>);
}
constexpr auto boost::hana::maximum

#include <boost/hana/fwd/maximum.hpp>

Initial value:
= [](auto&& xs[, auto&& predicate]) -> decltype(auto) {
return tag-dispatched;
}

Return the greatest element of a non-empty structure with respect to a predicate, by default less.Given a non-empty structure and an optional binary predicate (less by default), maximum returns the greatest element of the structure, i.e. an element which is greater than or equal to every other element in the structure, according to the predicate.

If the structure contains heterogeneous objects, then the predicate must return a compile-time Logical. If no predicate is provided, the elements in the structure must be Orderable, or compile-time Orderable if the structure is heterogeneous.

Signature

Given a Foldable F, a Logical Bool and a predicate \( \mathtt{pred} : T \times T \to Bool \), maximum has the following signatures. For the variant with a provided predicate,

\[ \mathtt{maximum} : F(T) \times (T \times T \to Bool) \to T \]

for the variant without a custom predicate, T is required to be Orderable. The signature is then

\[ \mathtt{maximum} : F(T) \to T \]

Parameters
xsThe structure to find the greatest element of.
predicateA function called as predicate(x, y), where x and y are elements of the structure. predicate should be a strict weak ordering on the elements of the structure and its return value should be a Logical, or a compile-time Logical if the structure is heterogeneous.

Example

// Copyright Louis Dionne 2013-2016
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
namespace hana = boost::hana;
int main() {
// without a predicate
hana::maximum(hana::tuple_c<int, -1, 0, 2, -4, 6, 9>) == hana::int_c<9>
);
// with a predicate
auto smallest = hana::maximum(hana::tuple_c<int, -1, 0, 2, -4, 6, 9>, [](auto x, auto y) {
return x > y; // order is reversed!
});
BOOST_HANA_CONSTANT_CHECK(smallest == hana::int_c<-4>);
}

Syntactic sugar (maximum.by)

maximum can be called in a third way, which provides a nice syntax especially when working with the ordering combinator:

maximum.by(predicate, xs) == maximum(xs, predicate)
maximum.by(predicate) == maximum(-, predicate)

where maximum(-, predicate) denotes the partial application of maximum to predicate.

Example

// Copyright Louis Dionne 2013-2016
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
namespace hana = boost::hana;
int main() {
static_assert(
hana::maximum.by(hana::ordering(hana::length), hana::make_tuple(
hana::make_tuple(),
hana::make_tuple(1, '2'),
hana::make_tuple(3.3, nullptr, 4)
))
== hana::make_tuple(3.3, nullptr, 4)
, "");
}

Tag dispatching

Both the non-predicated version and the predicated versions of maximum are tag-dispatched methods, and hence they can be customized independently. One reason for this is that some structures are able to provide a much more efficient implementation of maximum when the less predicate is used. Here is how the different versions of maximum are dispatched:

maximum(xs, pred) -> maximum_pred_impl<tag of xs>::apply(xs, pred)

Also note that maximum.by is not tag-dispatched on its own, since it is just syntactic sugar for calling the corresponding maximum.

constexpr auto boost::hana::minimum

#include <boost/hana/fwd/minimum.hpp>

Initial value:
= [](auto&& xs[, auto&& predicate]) -> decltype(auto) {
return tag-dispatched;
}

Return the least element of a non-empty structure with respect to a predicate, by default less.Given a non-empty structure and an optional binary predicate (less by default), minimum returns the least element of the structure, i.e. an element which is less than or equal to every other element in the structure, according to the predicate.

If the structure contains heterogeneous objects, then the predicate must return a compile-time Logical. If no predicate is provided, the elements in the structure must be Orderable, or compile-time Orderable if the structure is heterogeneous.

Signature

Given a Foldable F, a Logical Bool and a predicate \( \mathtt{pred} : T \times T \to Bool \), minimum has the following signatures. For the variant with a provided predicate,

\[ \mathtt{minimum} : F(T) \times (T \times T \to Bool) \to T \]

for the variant without a custom predicate, T is required to be Orderable. The signature is then

\[ \mathtt{minimum} : F(T) \to T \]

Parameters
xsThe structure to find the least element of.
predicateA function called as predicate(x, y), where x and y are elements of the structure. predicate should be a strict weak ordering on the elements of the structure and its return value should be a Logical, or a compile-time Logical if the structure is heterogeneous.

Example

// Copyright Louis Dionne 2013-2016
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
namespace hana = boost::hana;
int main() {
// without a predicate
hana::minimum(hana::tuple_c<int, -1, 0, 2, -4, 6, 9>) == hana::int_c<-4>
);
// with a predicate
auto largest = hana::minimum(hana::tuple_c<int, -1, 0, 2, -4, 6, 9>, [](auto x, auto y) {
return x > y; // order is reversed!
});
BOOST_HANA_CONSTANT_CHECK(largest == hana::int_c<9>);
}

Syntactic sugar (minimum.by)

minimum can be called in a third way, which provides a nice syntax especially when working with the ordering combinator:

minimum.by(predicate, xs) == minimum(xs, predicate)
minimum.by(predicate) == minimum(-, predicate)

where minimum(-, predicate) denotes the partial application of minimum to predicate.

Example

// Copyright Louis Dionne 2013-2016
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
namespace hana = boost::hana;
int main() {
hana::minimum.by(hana::ordering(hana::length), hana::make_tuple(
hana::make_tuple(),
hana::make_tuple(1, '2'),
hana::make_tuple(3.3, nullptr, 4)
))
== hana::make_tuple()
);
}

Tag dispatching

Both the non-predicated version and the predicated versions of minimum are tag-dispatched methods, and hence they can be customized independently. One reason for this is that some structures are able to provide a much more efficient implementation of minimum when the less predicate is used. Here is how the different versions of minimum are dispatched:

minimum(xs, pred) -> minimum_pred_impl<tag of xs>::apply(xs, pred)

Also note that minimum.by is not tag-dispatched on its own, since it is just syntactic sugar for calling the corresponding minimum.

template<typename M >
constexpr auto boost::hana::monadic_fold_left

#include <boost/hana/fwd/monadic_fold_left.hpp>

Initial value:
= [](auto&& xs[, auto&& state], auto&& f) -> decltype(auto) {
return tag-dispatched;
}

Monadic left-fold of a structure with a binary operation and an optional initial reduction state.

Note
This assumes the reader to be accustomed to non-monadic left-folds as explained by hana::fold_left, and to have read the primer on monadic folds.

monadic_fold_left<M> is a left-associative monadic fold. Given a Foldable with linearization [x1, ..., xn], a function f and an optional initial state, monadic_fold_left<M> applies f as follows:

// with state
((((f(state, x1) | f(-, x2)) | f(-, x3)) | ...) | f(-, xn))
// without state
((((f(x1, x2) | f(-, x3)) | f(-, x4)) | ...) | f(-, xn))

where f(-, xk) denotes the partial application of f to xk, and | is just the operator version of the monadic chain.

When the structure is empty, one of two things may happen. If an initial state was provided, it is lifted to the given Monad and returned as-is. Otherwise, if the no-state version of the function was used, an error is triggered. When the stucture contains a single element and the no-state version of the function was used, that single element is lifted into the given Monad and returned as is.

Signature

Given a Monad M, a Foldable F, an initial state of tag S, and a function \( f : S \times T \to M(S) \), the signatures of monadic_fold_left<M> are

\[ \mathtt{monadic\_fold\_left}_M : F(T) \times S \times (S \times T \to M(S)) \to M(S) \]

for the version with an initial state, and

\[ \mathtt{monadic\_fold\_left}_M : F(T) \times (T \times T \to M(T)) \to M(T) \]

for the version without an initial state.

Template Parameters
MThe Monad representing the monadic context in which the fold happens. The return type of f must be in that Monad.
Parameters
xsThe structure to fold.
stateThe initial value used for folding. If the structure is empty, this value is lifted in to the M Monad and then returned as-is.
fA binary function called as f(state, x), where state is the result accumulated so far and x is an element in the structure. The function must return its result inside the M Monad.

Example

// Copyright Louis Dionne 2013-2016
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
#include <type_traits>
namespace hana = boost::hana;
auto builtin_common_t = hana::sfinae([](auto&& t, auto&& u) -> decltype(hana::type_c<
std::decay_t<decltype(true ? hana::traits::declval(t) : hana::traits::declval(u))>
>) { return {}; });
template <typename ...T>
struct common_type { };
template <typename T, typename U>
struct common_type<T, U>
: std::conditional_t<std::is_same<std::decay_t<T>, T>{} &&
std::is_same<std::decay_t<U>, U>{},
decltype(builtin_common_t(hana::type_c<T>, hana::type_c<U>)),
common_type<std::decay_t<T>, std::decay_t<U>>
>
{ };
template <typename T1, typename ...Tn>
struct common_type<T1, Tn...>
: decltype(hana::monadic_fold_left<hana::optional_tag>(
hana::tuple_t<Tn...>,
hana::type_c<std::decay_t<T1>>,
hana::sfinae(hana::metafunction<common_type>)
))
{ };
template <typename ...Ts>
using common_type_t = typename common_type<Ts...>::type;
static_assert(std::is_same<
common_type_t<char, short, char, short>,
int
>{}, "");
static_assert(std::is_same<
common_type_t<char, double, short, char, short, double>,
double
>{}, "");
static_assert(std::is_same<
common_type_t<char, short, float, short>,
float
>{}, "");
static_assert(
hana::sfinae(hana::metafunction<common_type>)(
hana::type_c<int>, hana::type_c<int>, hana::type_c<int*>
) == hana::nothing
, "");
int main() { }
template<typename M >
constexpr auto boost::hana::monadic_fold_right

#include <boost/hana/fwd/monadic_fold_right.hpp>

Initial value:
= [](auto&& xs[, auto&& state], auto&& f) -> decltype(auto) {
return tag-dispatched;
}

Monadic right-fold of a structure with a binary operation and an optional initial reduction state.

Note
This assumes the reader to be accustomed to non-monadic right-folds as explained by hana::fold_right, and to have read the primer on monadic folds.

monadic_fold_right<M> is a right-associative monadic fold. Given a structure containing x1, ..., xn, a function f and an optional initial state, monadic_fold_right<M> applies f as follows

// with state
(f(x1, -) | (f(x2, -) | (f(x3, -) | (... | f(xn, state)))))
// without state
(f(x1, -) | (f(x2, -) | (f(x3, -) | (... | f(xn-1, xn)))))

where f(xk, -) denotes the partial application of f to xk, and | is just the operator version of the monadic chain. It is worth noting that the order in which the binary function should expect its arguments is reversed from monadic_fold_left<M>.

When the structure is empty, one of two things may happen. If an initial state was provided, it is lifted to the given Monad and returned as-is. Otherwise, if the no-state version of the function was used, an error is triggered. When the stucture contains a single element and the no-state version of the function was used, that single element is lifted into the given Monad and returned as is.

Signature

Given a Monad M, a Foldable F, an initial state of tag S, and a function \( f : T \times S \to M(S) \), the signatures of monadic_fold_right<M> are

\[ \mathtt{monadic\_fold\_right}_M : F(T) \times S \times (T \times S \to M(S)) \to M(S) \]

for the version with an initial state, and

\[ \mathtt{monadic\_fold\_right}_M : F(T) \times (T \times T \to M(T)) \to M(T) \]

for the version without an initial state.

Template Parameters
MThe Monad representing the monadic context in which the fold happens. The return type of f must be in that Monad.
Parameters
xsThe structure to fold.
stateThe initial value used for folding. If the structure is empty, this value is lifted in to the M Monad and then returned as-is.
fA binary function called as f(x, state), where state is the result accumulated so far and x is an element in the structure. The function must return its result inside the M Monad.

Example

// Copyright Louis Dionne 2013-2016
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
namespace hana = boost::hana;
int main() {
BOOST_HANA_CONSTEXPR_LAMBDA auto safe_div = [](auto x, auto y) {
return hana::eval_if(y == hana::int_c<0>,
hana::make_lazy(hana::nothing),
[=](auto _) {
return hana::just(_(x) / y);
}
);
};
// with an initial state
hana::monadic_fold_right<hana::optional_tag>(
hana::tuple_c<int, 1000, 8, 4>, hana::int_c<2>, safe_div
)
==
hana::just(hana::int_c<1000> / (hana::int_c<8> / (hana::int_c<4> / hana::int_c<2>)))
);
hana::monadic_fold_right<hana::optional_tag>(
hana::tuple_c<int, 1000, 8, 4>, hana::int_c<0>, safe_div
)
==
hana::nothing
);
// without an initial state
hana::monadic_fold_right<hana::optional_tag>(
hana::tuple_c<int, 1000, 8, 4, 2>, safe_div
)
==
hana::just(hana::int_c<1000> / (hana::int_c<8> / (hana::int_c<4> / hana::int_c<2>)))
);
hana::monadic_fold_right<hana::optional_tag>(
hana::tuple_c<int, 1000, 8, 4, 0>, safe_div
)
==
hana::nothing
);
}
constexpr auto boost::hana::product = see documentation

#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,.

product<R>(xs) = fold_left(xs, one<R or inferred Ring>(), mult)
product<> = product<integral_constant_tag<int>>

For numbers, this will just compute the product of the numbers in the xs structure.

Note
The elements of the structure are not actually required to be in the same Ring, but it must be possible to perform 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.
See the documentation for sum to understand why the Ring must sometimes be specified explicitly.

Example

// Copyright Louis Dionne 2013-2016
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
namespace hana = boost::hana;
int main() {
hana::product<>(hana::make_range(hana::int_c<1>, hana::int_c<6>)) == hana::int_c<1 * 2 * 3 * 4 * 5>
);
hana::product<>(hana::make_tuple(1, hana::int_c<3>, hana::long_c<-5>, 9)) == 1 * 3 * -5 * 9
);
hana::product<unsigned long>(hana::make_tuple(2ul, 3ul)) == 6ul
);
}
constexpr auto boost::hana::reverse_fold

#include <boost/hana/fwd/reverse_fold.hpp>

Initial value:
= [](auto&& xs[, auto&& state], auto&& f) -> decltype(auto) {
return fold_right(forwarded(xs), forwarded(state), flip(forwarded(f)));
}
constexpr auto fold_right
Right-fold of a structure using a binary operation and an optional initial reduction state...
Definition: fold_right.hpp:73
constexpr auto flip
Invoke a function with its two first arguments reversed.
Definition: flip.hpp:31

Equivalent to reverse_fold in Boost.Fusion and Boost.MPL.This method has the same semantics as reverse_fold in Boost.Fusion and Boost.MPL, with the extension that an initial state is not required. This method is equivalent to fold_right, except that the accumulating function must take its arguments in reverse order, to match the order used in Fusion. In other words,.

reverse_fold(sequence, state, f) == fold_right(sequence, state, flip(f))
reverse_fold(sequence, f) == fold_right(sequence, flip(f))
Note
This method is a convenience alias to fold_right. As an alias, reverse_fold is not tag-dispatched on its own and fold_right should be customized instead.

Signature

Given a Foldable F and an optional initial state of tag S, the signatures for reverse_fold are

\[ \mathtt{reverse\_fold} : F(T) \times S \times (S \times T \to S) \to S \]

for the variant with an initial state, and

\[ \mathtt{reverse\_fold} : F(T) \times (T \times T \to T) \to T \]

for the variant without an initial state.

Parameters
xsThe structure to fold.
stateThe initial value used for folding.
fA binary function called as f(state, x), where state is the result accumulated so far and x is an element in the structure. For reverse folds without an initial state, the function is called as f(x1, x2), where x1 and x2 are elements of the structure.

Example

// Copyright Louis Dionne 2013-2016
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
#include <sstream>
#include <string>
namespace hana = boost::hana;
auto to_string = [](auto x) {
std::ostringstream ss;
ss << x;
return ss.str();
};
int main() {
auto f = [=](std::string s, auto element) {
return "f(" + s + ", " + to_string(element) + ")";
};
// With an initial state
hana::reverse_fold(hana::make_tuple(1, '2', 3.0, 4), "5", f)
==
"f(f(f(f(5, 4), 3), 2), 1)"
);
// Without an initial state
hana::reverse_fold(hana::make_tuple(1, '2', 3.0, 4, "5"), f)
==
"f(f(f(f(5, 4), 3), 2), 1)"
);
}
constexpr auto boost::hana::size = hana::length

#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 tag-dispatched on its own and length should be customized instead.

Example

// Copyright Louis Dionne 2013-2016
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
namespace hana = boost::hana;
int main() {
BOOST_HANA_CONSTANT_CHECK(hana::size(hana::make_tuple()) == hana::size_c<0>);
BOOST_HANA_CONSTANT_CHECK(hana::size(hana::make_tuple(1, '2', 3.0)) == hana::size_c<3>);
BOOST_HANA_CONSTANT_CHECK(hana::size(hana::nothing) == hana::size_c<0>);
BOOST_HANA_CONSTANT_CHECK(hana::size(hana::just('x')) == hana::size_c<1>);
}
constexpr auto boost::hana::sum = see documentation

#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,.

sum<M>(xs) = fold_left(xs, zero<M or inferred Monoid>(), plus)
sum<> = sum<integral_constant_tag<int>>

For numbers, this will just compute the sum of the numbers in the xs structure.

Note
The elements of the structure are not actually required to be in the same Monoid, but it must be possible to perform 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.

Why must we sometimes specify the Monoid by using sum<M>?

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::ranges 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 non-parameterized tags, but we have no good solution for now.

Example

// Copyright Louis Dionne 2013-2016
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
namespace hana = boost::hana;
BOOST_HANA_CONSTANT_CHECK(hana::sum<>(hana::make_range(hana::int_c<1>, hana::int_c<6>)) == hana::int_c<15>);
static_assert(hana::sum<>(hana::make_tuple(1, hana::int_c<3>, hana::long_c<-5>, 9)) == 8, "");
static_assert(hana::sum<unsigned long>(hana::make_tuple(1ul, 3ul)) == 4ul, "");
int main() { }
constexpr auto boost::hana::unpack

#include <boost/hana/fwd/unpack.hpp>

Initial value:
= [](auto&& xs, auto&& f) -> decltype(auto) {
return tag-dispatched;
}

Invoke a function with the elements of a Foldable as arguments.Given a function and a foldable structure whose length can be known at compile-time, 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 compile-time, 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 compile-time.

To create a function that accepts a foldable instead of variadic arguments, see fuse instead.

Parameters
xsThe structure to expand into the function.
fA function to be invoked as f(x...), where x... are the elements of the structure as-if they had been linearized with to<tuple_tag>.

Example

// Copyright Louis Dionne 2013-2016
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
namespace hana = boost::hana;
int main() {
BOOST_HANA_CONSTEXPR_LAMBDA auto add = [](auto x, auto y, auto z) {
return x + y + z;
};
BOOST_HANA_CONSTEXPR_CHECK(hana::unpack(hana::make_tuple(1, 2, 3), add) == 6);
}

Rationale: unpack's name and parameter order

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

std::apply([](auto ...args) {
use(args...);
}, tuple);

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

hana::unpack(tuple, [](auto ...args) {
use(args...);
});

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.