conduit: 现代 C++ 的协程与函数式编程
这次研究基于的项目是 Github 上的 conduit，项目作者应该是在 C++20 尚未正式颁布时就写好了，里面包含的头文件都是 <expriment/coroutine> 这样的。笔者根据正式标准稍作改写后，公布在自己的 Gitee 仓库上，文末有链接。
先看示例主函数：
int main() {auto primes = range() //seq<ulong>: 0, 1, 2, 3...>> map([](auto i) {return (3 + i * 2); }) //3,5,7,9...>> flatMap([primeVector = std::vector<int>()](auto c) mutable {return primeVector>> take(primeVector.size())>> find([c](auto p) { return c % p == 0; })>> count()>> orElse(just(c))>> find([](auto x) { return x; })>> forEach([&](auto p) { primeVector.push_back(p); });})>> startsWith(just(2))>> take(10);for (auto n : primes)std::cout << n << std::endl;return 0;}
程序的功能就是找出前 10 个素数，我们关注的重点不是这个算法如何（其实效率还是很高的），而是看它的设计思想，值得学习的主要有两点：
1.协程2.函数式编程
下面一一介绍。
协程
C++20 终于引入了协程，官方示例中有如下的例子：
generator<int> iota(int n = 0) {while(true) co_yield n++;}lazy<int> f() {co_return 7;}
我原来以为 generator<T> 和 lazy<T> 都是标准库提供的类，后来才知道不是，只能新写一个：
template<std::movable T>class seq {public:struct promise_type {seq<T> get_return_object() { return seq{ Handle::from_promise(*this) }; }static std::suspend_always initial_suspend() noexcept { return {}; }static std::suspend_always final_suspend() noexcept { return {}; }static void return_void() noexcept {}[[noreturn]] static void unhandled_exception() { throw; }std::suspend_always yield_value(T value) noexcept {current_value = std::move(value);return {};}std::optional<T> current_value;};using Handle = std::coroutine_handle<promise_type>;class iterator {public:void operator++() { m_coroutine.resume(); }const T& operator*() const { return *m_coroutine.promise().current_value; }bool operator==(std::default_sentinel_t) const { return !m_coroutine || m_coroutine.done(); }explicit iterator(const Handle coroutine) : m_coroutine{ coroutine } {}private:Handle m_coroutine;};explicit seq(const Handle coroutine) : m_coroutine{ coroutine } {}seq() = default;~seq() { if (m_coroutine) m_coroutine.destroy(); }seq(const seq&) = delete;seq(seq&& other) noexcept : m_coroutine{ other.m_coroutine } { other.m_coroutine = {}; }seq& operator=(const seq&) = delete;seq& operator=(seq&& other) noexcept {if (this != &other) {if (m_coroutine)m_coroutine.destroy();m_coroutine = other.m_coroutine;other.m_coroutine = {};}return *this;}iterator begin() {if (m_coroutine)m_coroutine.resume();return iterator{ m_coroutine };}std::default_sentinel_t end() { return {}; }private:Handle m_coroutine;};
这个类在源项目中也有，但这个版本更加简明一些。其实这个类的主体代码，都是从官方文档上参考来的，基本上不需要作什么修改，就能适用于大多数场合。所以非常奇怪，为什么标准库不直接提供一个能拿来就用的呢？
这个类中，promise_type 嵌套类可以自定义 operator new 和 operator delete，以提供自定义的内存分配和回收操作。源项目 conduit 中有示例，这里简化去掉了。
有了 seq 类之后，我们就可以用它作为数据传输载体了：
template<typename T = unsigned long>auto range(T b = 0) -> seq<T> {while (true) {co_yield b;++b;}};
这就是主程序中的 range() 函数，很简单，就是从零开始依次生成整数序列。那么它又是如何逐步转化成素数序列的呢？
函数式编程
首先定义一个概念和两个辅助函数：
template<typename R>concept sequence = requires(R & r) { r.begin(); r.end(); };template<typename T>T id(T const& x) { return x; }template<typename T>auto first(T&& xs) -> decltype(id(*xs.begin())) { return *xs.begin(); }
sequence 是个序列，满足条件是只要它有 begin、end 两个成员函数即可。因此上面的 seq 类，以及标准库中的常用容器，都是符合它的。
下面看 map 函数的定义，主函数中就是使用它完成第一步转换的：
namespace detail {auto map = [](sequence auto xs, auto f) -> seq<decltype(id(f(first(xs))))> {for (auto x : xs)co_yield f(x);};}auto map = [](auto f) {return [f](sequence auto&& xs) {return detail::map(std::forward<decltype(xs)>(xs), f);};};
这就是典型的函数式编程思想，注意 map 在调用的时候传入的参数是一个 lambda 函数，然后这里的两级函数返回的都是一个 lambda 函数。也就是说，传入不同的功能函数，就能让 map 去执行不同的任务。
注意我将 xs 参数添加了 sequence 约束，但是对 f 没有加，函数返回值类型也是使用 decltype 去推导。这是因为函数参数可以返回各种不同类型的值，因此 map 函数返回的类型，在设计时是无法知道的，只好交给编译器去自动推导了。
再看 flatMap 函数。与 map 函数的区别是，map 对每个元素只返回一个结果，而 flatMap 则对每个元素返回一个集合，再逐个 yield：
namespace detail {auto flatMap = [](sequence auto xs, auto f) -> seq<decltype(first(f(first(xs))))> {for (auto x : xs) //每个元素for (auto&& y : f(x)) //调用函数之后生成一个序列co_yield std::move(y); //再逐个yield};}auto flatMap = [](auto&& f) {return [f](sequence auto&& xs) {return detail::flatMap(std::forward<decltype(xs)>(xs), f);};};
主函数中就是使用 flatMap，对每个元素检查其是否为素数，如果是就 yield 并加入已有素数序列，如果不是那么空集合自然不会 yield，这样就可以进行过滤。
以下是 flatMap 函数所使用的 lambda 函数参数，添加了详细注释：
[primeVector = std::vector<int>()](auto c) mutable { //确保向量可修改return primeVector //已找到的质数，vector（生存期同 flatMap）可以用>>>> take(primeVector.size()) //逐一拿出来尝试>> find([c](auto p) { return c % p == 0; }) //找到一个就 yield & break>> count() //能整除就 yield 其序号（默认返回零）>> orElse(just(c)) //左侧无元素就 yield 右侧。结果要么 0，要么 c>> find([](auto x) { return x; }) //再排除掉零，剩下要么 c，要么空>> forEach([&](auto p) { primeVector.push_back(p); }); //非空则加进向量}
首先，注意函数声明了 mutable，这是因为 primeVector 的值是需要改变的，如果不加 mutable，在 push_back 的地方就会出现编译错误。
注意到主函数和这个 lambda 函数里都大量使用了 operator >>，它是重载了的，相当于管道操作符：
template <sequence Xs, typename F>auto operator >> (Xs&& xs, F&& f) {return f(std::forward<decltype(xs)>(xs));}
Xs 加了 sequence 约束，由于 vector 容器支持 begin、end 函数，因此当然也是可用的。
take、find、count、forEach 这些函数基本上一看就知道做什么的，不再解释了。just 和 orElse 相对不常见。
just 用于直接从元素生成序列：
template<typename...Xs>auto just(Xs...xs) {if constexpr (sizeof...(xs) > 0) {using T = std::common_type_t<decltype(xs)...>;return [=]() -> seq<T> {T data[] = { (T)xs... };for (auto x : data)co_yield x;};} else {return []() -> seq<int> { co_return; };}}
orElse 则是判断给定序列是否为空，不为空则逐一 yield，否则调用 lambda 函数参数得到新序列：
namespace detail {template<sequence Xs, typename Xsf>auto orElse(Xs xs, Xsf xsf) -> seq<decltype(first(xs))> {bool hasElements = false;for (auto x : xs) {hasElements = true;co_yield x;}if (!hasElements) {for (auto x : xsf())co_yield x;}}}auto orElse = [](auto xsf) {return [xsf](sequence auto&& xs) {return detail::orElse(std::forward<decltype(xs)>(xs), xsf);};};
最后看 startsWith，其实就是一个连接，将给定序列接在已有序列的头部：
namespace detail {template<sequence Xs, sequence Ys>auto concat(Xs xs, Ys ys) -> seq<decltype(first(xs))> {for (auto x : xs)co_yield x;for (auto x : ys)co_yield x;}}auto startsWith = [](auto...xsf) {return [=](sequence auto&& ys) mutable {return detail::concat(xsf()..., std::forward<decltype(ys)>(ys));};};
本文相关 Github 项目：https://github.com/LoopPerfect/conduit
笔者改写后的源码：https://gitee.com/sunwaywei/study-cpp/blob/master/conduit.cpp