Lazy sequence generation in Rust

by

Rust does have generators, but they are highly experimental and not currently available in stable Rust.

Works in stable Rust 1.0 and above

Range handles your concrete example. You can use it with the syntactical sugar of ..:

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

What if Range didn’t exist? We can create an iterator that models it!

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)
}

The guts are the same, but more explicit than the Python version. Notably, Python’s generators keep track of the state for you. Rust prefers explicitness, so we have to create our own state and update it manually. The important part is the implementation of the Iterator trait. We specify that the iterator yields values of a specific type (type Item = u64) and then deal with stepping each iteration and how to tell we have reached the end of iteration.

This example is not as powerful as the real Range, which uses generics, but shows an example of how to go about it.

Works in nightly Rust

Nightly Rust does have generators, but they are highly experimental. You need to bring in a few unstable features to create one. However, it looks pretty close to the Python example, with some Rust-specific additions:

// 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;
        }
    }
}

Since everything in current Rust operates on iterators, we create an adapter that converts a generator into an iterator in order to play with the broader ecosystem. I’d expect that such an adapter would be present in the standard library eventually:

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,
        }
    }
}

Now we can use it:

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

What’s interesting about this is that it’s less powerful than an implementation of Iterator. For example, iterators have the size_hint method, which allows consumers of the iterator to have an idea of how many elements are remaining. This allows optimizations when collecting into a container. Generators do not have any such information.

More Related Contents:

  1. Why can’t I store a value and a reference to that value in the same struct?
  2. The compiler suggests I add a ‘static lifetime because the parameter type may not live long enough, but I don’t think that’s what I want
  3. Is it possible to control the size of an array using the type parameter of a generic?
  4. Does println! borrow or own the variable?
  5. How do I pass disjoint slices from a vector to different threads?
  6. Why does Iterator::take_while take ownership of the iterator?
  7. When should I implement std::convert::From vs std::convert::Into?
  8. Why is it possible to implement Read on an immutable reference to File?
  9. Compare enums only by variant, not value
  10. How can I call a mutating method while holding a reference to self?
  11. How do you actually use dynamically sized types in Rust?
  12. “parameter `’a` is never used” error when ‘a is used in type parameter bound
  13. Borrowing references to attributes in a struct
  14. How to operate on 2 mutable slices of a Rust array?
  15. Mutating one field while iterating over another immutable field
  16. How can I use a module from outside the src folder in a binary project, such as for integration tests or benchmarks?
  17. How to match on data type in Rust?
  18. Why does Rust allow mutation through a reference field using an immutable binding?
  19. How can I modify self in a closure called from a member function?
  20. Multiple return types from a method
  21. How to end a borrow in a match or if let expression?
  22. How do I move out of a struct field that is an Option?
  23. Why does this mutable borrow live beyond its scope?
  24. Why does creating a mutable reference to a dereferenced mutable reference work?
  25. Cannot borrow `x` as mutable more than once at a time
  26. What is unwrap in Rust, and what is it used for?
  27. How can I find a subsequence in a &[u8] slice?
  28. Can Cargo download and build dependencies without also building the application?
  29. Is there a way for me to use #[derive] on a struct or enum from a library without editing the actual library’s source code?
  30. Why is this Rust slower than my similar Python? [duplicate]

Leave a Comment