可折叠

描述

Foldable 概念表示可以归约为单个值的数据结构。

一般来说，折叠指的是将复杂结构总结为单个值的理念，方法是连续应用二元运算，将结构的两个元素归约为单个值。折叠有很多种形式；左折叠、右折叠、带或不带初始归约状态的折叠，以及它们的单子变体。此概念能够表达所有这些折叠变体。

另一种看待 Foldable 的方式是将其视为支持内部迭代并能够累积结果的数据结构。通过内部迭代，我们的意思是循环控制掌握在结构手中，而不是调用者。因此，结构决定何时停止迭代，通常是在整个结构被消耗时。由于 C++ 是一种急切语言，因此这要求 Foldable 结构是有限的，否则需要无限循环来消耗整个结构。

注意

虽然 Foldable 只适用于有限结构这一事实与 Haskell 中 Foldable 的定义相比似乎过于严格，但对概念进行更细粒度的分离应该可以缓解此问题。有关迭代可能无限的数据结构，请参见 Iterable 概念。有关搜索可能无限的数据结构，请参见 Searchable 概念。

最小完整定义

fold_left 或 unpack

但是，请注意，通过 unpack 提供的最小完整定义在编译时效率将比通过 fold_left 提供的定义高得多。

具体模型

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

<tt>Foldable</tt> 的线性化

直观地说，对于 Foldable 结构 xs，xs 的线性化是 xs 中所有元素的序列，就像它们被放入列表中一样

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

请注意，对于有限的 Foldable，始终可以通过设置以下内容来生成这样的线性化

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

对于 [] 和 prepend 的适当定义。线性化的概念可用于表达 Foldable 结构的各种属性，并在整个文档中使用。另请注意，Iterable 定义了此功能的扩展版本，允许使用无限结构。

编译时可折叠

编译时 Foldable 是一个 Foldable，其总长度在编译时已知。换句话说，它是一个 Foldable，其 length 方法返回无符号整型类型的 Constant。当折叠编译时 Foldable 时，可以展开折叠，因为算法的最终步骤数在编译时已知。

此外，unpack 方法仅对编译时 Foldable 可用。这是因为 unpack 的返回类型取决于结构中对象的个数。因此，能够在编译时解析 unpack 的返回类型也要求结构的长度在编译时已知。

在当前版本的库中，仅支持编译时 Foldable。虽然从理论上讲也可以支持运行时 Foldable，但有效地做到这一点需要更多的研究。

提供的转换为 <tt>Sequence</tt>

给定一个标签 S，它是一个 Sequence，其标签是 Foldable 概念的模型的对象可以转换为标签 S 的对象。换句话说，Foldable 可以转换为 Sequence S，只需获取 Foldable 的线性化并使用它创建序列即可。更具体地说，给定一个 Foldable xs，其线性化为 [x1, ..., xn] 和一个 Sequence 标签 S，to<S>(xs) 等效于 make<S>(x1, ..., xn)。

// 版权所有 Louis Dionne 2013-2017
// 根据 Boost 软件许可证版本 1.0 分发。
// （参见随附文件 LICENSE.md 或复制到 https://boost.ac.cn/LICENSE_1_0.txt）
 
#include <boost/hana/assert.hpp>
#include <boost/hana/core/to.hpp>
#include <boost/hana/equal.hpp>
#include <boost/hana/integral_constant.hpp>
#include <boost/hana/optional.hpp>
#include <boost/hana/range.hpp>
#include <boost/hana/tuple.hpp>
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());
 
    BOOST_HANA_CONSTANT_CHECK(
hana::to<hana::tuple_tag>(hana::make_range(hana::int_c<3>, hana::int_c<6>))
            ==
hana::tuple_c<int, 3, 4, 5>
    );
}

内置数组的免费模型

已知大小的内置数组可以像同构元组一样折叠。但是，请注意，内置数组不能成为超过 Foldable 的东西（例如 Iterable），因为它们不能为空，也不能从函数中返回。

单子折叠入门

单子折叠是一种折叠，其中对二元函数的后续调用与相应单子的单子 chain 运算符链接。这允许在自定义单子上下文中折叠结构。例如，使用 hana::optional 单子执行单子折叠将要求二元函数将结果作为 hana::optional 返回，并且只要累积步骤之一失败（即返回 nothing），折叠就会中止并返回 nothing。但是，如果所有归约步骤都成功，则会返回 just 结果。当然，不同的单子会导致不同的效果。

变量
constexpr auto	boost::hana::count
	返回结构中与给定值相等的元素数量。更多...
constexpr auto	boost::hana::count_if
	返回结构中满足 predicate 的元素数量。更多...
constexpr auto	boost::hana::fold = fold_left
	等效于 fold_left；为了方便起见而提供。更多...
constexpr auto	boost::hana::for_each
	对可折叠的每个元素执行操作，每次都丢弃结果。更多...
constexpr auto	boost::hana::fuse
	将接受多个参数的函数转换为可以使用编译时 Foldable 调用的函数。更多...
constexpr auto	boost::hana::length
	返回可折叠结构中的元素数量。更多...
constexpr auto	boost::hana::product = 请参阅文档
	计算结构中数字的乘积。更多...
constexpr auto	boost::hana::size = hana::length
	等效于 length；为了与标准库保持一致而提供。更多...
constexpr auto	boost::hana::sum = 请参阅文档
	计算结构中数字的总和。更多...
constexpr auto	boost::hana::unpack
	使用可折叠的元素作为参数来调用函数。更多...

变量文档

count

constexpr auto boost::hana::count

constexpr

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

初始值

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

返回结构中与给定值相等的元素数量。

给定一个可折叠结构 xs 和一个值 value，count 返回一个无符号整数，或其 Constant，表示与 value 相等的 xs 元素的数量。为了使此方法定义良好，结构的所有元素都必须与给定值具有可比性。

参数

xs	要计算其元素的结构。
value	与结构中每个元素进行比较的值。与该值相等的元素会被计算，其他元素不会。

示例

// 版权所有 Louis Dionne 2013-2017
// 根据 Boost 软件许可证版本 1.0 分发。
// （参见随附文件 LICENSE.md 或复制到 https://boost.ac.cn/LICENSE_1_0.txt）
 
#include <boost/hana/assert.hpp>
#include <boost/hana/count.hpp>
#include <boost/hana/equal.hpp>
#include <boost/hana/integral_constant.hpp>
#include <boost/hana/tuple.hpp>
#include <boost/hana/type.hpp>
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>);
}

count_if

constexpr auto boost::hana::count_if

constexpr

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

初始值

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

返回结构中满足 predicate 的元素数量。

具体来说，返回一个无符号整型对象，或一个包含此类对象的 Constant，它表示结构中满足给定 predicate 的元素数量。

参数

xs	要计算其元素的结构。
predicate	一个函数，调用方式为 predicate(x)，其中 x 是结构中的一个元素，并返回一个 Logical，表示是否应该计算 x。

例子

// 版权所有 Louis Dionne 2013-2017
// 根据 Boost 软件许可证版本 1.0 分发。
// （参见随附文件 LICENSE.md 或复制到 https://boost.ac.cn/LICENSE_1_0.txt）
 
#include <boost/hana/assert.hpp>
#include <boost/hana/count_if.hpp>
#include <boost/hana/equal.hpp>
#include <boost/hana/ext/std/integral_constant.hpp>
#include <boost/hana/integral_constant.hpp>
#include <boost/hana/mod.hpp>
#include <boost/hana/not_equal.hpp>
#include <boost/hana/tuple.hpp>
#include <boost/hana/type.hpp>
 
#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>);
}

fold

constexpr auto boost::hana::fold = fold_left

constexpr

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

等价于 fold_left；为了方便提供。

fold 等价于 fold_left。但是，它本身没有进行标签分派，因为它只是 fold_left 的别名。还要注意，fold 可以带或不带初始状态调用，就像 fold_left 一样

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

例子

// 版权所有 Louis Dionne 2013-2017
// 根据 Boost 软件许可证版本 1.0 分发。
// （参见随附文件 LICENSE.md 或复制到 https://boost.ac.cn/LICENSE_1_0.txt）
 
#include <boost/hana/assert.hpp>
#include <boost/hana/fold.hpp>
#include <boost/hana/tuple.hpp>
 
#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) + ")";
    };
 
    // 带有初始状态
    BOOST_HANA_RUNTIME_CHECK(
        hana::fold(hana::make_tuple(2, '3', 4, 5.0), "1", f)
            ==
        "f(f(f(f(1, 2), 3), 4), 5)"
    );
 
    // 没有初始状态
    BOOST_HANA_RUNTIME_CHECK(
        hana::fold(hana::make_tuple("1", 2, '3', 4, 5.0), f)
            ==
        "f(f(f(f(1, 2), 3), 4), 5)"
    );
}

for_each

constexpr auto boost::hana::for_each

constexpr

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

初始值

= [](auto&& xs, auto&& f) -> void {
标签分派；
    }

对可折叠的每个元素执行一个操作，每次都丢弃结果。

迭代从左到右进行，即与使用 fold_left 时顺序相同。如果结构不是有限的，则此方法将不会终止。

参数

xs	要迭代的结构。
f	一个函数，对结构的每个元素 x 调用 f(x)。f(x) 的结果（无论是什么）都将被忽略。

例子

// 版权所有 Louis Dionne 2013-2017
// 根据 Boost 软件许可证版本 1.0 分发。
// （参见随附文件 LICENSE.md 或复制到 https://boost.ac.cn/LICENSE_1_0.txt）
 
#include <boost/hana/assert.hpp>
#include <boost/hana/for_each.hpp>
#include <boost/hana/tuple.hpp>
 
#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 ");
}

fuse

constexpr auto boost::hana::fuse

constexpr

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

初始值

= [](auto&& f) {
        return [perfect-capture](auto&& xs) -> decltype(auto) {
            return unpack(forwarded(xs), forwarded(f));
        };
    }

将一个接受多个参数的函数转换为一个可以用编译时 Foldable 调用的函数。

此函数作为调用 unpack 的另一种方式提供，以便于使用。具体来说，fuse(f) 是一个函数，使得

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

其中 x... 是可折叠结构中的元素。当想要创建一个接受尚未知的可折叠结构的函数时，此函数很有用。

注意

此函数没有进行标签分派；请改用自定义 unpack。

例子

// 版权所有 Louis Dionne 2013-2017
// 根据 Boost 软件许可证版本 1.0 分发。
// （参见随附文件 LICENSE.md 或复制到 https://boost.ac.cn/LICENSE_1_0.txt）
 
#include <boost/hana/assert.hpp>
#include <boost/hana/fuse.hpp>
#include <boost/hana/tuple.hpp>
namespace hana = boost::hana;
 
 
auto tie = [](auto& ...vars) {
    return hana::fuse([&vars...](auto ...values) {
        // 使用初始化列表来排序赋值。
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);
}

length

constexpr auto boost::hana::length

constexpr

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

初始值

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

返回可折叠结构中的元素数量。

给定一个 Foldable xs，length(xs) 必须返回一个无符号整型对象，或一个包含此类对象的 IntegralConstant，它表示结构中的元素数量。

注意

由于库目前仅支持编译时 Foldable，因此 length 必须始终返回一个 IntegralConstant。

例子

// 版权所有 Louis Dionne 2013-2017
// 根据 Boost 软件许可证版本 1.0 分发。
// （参见随附文件 LICENSE.md 或复制到 https://boost.ac.cn/LICENSE_1_0.txt）
 
#include <boost/hana/assert.hpp>
#include <boost/hana/equal.hpp>
#include <boost/hana/integral_constant.hpp>
#include <boost/hana/length.hpp>
#include <boost/hana/optional.hpp>
#include <boost/hana/tuple.hpp>
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>);
}

product

constexpr auto boost::hana::product = 请参见文档

constexpr

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

计算结构中数字的乘积。

更一般地，product 将接受任何包含形成环的对象的可折叠结构，并使用环的二元运算对其进行归约。折叠的初始状态是环运算的单位元。有时需要指定要使用的环；这可以通过使用 product<R> 来实现。如果没有指定环，则结构将使用其包含的元素形成的环（如果知道），否则使用 integral_constant_tag<int>。因此，

product<R>(xs) = fold_left(xs, one<R 或推断出的环>(), mult)
product<> = product<integral_constant_tag<int>>

对于数字，这将只计算结构 xs 中数字的乘积。

注意

结构的元素实际上不需要位于同一个环中，但必须能够对结构的任意两个相邻元素执行 mult 操作，这要求每对相邻元素至少具有一个共同的环嵌入。此处使用的“相邻”的含义是指，如果结构 x 和 y 的两个元素在该结构的线性化中是相邻的，则它们就是相邻的，如 Iterable 概念中所述。

请参阅 sum 的文档，了解为什么有时必须显式指定环。

示例

// 版权所有 Louis Dionne 2013-2017
// 根据 Boost 软件许可证版本 1.0 分发。
// （参见随附文件 LICENSE.md 或复制到 https://boost.ac.cn/LICENSE_1_0.txt）
 
#include <boost/hana/assert.hpp>
#include <boost/hana/equal.hpp>
#include <boost/hana/integral_constant.hpp>
#include <boost/hana/product.hpp>
#include <boost/hana/range.hpp>
#include <boost/hana/tuple.hpp>
namespace hana = boost::hana;
 
 
int main() {
    BOOST_HANA_CONSTANT_CHECK(
hana::product<>(hana::make_range(hana::int_c<1>, hana::int_c<6>)) == hana::int_c<1 * 2 * 3 * 4 * 5>
    );
 
    BOOST_HANA_CONSTEXPR_CHECK(
hana::product<>(hana::make_tuple(1, hana::int_c<3>, hana::long_c<-5>, 9)) == 1 * 3 * -5 * 9
    );
 
    BOOST_HANA_CONSTEXPR_CHECK(
hana::product<unsigned long>(hana::make_tuple(2ul, 3ul)) == 6ul
    );
}

size

constexpr auto boost::hana::size = hana::length

constexpr

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

等效于 length；为了与标准库保持一致而提供。

此方法是 length 的别名，为了方便和与标准库保持一致而提供。作为别名，size 本身不会进行标签分派，而应自定义 length。

示例

// 版权所有 Louis Dionne 2013-2017
// 根据 Boost 软件许可证版本 1.0 分发。
// （参见随附文件 LICENSE.md 或复制到 https://boost.ac.cn/LICENSE_1_0.txt）
 
#include <boost/hana/assert.hpp>
#include <boost/hana/equal.hpp>
#include <boost/hana/integral_constant.hpp>
#include <boost/hana/optional.hpp>
#include <boost/hana/size.hpp>
#include <boost/hana/tuple.hpp>
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>);
}

sum

constexpr auto boost::hana::sum = 请参阅文档

constexpr

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

计算结构中数字的总和。

更一般地，sum 将接受任何包含形成幺半群的对象的可折叠结构，并使用幺半群的二元运算对其进行归约。折叠的初始状态是幺半群的单位元。有时需要指定要使用的幺半群；这可以通过使用 sum<M> 来实现。如果没有指定幺半群，则结构将使用其包含的元素形成的幺半群（如果知道），否则使用 integral_constant_tag<int>。因此，

sum<M>(xs) = fold_left(xs, zero<M 或推断出的幺半群>(), plus)
sum<> = sum<integral_constant_tag<int>>

对于数字，这将只计算结构 xs 中数字的总和。

注意

结构的元素实际上不需要位于同一个幺半群中，但必须能够对结构的任意两个相邻元素执行 plus 操作，这要求每对相邻元素至少具有一个共同的幺半群嵌入。此处使用的“相邻”的含义是指，如果结构 x 和 y 的两个元素在该结构的线性化中是相邻的，则它们就是相邻的，如 Iterable 概念中所述。

为什么有时必须使用 sum<M> 来指定 Monoid？

这是因为像 tuple_tag 这样的序列标签（根据设计）没有参数化。因此，我们不知道序列中包含什么类型的对象，所以我们无法知道当序列为空时应该返回哪种类型的 0 值。因此，必须显式指定空情况下要返回的 0 的类型。其他可折叠结构（如 hana::range）将忽略建议的幺半群，因为它们知道其包含的对象的标签。这种不一致的行为是当前设计中非参数化标签的限制，但我们目前没有好的解决方案。

示例

// 版权所有 Louis Dionne 2013-2017
// 根据 Boost 软件许可证版本 1.0 分发。
// （参见随附文件 LICENSE.md 或复制到 https://boost.ac.cn/LICENSE_1_0.txt）
 
#include <boost/hana/assert.hpp>
#include <boost/hana/equal.hpp>
#include <boost/hana/integral_constant.hpp>
#include <boost/hana/range.hpp>
#include <boost/hana/sum.hpp>
#include <boost/hana/tuple.hpp>
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() { }

unpack

constexpr auto boost::hana::unpack

constexpr

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

初始值

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

使用 Foldable 的元素作为参数调用函数。

给定一个函数和一个可折叠结构（其长度可以在编译时知道），unpack 将使用该结构的内容调用该函数。换句话说，unpack(xs, f) 等效于 f(x...)，其中 x... 是结构的元素。结构的长度必须在编译时知道，因为要编译的 f 的 operator() 版本取决于其调用的参数数量，而这必须在编译时知道。

要创建接受可折叠结构而不是可变参数的函数，请参阅 fuse。

参数

xs	要扩展到函数中的结构。
f	一个要作为 f(x...) 调用的函数，其中 x... 是结构的元素，就像它们已使用 to<tuple_tag> 线性化一样。

示例

// 版权所有 Louis Dionne 2013-2017
// 根据 Boost 软件许可证版本 1.0 分发。
// （参见随附文件 LICENSE.md 或复制到 https://boost.ac.cn/LICENSE_1_0.txt）
 
#include <boost/hana/assert.hpp>
#include <boost/hana/config.hpp>
#include <boost/hana/tuple.hpp>
#include <boost/hana/unpack.hpp>
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);
}

理由：unpack 的名称和参数顺序

有人建议几次将 unpack 重命名为 apply，并将参数顺序反转以匹配 提议的 std::apply 函数。但是，名称 apply 已用于表示正常的函数应用，这种用法与 Boost MPL 库以及世界其他地方（尤其是函数式编程社区）保持一致。此外，此库的作者认为提议的 std::apply 既有不幸的名称，也有不幸的参数顺序。实际上，将函数作为第一个参数意味着使用带有 lambda 函数的 std::apply 如下所示

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

这无疑是丑陋的，因为最后一行上的 , tuple) 部分。另一方面，将函数作为第二个参数允许编写

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

看起来好多了。由于这些观察结果，此库的作者认为有理由使用 unpack 而不是 apply，并使用合理的参数顺序。