rust - Rust 中的惰性序列生成

Question

我如何创建其他语言所称的惰性序列或“生成器”函数？

在 Python 中，我可以像下面的示例(来自 Python 的文档)那样使用 yield 来懒惰地生成一个可迭代的序列，而不使用中间列表的内存:

# a generator that yields items instead of returning a list
def firstn(n):
    num = 0
    while num < n:
        yield num
        num += 1

sum_of_first_n = sum(firstn(1000000))

如何在 Rust 中做类似的事情？

Answer 1

Rust 确实有生成器，但它们是高度实验性的，目前在稳定的 Rust 中不可用。

在稳定的 Rust 1.0 及更高版本中工作

Range处理你的具体例子。您可以将它与 .. 的语法糖一起使用:

fn main() {
    let sum: u64 = (0..1_000_000).sum();
    println!("{}", sum)
}

如果 Range 不存在怎么办？我们可以创建一个对其建模的迭代器!

struct MyRange {
    start: u64,
    end: u64,
}

impl MyRange {
    fn new(start: u64, end: u64) -> MyRange {
        MyRange {
            start: start,
            end: end,
        }
    }
}

impl Iterator for MyRange {
    type Item = u64;

    fn next(&mut self) -> Option<u64> {
        if self.start == self.end {
            None
        } else {
            let result = Some(self.start);
            self.start += 1;
            result
        }
    }
}

fn main() {
    let sum: u64 = MyRange::new(0, 1_000_000).sum();
    println!("{}", sum)
}

内容是相同的，但比 Python 版本更明确。值得注意的是，Python 的生成器会为您跟踪状态。 Rust 更喜欢显式，因此我们必须创建自己的状态并手动更新它。重要的部分是 Iterator trait 的实现.我们指定迭代器生成特定类型的值 (type Item = u64)，然后处理步进每次迭代以及如何判断我们已经到达迭代结束。

这个例子没有真正的 Range 强大，它使用了泛型，但是展示了一个如何实现它的例子。

在 nightly Rust 中工作

Nightly Rust does have generators ，但它们具有高度实验性。您需要引入一些不稳定的功能来创建一个。但是，它看起来非常接近于 Python 示例，并添加了一些特定于 Rust 的内容:

// 1.43.0-nightly (2020-02-09 71c7e149e42cb0fc78a8)
#![feature(generators, generator_trait)]

use std::{
    ops::{Generator, GeneratorState},
    pin::Pin,
};

fn firstn(n: u64) -> impl Generator<Yield = u64, Return = ()> {
    move || {
        let mut num = 0;
        while num < n {
            yield num;
            num += 1;
        }
    }
}

由于当前 Rust 中的所有内容都在迭代器上运行，因此我们创建了一个将生成器转换为迭代器的适配器，以便与更广泛的生态系统一起玩。我希望这样的适配器最终会出现在标准库中:

struct GeneratorIteratorAdapter<G>(Pin<Box<G>>);

impl<G> GeneratorIteratorAdapter<G>
where
    G: Generator<Return = ()>,
{
    fn new(gen: G) -> Self {
        Self(Box::pin(gen))
    }
}

impl<G> Iterator for GeneratorIteratorAdapter<G>
where
    G: Generator<Return = ()>,
{
    type Item = G::Yield;

    fn next(&mut self) -> Option<Self::Item> {
        match self.0.as_mut().resume(()) {
            GeneratorState::Yielded(x) => Some(x),
            GeneratorState::Complete(_) => None,
        }
    }
}

现在我们可以使用它了:

fn main() {
    let generator_iterator = GeneratorIteratorAdapter::new(firstn(1_000_000));
    let sum: u64 = generator_iterator.sum();
    println!("{}", sum);
}

有趣的是，它不如 Iterator 的实现强大。例如，迭代器有 size_hint方法，它允许迭代器的使用者了解剩余的元素数量。这允许在 collect 到容器中时进行优化。生成器没有任何此类信息。