Generación de secuencia perezosa en Rust

lazy-sequences

Question

¿Cómo puedo crear lo que otros idiomas llaman una secuencia perezosa o una función de "generador"?

En Python, puedo usar el yield como en el siguiente ejemplo (de los documentos de Python) para generar perezosamente una secuencia que es iterable de una manera que no usa la memoria de una lista intermedia:

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

¿Cómo puedo hacer algo similar en Rust?

Answer 1

Puede usar mi biblioteca de generadores Rust apilables que admite Rust estable:

#[macro_use]
extern crate generator;
use generator::{Generator, Gn};

fn firstn(n: usize) -> Generator<''static, (), usize> {
    Gn::new_scoped(move |mut s| {
        let mut num = 0;
        while num < n {
            s.yield_(num);
            num += 1;
        }
        done!();
    })
}

fn main() {
    let sum_of_first_n: usize = firstn(1000000).sum();
    println!("sum ={}", sum_of_first_n);
}

o más simplemente:

let n = 100000;
let range = Gn::new_scoped(move |mut s| {
    let mut num = 0;
    while num < n {
        s.yield_(num);
        num += 1;
    }
    done!();
});

let sum: usize = range.sum();

Answer 2

Rust 1.0 no tiene funciones de generador, por lo que tendría que hacerlo manualmente con iteradores explícitos .

Primero, vuelva a escribir su ejemplo de Python como una clase con un método next() , ya que está más cerca del modelo que probablemente obtendrá en Rust. Luego, puede reescribirlo en Rust con una estructura que implemente el rasgo del Iterator .

También es posible que pueda usar una función que devuelva un cierre para lograr un resultado similar, pero no creo que sea posible tener que implementar el rasgo del Iterator (ya que sería necesario que se lo llame para generar un nuevo resultado).

Answer 3

Rust tiene generadores, pero son altamente experimentales y no están disponibles actualmente en Rust estable.

Funciona en estable Rust 1.0 y superior.

Range maneja tu ejemplo concreto. Puedes usarlo con el azúcar sintáctico de .. :

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

¿Qué pasaría si el Range no existiera? Podemos crear un iterador que lo modele!

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

Las agallas son las mismas, pero más explícitas que la versión de Python. En particular, los generadores de Python realizan un seguimiento del estado para usted. Rust prefiere la explicación explícita, por lo que tenemos que crear nuestro propio estado y actualizarlo manualmente. La parte importante es la implementación del rasgo Iterator . Especificamos que el iterador produce valores de un tipo específico ( type Item = u64 ) y luego tratamos con el paso de cada iteración y cómo saber si hemos llegado al final de la iteración.

Este ejemplo no es tan poderoso como el Range real, que utiliza genéricos, pero muestra un ejemplo de cómo hacerlo.

Funciona en el óxido nocturno

El óxido nocturno tiene generadores , pero son altamente experimentales . Necesita crear algunas características inestables para crear una. Sin embargo, se parece bastante al ejemplo de Python, con algunas adiciones específicas de Rust:

#![feature(generators, generator_trait)]

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

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

Dado que todo en Rust actual funciona con iteradores, creamos un adaptador que convierte un generador en un iterador para jugar con el ecosistema más amplio. Espero que dicho adaptador esté presente en la biblioteca estándar eventualmente:

struct GeneratorIteratorAdapter<G>(G);

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

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

Ahora podemos usarlo:

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

Lo interesante de esto es que es menos potente que una implementación de Iterator . Por ejemplo, los iteradores tienen el método size_hint , que permite a los consumidores del iterador tener una idea de cuántos elementos quedan. Esto permite optimizaciones al collect en un contenedor. Los generadores no tienen tal información.