65.9K
CodeProject 正在变化。 阅读更多。
Home

C++11 中的惰性流实现

David Serrano Martínez
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.87/5 (21投票s)

2012年12月21日

CPOL

9分钟阅读

viewsIcon

46719

downloadIcon

403

C++11 中实现了一个惰性流，以突出此新规范的函数式功能

引言

在 Coursera 上参加了一门免费的函数式编程入门课程后，我被惰性（非严格）集合的强大功能所吸引。我学习了 Scala 中 `Stream` 类的基本工作原理（基本上是一个具有非严格求值的简单链表）。这彻底改变了我对集合结构以及元素求值方式的看法。

作为一个 C++ 爱好者，我主要生活在命令式世界中，函数式编程对我来说就像一只异国情调的神兽，我渴望将其驯服到我更熟悉的语言中。

在网上浏览时，我的第一个灵感来自 Louis Botterill 技术博客的这篇富有洞察力的 文章 中的示例 2。在这个例子中，Louis 描述了一个自制但非常鼓舞人心的 Scala `Stream` 类模仿品。我采用了他的设计，并尝试将其转换为等效的 C++03 类，但经过几天努力后完全失败了。直到我转向 C++11，我才开始看到隧道尽头的光明……但现在还不是展示最终实现内部结构的时候。

无限流的魅力

让我们看看这个简单的指令

lazy_stream<int> stream_a = lazy_stream<int>::from(3);

简单来说，`stream_a` 是所有大于 2 的整数集合，即 `{3, 4, 5,…}`。它代表一个无限集合，我们可以在其上应用一些我们可能不习惯的有趣操作。第一个是过滤

lazy_stream<int> stream_b = stream_a.filter(
    [](int value){
        return value % 4 == 0;
        });

我们刚刚创建了另一个名为 `stream_b` 的无限集合。在这种情况下，它是 `stream_a` 中所有 4 的倍数的子集。过滤是通过匿名 (lambda) 函数实现的，在上面的示例中，模式是 `[](...){...}`。该操作表示集合 `{4, 8, 12,…}`。

好的。很棒，但我如何将无限集合保存在内存中？实际上，你不能，但你也不需要。在创建 `stream_a` 时，唯一已知的元素是流的**头部**，即数字 `3`。其余部分（称为**尾部**）只是一个胚胎，尚未诞生的流，可以通过调用我们可能称之为**尾部生成器**的函数来创建。要调用尾部生成器，我们使用 `tail` 方法。因此

stream_a.tail();

创建一个全新的惰性流，其头部是数字 4，其尾部是另一个尾部生成器（只是一个函数）。

但并非所有操作都同样是惰性的。`from` 是纯惰性的，但 `filter` 则不然。实际上，它在内部调用 `tail`，直到找到第一个符合过滤条件的元素（在我们的例子中是数字 `4`）。很容易看出，如果没有找到这样的出现，我们就会陷入困境（记住：流是无限的）。

让我们看看另一个纯惰性操作，`map`

typedef std::pair<int, int> pair_type;                                
lazy_stream<pair_type> stream_c = stream_b.map<pair_type>(
    [](int value){ 
        return std::pair<int, int>(value, value + 1);
        });

我们通过将 `stream_b` 的每个值元素映射到对 (value, value+1) 来创建了一个新的惰性流 `stream_c`。那么 `stream_c` 就是：`{(4, 5), (8, 9), (12, 13),…}`。

一旦创建了无限流，我们可能很快就会对探索其元素感兴趣。要获取 `stream_c` 的（比如说）前 10 个元素，我们这样写

lazy_stream<pair_type> stream_d = stream_c.take(10);

注意 `stream_d` 是一个有限流。事实上，我们可以获取它的大小

std::cout << stream_d.size() << std::endl; // Prints 10.

正如你可能想象的，`size` 是一个严格（非惰性）操作。你必须评估惰性流的所有元素才能知道它们有多少。

如果我们只想获取一个元素，我们可以使用 `get` 方法。它只检索指定索引 `n {n=0, 1, 2,…}` 的元素。不幸的是，它还必须评估之前的 `n-1` 个元素。

std::cout << stream_b.get(2) << std::endl; // Prints 12.

一个过时但非常有启发性的惰性流示例是使用所谓的 埃拉托斯特尼筛法 提取前 n 个素数。

无需更多解释，代码如下

// The sieve function object does the hard work.
std::function<lazy_stream<int> (const lazy_stream<int>&)> sieve =
[&sieve](const lazy_stream<int>& start){
    int head = start.head();
    // We filter the primes with respect to head.
    lazy_stream<int> temp = start.filter([head](int value){
        return value % head > 0;
        });
    // We return a new lazy stream with its own head and tail generator.
    return lazy_stream<int>(head, [&sieve, temp](){
        return sieve(temp);
        });
}; 
// prime_numbers holds all the prime numbers.
lazy_stream<int> prime_numbers = sieve(lazy_stream<int>::from(2));
// Let’s take the first 100 prime numbers and pour them into a std::list.
std::list<int> prime_number_list = prime_numbers.take(100).to_list();

没那么花哨的有限惰性流

不那么华丽，但毕竟它们看起来也还不错。要构成一个有限惰性流，我们只需将元素前置到一个已经存在的有限流中。最简单的有限惰性流是空流，也称为 `nil`。

lazy_stream<int> stream_e = 1 & (2 & lazy_stream<int>::nil);

使用括号是一种遗憾，但 C++ 中所有 右结合运算符 只能作为类的成员重载，所以我不得不使用左结合运算符 `&`。例如，等效的 Scala 运算符 ` #:: ` 不需要括号。

一些有趣的注意事项

  • `stream_e` 的大小是 `2`。
  • `lazy_stream::nil` 等价于 `lazy_stream()`。
  • 我们总是可以将一个元素前置到一个已经惰性化的流中，无论它是有限的还是无限的。

除了生成函数 `from`，其余操作（`filter`、`map`、`take` 等）也同样适用于有限流。对于整型，例如，我们可以创建有限范围

// This is the lazy finite set {100, 99, 98,… ,2}. 
lazy_stream<int> stream_f = lazy_stream<int>::range(100, 1);

还有其他操作不值得一提。我只想强调函数式语言中一个非常重要的归约函数：`fold_left`。此操作首先获取类型为 `U` 的起始值（我们称之为 `start`）。然后，对于流中的每个元素，它执行一个给定函数 `op`，该函数接受 `start` 值加上元素值，并将结果存储在 `start` 中。然后它继续处理下一个元素，依此类推。最终结果是一个类型为 `U` 的单个值。

让我们将 `double` 0.5 与 `stream_f` 中的所有元素相加

// Observe that stream_f is a lazy stream of type int.
// The result is of type double instead. 
// (Types of start and result must be the same).
double addition = stream_f.fold_left<double>(0.5)(
    [](double accum, int element){
        return accum + element;
        });

lazy_stream<> 类的目的

在编写 `lazy_stream<>` 时，我无意制作一个功能齐全、优化和高效的代码片段。我只是想了解新的 C++11 规范如何能显著地将语言范围推向更函数式（更少命令式）的视角。

事实上，`lazy_stream<>` 类的一个特点是其所有对象都是不可变的，即一旦创建，它们就不能被修改。这是函数式编程对象的共同特征，通常被命令式语言所忽视，因为不可变性有时会导致内存效率降低；很多时候，修改一个对象比复制它便宜得多。

另一方面，我认为如果使用 C++ 之前的规范，这种设计将非常棘手，甚至不可能。我稍后会讨论这个想法。

实现细节

有限流和无限流都保留三个智能指针，指向堆中动态分配的信息，即

  1. 一个 `std::shared_ptr` 智能指针，名为 `head_ptr_`，指向**头部**（一个泛型类型 `T` 的值）。
  2. 一个 `std::shared_ptr` 智能指针，名为 `tail_ptr_`，指向流的**尾部**（另一个 `lazy_stream`）。
  3. 一个 `std::shared_ptr` 智能指针，名为 `tail_gen_ptr_`，指向流的**尾部生成器**（一个类型为 `std::function ()>` 的函数类）。

指针 [2] 和 [3] 相互排斥，以保持设计一致性。因此，其中一个从对象创建时就直接设置为 `nullptr`。

对于 C++03 开发者来说，`std::function ()>` 这种表示法（在代码中别名为 `tail_gen_type`）相当奇怪。上述类型可以封装任何没有输入参数并返回惰性流的函数。这包括

  1. 纯粹的独立函数
  2. 成员函数（静态或非静态）
  3. Lambda（匿名）函数，带或不带闭包

`tail_gen_type` 的使用是整个设计的基石。在代码中，使用 lambda（带或不带闭包）来表示尾部生成器是普遍的。所有这些函数都可以被同一类型 `tail_gen_type` 包装（或表示）。

作为一个说明性示例，让我们看看 `take` 方法的实现。请记住，此方法接受一个输入流，并返回一个包含前 `n` 个元素的新流。

// take method implementation
template <typename T>
lazy_stream<T> lazy_stream<T>::take(size_t n) const
{
    if(empty_ || n<1)
        return lazy_stream<T>();         // [1]    
    const tail_type& tail_ = tail();     // [2]
    return lazy_stream<T>
            (*head_ptr_, [tail_, n]() -> lazy_stream<T> {return tail_.take(n-1);}) // [3]
}

此方法以及 `lazy_stream<>` 中的其他方法都是 `const`。

如果 `this` 流为空，或者我们请求的元素少于一个，我们只返回一个空流 [1]。否则，我们评估尾部流，调用 `tail()` [2]。最终，我们创建并返回一个全新的惰性流 [3]，其头部是 `this` 的头部，其尾部生成器由 lambda 给出

[tail_, n]() -> lazy_stream<T> { 
    return tail_.take(n-1); 
    });

请注意，一旦新的惰性流被创建并返回，就不会采取进一步的行动。此时，我们只知道这个第二个流的头部（`*head_ptr_`）。如果我们现在在这个新生流上调用 `tail()`，将通过评估

tail_.take(n-1);

在 lambda 中，其中 `tail_` 是第一个流的尾部。

我们一直很懒，但实际上我们可以更懒。考虑这个替代（但未实现）的代码

// Alternative take method implementation
template <typename T> 
lazy_stream<T> lazy_stream<T>::take(size_t n) const
{
    if(empty_ || n<1)
        return lazy_stream<T>();
    const tail_ptr_type& tail_ptr = tail_ptr_;
    const tail_gen_ptr_type& tail_gen_ptr = tail_gen_ptr_;
    return lazy_stream<T>(*head_ptr_,
                          [tail_ptr, tail_gen_ptr, n]() -> lazy_stream<T> {
                          // This cannot happen
                          assert(!(tail_ptr && tail_gen_ptr));
                          if(tail_ptr)
                              return tail_ptr->take(n-1);
                          return (*tail_gen_ptr)().take(n-1);
                          });
}

上面的实现确实比原始实现效率更高一些：我们没有将流头传入 lambda。此外，它更懒惰一些：`tail()` 的第一次调用是在 lambda 内部。我忽略它只是出于主观原因：它相对于原始版本失去了清晰度，并且有点冗长。你可以随意选择你更喜欢的。

因为这里开发的惰性流是不可变的，它们不能被赋值（赋值操作被禁用）。另一方面，复制构造以合理的成本可用。正如我们所知，惰性流对象将其信息存储在堆中，只保留两个活动智能指针指向它。复制时，我们实际上是共享资源所有权。

C++03 中的实现陷阱

我在 Scala 课程后的第一次尝试是用 C++03 编写一个惰性流类。绞尽脑汁很久之后，我放弃了。在 C++03 中，没有 lambda，所以为了接近它们，我尝试使用函数类（仿函数）。例如，让我们将以下 lambda 转换为一个仿函数

[tail_, n]() ->lazy_stream<T> {
    return tail_.take(n-1);
    });

等效的仿函数可能是

template <typename T>
class take_functor
{
    typedef lazy_stream<T> tail_type;
    T n_;            // Closure parameter
    tail_type tail_; // Closure parameter
public:
    take_functor(const T& n, const tail_type& tail) : n_(n), tail_(tail) {}
    tail_type operator()() const
    {
        return tail_.take(n_-1);
    }
};

本质区别在于，每个具有符号类型 `()=>lazy_stream` (在 Scala 表示法中) 的 lambda 函数，无论它是什么，都可以由 `std::function ()>` 表示。据我所知，在 C++03 中，仿函数没有类似的表示。此外，`std::function` 在 2011 年之前的 C++ 规范中甚至不存在。因此，在使用 C++03 时，我无法为我编写的所有仿函数提供一个共同的表示。C++03 中有什么唯一的类型可以容纳一个带有任何闭包参数的仿函数，它表示类型为 `()=>lazy_stream` 的函数？我想没有。所以关键问题是我无法弄清楚如何在 C++03 中编写一个尾部生成器。

源代码

`lazy_stream<>` 的实现代码以及主示例代码已附上。只翻译了相应 Scala 方法的一个子集（从我的角度来看，最有见地）。该类允许扩展和进一步优化。

代码是用 Code::Blocks 编写的，并用 MinGw (mingw32-gcc-g++ 5.3.0-3) 编译。它也已用 MS Visual Studio 2015 编译。

历史

  • 2012 年 12 月。初始版本
  • 2014 年 5 月。版本 1.1。主要更改
    • 构造函数已模板化，以支持右值参数。（感谢 Lukasz Gwizdz，另一位 CodeProject 成员的见解）
    • 新增成员函数：`filter_not`、`find_first`、`reduce_left` 等。
  • 2018 年 6 月。版本 1.2。主要更改
    • `reduce_left` 方法中的错误已更正
    • 添加了对 MS Visual Studio 2015 的解决方案

参考文献

  1. Coursera。Scala 中的函数式编程原理。Martin Odersky (www.coursera.org)
  2. Louis Botterill 的主要软件和技术博客。Scala、惰性求值和埃拉托斯特尼筛法 (http://louisbotterill.blogspot.com.es/2009/07/scala-lazy-evaluation-and-sieve-of.html)
  3. 维基百科。埃拉托斯特尼筛法 (http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes)
  4. C/C++ 运算符优先级和结合性 (http://www.anne-gert.nl/techcorner/cpp/cpp-operators.html)
  5. 仿函数：C++ 中的函数对象。Alex Allain (http://www.cprogramming.com/tutorial/functors-function-objects-in-c++.html)
© . All rights reserved.