这次研究基于的项目是 Github 上的 conduit，项目作者应该是在 C++20 尚未正式颁布时就写好了，里面包含的头文件都是 <expriment/coroutine> 这样的格式。笔者用正式标准稍作改写，发布在自己的 Gitee 上，文末有链接。
先看示例主函数：
int main() {
auto primes = range()
>> map([](auto i) {return (3 + i * 2); })
>> 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 个素数，我们关注的重点不是这个算法如何（其实效率还是很高的），而是看它的设计思想，值得学习的主要有两点：
- 协程
- 函数式编程
下面一一介绍。
协程
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，以提供自定义的内存分配和回收操作。源项目中有示例，这里简化去掉了。
有了 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 项目：conduit
笔者改写后的源码：conduit.cpp
欢迎关注微信公众号，一起交流
