Generazione di sequenze pigri in Rust

Question

Come posso creare quelle che altre lingue chiamano una sequenza lazy o una funzione "generatore"?

In Python, posso usare yield come nel seguente esempio (da documenti di Python) per generare pigramente una sequenza che è iterabile in un modo che non utilizza la memoria di un elenco intermediario:

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

Come posso fare qualcosa di simile in Rust?

Answer 1

Rust 1.0 non ha funzioni di generatore, quindi è necessario farlo manualmente con explicit iterators.

Prima di tutto, riscrivi il tuo esempio Python come una classe con un metodo next(), poiché è più vicino al modello che potresti ottenere in Rust. Quindi puoi riscriverlo in Rust con una struttura che implementa il tratto Iterator.

Si potrebbe anche essere in grado di utilizzare una funzione che restituisce una chiusura per ottenere un risultato simile, ma non penso che sarebbe possibile avere che implementare il tratto Iterator (poiché richiederebbe essere chiamato per generare un nuovo risultato).

Answer 2

ruggine fa hanno generatori, ma sono altamente sperimentale e non attualmente disponibile in ruggine stabile.

Lavori in stabile Rust 1.0 e superiori

Range gestisce il vostro esempio concreto. Si può usare con lo zucchero sintattico di ..:

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

E se Range non esistesse? Possiamo creare un iteratore che lo modella!

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

Gli intestini sono gli stessi, ma più espliciti rispetto alla versione Python. In particolare, i generatori di Python tengono traccia dello stato per te. La ruggine preferisce l'explicitness, quindi dobbiamo creare il nostro stato e aggiornarlo manualmente. La parte importante è l'implementazione di Iterator trait. Specifichiamo che l'iteratore restituisce valori di un tipo specifico (type Item = u64) e quindi gestiamo l'stepping di ciascuna iterazione e il modo in cui dire che abbiamo raggiunto la fine dell'iterazione.

Questo esempio non è potente come il reale Range, che utilizza i generici, ma mostra un esempio di come procedere.

Lavori in Rust notte

Nightly Rust does have generators, ma sono altamente sperimentale. Devi creare alcune caratteristiche instabili per crearne una. Tuttavia, sembra abbastanza vicino l'esempio di Python, con alcune aggiunte Rust-specifici:

#![feature(generators, generator_trait, conservative_impl_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; 
     } 
    } 
} 

Poiché tutto a Rust attuale opera su iteratori, creiamo un adattatore che converte un generatore in un iteratore al fine di giocare con l'ecosistema più ampio.Mi aspetto che un tale adattatore sarebbe presente nella libreria standard alla fine:

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 self.0.resume() { 
      GeneratorState::Yielded(x) => Some(x), 
      GeneratorState::Complete(_) => None, 
     } 
    } 
} 

Ora si può usare:

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

La cosa interessante di questo è che è meno potente di un'implementazione di Iterator. Ad esempio, gli iteratori hanno il metodo size_hint, che consente ai consumatori dell'iteratore di avere un'idea di quanti elementi restano. Ciò consente ottimizzazioni quando collect si inserisce in un contenitore. I generatori non hanno tali informazioni.

Answer 3

Puoi usare il mio Rust stackful generator library che sostiene Rust stabile:

#[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 più semplicemente:

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();