Lazy Sequence Generation in Rust

Question

Wie kann ich erstellen, was andere Sprachen eine Lazy-Sequenz oder eine "Generator" -Funktion nennen?

In Python, kann ich yield wie im folgenden Beispiel verwenden (von Python-Dokumente) an lazily eine Sequenz zu erzeugen, die in einer Art und Weise iterable ist, die nicht auf den Speicher eines Zwischenliste nicht verwendet:

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

Wie kann ich in Rust etwas Ähnliches machen?

Answer 1

Rust 1.0 hat keine Generatorfunktionen, also müssten Sie es manuell mit explicit iterators tun.

Schreiben Sie zuerst Ihr Python-Beispiel als eine Klasse mit einer next() Methode, da das näher an dem Modell ist, das Sie wahrscheinlich in Rust bekommen. Dann können Sie es in Rust mit einer Struktur umschreiben, die das Merkmal Iterator implementiert.

Sie können möglicherweise auch eine Funktion verwenden, die eine Schließung zurückgibt, um ein ähnliches Ergebnis zu erzielen, aber ich denke nicht, dass es möglich wäre, das Iterator Merkmal zu implementieren (da es aufgerufen werden müsste, um a zu generieren neues Ergebnis).

Answer 2

Rust tut Generatoren haben, aber sie sind höchst experimentell und derzeit nicht in stabilen Rust.

Arbeiten in stabilen Rust 1.0 und höher

Range Griffe Ihr konkretes Beispiel. Sie können es mit dem syntaktischen Zucker von .. verwenden:

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

Was passiert, wenn Range nicht existieren? Wir können einen Iterator erstellen, der es modelliert!

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

Die Eingeweide sind die gleichen, aber expliziter als die Python-Version. Bemerkenswert ist, dass Pythons Generatoren den Status für Sie verfolgen. Rust bevorzugt Explizitheit, also müssen wir unseren eigenen Status erstellen und manuell aktualisieren. Der wichtige Teil ist die Implementierung der Iterator trait. Wir geben an, dass der Iterator Werte eines bestimmten Typs liefert (type Item = u64) und dann mit dem schrittweisen Ausführen jeder Iteration und dem Ermitteln, dass wir das Ende der Iteration erreicht haben.

Dieses Beispiel ist nicht so leistungsfähig wie das echte Range, das Generics verwendet, aber zeigt ein Beispiel dafür, wie es geht.

Werke in der nächtlichen Rust

Nightly Rust does have generators, aber sie sind höchst experimentell. Sie müssen ein paar instabile Funktionen einbringen, um eines zu erstellen. Allerdings sieht es ziemlich nahe dem Python Beispiel mit einigen Rust spezifische Ergänzungen:

#![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; 
     } 
    } 
} 

Da alles in der aktuellen Rust auf Iteratoren arbeitet, schaffen wir einen Adapter, der einen Generator in einem Iterator, um umwandelt mit dem breiteren Ökosystem spielen.Ich würde erwarten, dass ein solcher Adapter in der Standard-Bibliothek vorhanden sein würde schließlich:

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

Jetzt können wir sie verwenden:

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

Was ist das interessant ist, dass es weniger leistungsfähig als eine Implementierung Iterator. Zum Beispiel haben Iteratoren die size_hint-Methode, die es Verbrauchern des Iterators ermöglicht, eine Vorstellung davon zu haben, wie viele Elemente noch übrig sind. Dies ermöglicht Optimierungen, wenn Sie in einen Container einsteigen. Generatoren haben keine solchen Informationen.

Answer 3

Sie können meine stackful Rust generator library verwenden, die stabil Rust unterstützt:

#[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); 
} 

oder einfacher:

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