Was sind Iteratoren und wozu sind sie wichtig? Diese Fragen sollen anhand eines motivierenden Beispiels beantwortet werden. Vorzulegen sei ein Programm, das von einer Reihe von Werten den Mittelwert berechnet. Die klassische Formulierung für die Berechnung des Mittelwerts sieht wie folgt aus.
fn mean(a: &[f64]) -> f64 {
let mut sum = 0.0;
for i in 0..a.len() {
sum += a[i];
}
sum/(a.len() as f64)
}
Angenommen, die Werte kommen nun aus einer Datei. Man müsste nun zunächst die Werte aus der Datei extrahieren und in einem Array zwischenspeichern. Ist die Zahl der Werte allerdings sehr groß, kann das Array eine immense Menge an Hauptspeicher belegen. Zur Umgehung dieses Problems formuliert man dann eine Anpassung die auf das Zwischenspeichern verzichtet. Infolge liegen nun aber zwei unterschiedliche Varianten vom gleichen Algorithmus vor, was man als unelegant und umständlich betrachten kann.
Was wir bräuchten wäre eine Funktion die nicht von der Form der zu verarbeitenden Datenstruktur abhängig ist. Die obige Funktion erlaubt nur Arrays, Slices und dynamische Arrays, jedoch z. B. keine verketteten Listen. Das zentrale Problem dabei ist, dass die Schnittstelle der Funktion die interne Struktur der Datenstruktur offenlegt. Wir benötigen stattdessen eine abstrakte Schnittstelle.
An dieser Stelle kommen Iteratoren ins Spiel. Ein Iterator kann als Schnittstelle zum Zugriff auf die Elemente einer Datenstruktur betrachtet werden. Die über alle iterierbaren Typen polymorphe Formulierung der Berechnung des Mittelwertes gestaltet sich so:
fn mean(a: impl Iterator<Item = f64>) -> f64 {
let mut count: u64 = 0;
let mut sum = 0.0;
for x in a {
sum += x; count += 1;
}
sum/(count as f64)
}
Diese Funktion erlaubt sowohl Arrays:
fn main() {
let a = &[1.0, 2.0, 3.0, 4.0];
println!("{}", mean(a.iter().cloned()));
}
als auch Datenströme aus Dateien:
fn main() -> std::io::Result<()> {
use std::{fs::File, io::BufReader, io::BufRead};
let argv: Vec<String> = std::env::args().collect();
let file = BufReader::new(File::open(&argv[1])?);
let stream = file.lines()
.map(|s| s.unwrap().parse::<f64>().unwrap());
println!("{}", mean(stream));
Ok(())
}
Ein verbleibendes Manko schlägt sich im Vorkommen von
unwrap nieder. Aufgrund dieses Umstandes könnte man nun
meinen, Iteratoren wären, weil sie keine Fehler berücksichtigen können,
zur kurz gedacht und damit für die Praxis ungeeignet. Dem ist
jedoch nicht so. Später zeige ich im Abschnitt
›Fehlbare Iteratoren‹ auf, wie man
Fehler in die Iteratoren einbeziehen kann.
Ein interner Iterator manifestiert sich im Aufruf einer Funktion
höherer Ordnung, die kontrolliert welche Argumente an einen
Funktionenzeiger übergeben werden. Die Argumente sind die Werte des
Iterators. Betrachten wir als Beispiel die Methode
for_each, die jedes Element mit dem Funktionenzeiger
cb (callback) aufruft. Nur for_each besitzt
die Kontrolle darüber, mit welchen Elementen cb aufgerufen
wird.
trait ForEach<T> {
fn for_each(self, cb: impl Fn(&T));
}
impl<T> ForEach<T> for &[T] {
fn for_each(self, cb: impl Fn(&T)) {
for i in 0..self.len() {
cb(&self[i]);
}
}
}
fn main() {
let a = ["Eiche", "Buche", "Ahorn", "Birke"];
a.for_each(|x| {
println!("{}", x);
});
}
Hier ist x der Wert des zu for_each
gehörenden verborgenen Iterators.
Ein externer Iterator ist ein Objekt, welches den Trait
Iterator implmentiert, d. h. eine Methode
next besitzt, die den nächsten Wert der Iteration
liefert.
struct SliceIterator<'a,T> {
a: &'a [T],
i: usize
}
impl<'a,T> Iterator for SliceIterator<'a,T> {
type Item = &'a T;
fn next(&mut self) -> Option<&'a T> {
match self.i < self.a.len() {
false => None,
_ => {self.i += 1; Some(&self.a[self.i-1])}
}
}
}
fn iter<T>(a: &[T]) -> SliceIterator<T> {
SliceIterator {a, i: 0}
}
fn main() {
let a = ["Eiche", "Buche", "Ahorn", "Birke"];
for x in iter(&a) {
println!("{}", x);
}
}
In Rust besteht zwischen Iteratoren und der for-Schleife ein
enger Zusammenhang. Und zwar ist die for-Schleife eine Kurzschreibweise
für die Erzeugung eines Iterators durch den Aufruf von
into_iter und dessen Abarbeitung durch den Aufruf von
next. Der erzeugte Iterator ist hierbei nur implizit
vorhanden, – damit meine ich, er kommt aus äußerer Sicht
nicht vor.
Zur näheren Erläuterung ein Beispiel. Das Programm
let v = vec![1, 2, 3, 4];
for x in v {
println!("{}", x);
}
ist äquivalent zu
let v = vec![1, 2, 3, 4];
let mut i = v.into_iter();
while let Some(x) = i.next() {
println!("{}", x);
}
bzw.
let v = vec![1, 2, 3, 4];
let mut i = v.into_iter();
loop {
let x = match i.next() {
Some(value) => value,
None => break
};
println!("{}", x);
}
Von Belang ist für uns, dass die Methode into_iter
ihr Argument konsumiert, wie man an ihrer Signatur
fn into_iter(self) -> Self::IntoIter
ablesen kann. In vielen Fällen ist allerdings eine Leihgabe anstelle
einer Besitzübertragung gewünscht. Erreicht wird dies meistens
einfach, indem man zuvor eine Leihgabe bildet. Nämlich ist
into_iter
die Methode des Traits IntoIterator, welcher für viele
unterschiedliche Typen implementiert ist. Die Idee dabei: Zwar
konsumiert into_iter immer ihr Argument. Aber falls
dieses Argument eine Leihgabe ist, wird ja lediglich diese Leihgabe
konsumiert.
Alternativ schaltet man den Aufruf einer der Methoden
iter oder iter_mut vor, welche
auch für viele Typen implementiert sind, – allerdings nicht
in Form von Trait-Methoden. Diese Methoden erzeugen einen Iterator
aus Leihgaben, welcher daraufhin durch into_iter
konsumiert wird. Es ist nämlich so, dass into_iter
für jeden Iterator generisch als identische Abbildung implementiert
ist. Das heißt, falls bereits ein Iterator vorliegt, ist
into_iter schlicht wirkungslos.
Zu beachten ist noch, dass die Bildung von Leihgaben mit der Leihgabe der Iteratorwerte einhergeht. Das muss auch so sein. Wurde der Iterator lediglich aus einer Leihgabe heraus erzeugt, darf dieser keinesfalls die Elemente konsumieren, da diese Elemente nicht im Besitz des Iterators liegen.
Der Typ Vec<T> ist zudem mit der Besonderheit
behaftet, die Methoden iter und iter_mut
nicht extra implementieren zu müssen, weil die Leihgabe bei diesem
über den Deref-Mechanismus auf die Leihgabe der Belegung des internen
Puffers zurückgeführt wird. Dieser Puffer-Ausschnitt ist vom Typ
[T], welcher bereits die entsprechenden Methoden besitzt.
| Methode | Typ des Arguments | Typ des Iteratorwertes |
|---|---|---|
iter | &[T] | &T
|
iter_mut | &mut [T] | &mut T
|
into_iter | Vec<T> | T
|
Die Einführung von Iteratoren wurde anhand einer
Mittelwert-Berechnung motiviert. Da tat sich sogleich die Problematik
auf, dass Iteratoren Fehler berücksichtigen können müssen,
damit man das Programm von Programmabbrüchen via unwrap
oder ähnlich bereinigen kann.
Ein Weg zur Einbeziehung von Fehlern besteht in der
Anpassung der Funktion mean. Das geht so:
fn mean<E>(a: impl Iterator<Item = Result<f64, E>>)
-> Result<f64, E>
{
let mut count: u64 = 0;
let mut sum = 0.0;
for x in a {
sum += x?; count += 1;
}
Ok(sum/(count as f64))
}
type Error = Box<dyn std::error::Error>;
fn main() -> Result<(), Error> {
use std::{fs::File, io::BufReader, io::BufRead};
let argv: Vec<String> = std::env::args().collect();
let file = BufReader::new(File::open(&argv[1])?);
let stream = file.lines()
.map(|s| Ok::<f64, Error>(s?.parse::<f64>()?));
println!("{}", mean(stream)?);
Ok(())
}
Die neue Funktion kann man als eine Verallgemeinerung betrachten, denn die ursprüngliche lässt sich aus dieser zurückgewinnen:
fn mean_plain(a: impl Iterator<Item = f64>) -> f64 {
enum Zero {}
match mean(a.map(Ok::<f64, Zero>)) {
Ok(value) => value,
Err(e) => match e {} // unreachable
}
}
Das ist ein wenig umständlich. In Zukunft sollte man das ein wenig kürzer formulieren können:
fn mean_plain(a: impl Iterator<Item = f64>) -> f64 {
let Ok(value) = mean(a.map(Ok::<f64, !>));
value
}
Die manuelle Berücksichtigung kommt recht umständlich daher,
das ist ein berechtigter Einwand. Wir würden lieber eine Funktionalität
haben, die zu einem Iterator automatisch eine fehlbare Verarbeitung
erzeugt, so ähnlich wie Result::map das bei einer Funktion
tut. Hier stellt sich die Schwierigkeit in den Weg, dass
mean den Iterator konsumiert, woraufhin der Iterator von
außen aus nicht mehr kontrollierbar ist.
Der einzige verbleibende Weg besteht darin, den Iterator von
innen aus zu kontrollieren. Dazu wird der ursprüngliche fehlbare
Iterator durch einen neuen unfehlbaren Iterator verhüllt. Kommt es
im ursprünglichen Iterator zu einem Fehler, wird der Fehler in eine
Hilfsvariable geschrieben und der unfehlbare Iterator beendet.
Der Wert von mean wird verworfen und durch den Fehler
ersetzt.
Weil der unfehlbare Iterator von mean konsumiert
wird, muss die Hilfsvariable als Leihgabe gespeichert werden,
denn andernfalls würde sie mit dem Iterator verschwinden.
Das führt zu der folgenden Konstruktion.
struct ProcessResults<'a, I, E> {
error: &'a mut Result<(), E>,
iter: I
}
impl<I, T, E> Iterator for ProcessResults<'_, I, E>
where I: Iterator<Item = Result<T, E>>
{
type Item = T;
fn next(&mut self) -> Option<Self::Item> {
match self.iter.next() {
Some(Ok(x)) => Some(x),
Some(Err(e)) => {
*self.error = Err(e);
None
},
None => None
}
}
}
fn process_results<I, F, T, E, R>(i: I, cb: F) -> Result<R, E>
where
I: Iterator<Item = Result<T, E>>,
F: FnOnce(ProcessResults<I, E>) -> R
{
let mut error = Ok(());
let value = cb(ProcessResults {iter: i, error: &mut error});
match error {Ok(()) => Ok(value), Err(e) => Err(e)}
}
Diese Funktion process_results ist im Paket
»itertools«
verfügbar. Damit wird man unwrap los, ohne
mean modifizieren zu müssen:
fn mean(a: impl Iterator<Item = f64>) -> f64 {
let mut count: u64 = 0;
let mut sum = 0.0;
for x in a {
sum += x; count += 1;
}
sum/(count as f64)
}
type Error = Box<dyn std::error::Error>;
fn main() -> Result<(), Error> {
use std::{fs::File, io::BufReader, io::BufRead};
let argv: Vec<String> = std::env::args().collect();
let file = BufReader::new(File::open(&argv[1])?);
let stream = file.lines()
.map(|s| Ok::<f64, Error>(s?.parse::<f64>()?));
println!("{:?}", process_results(stream, |i| mean(i))?);
Ok(())
}
Zu beachten ist, dass process_results im Allgemeinen
nicht die äquivalente Semantik liefert wie die manuelle Anpassung,
da die Funktion nach dem Ende des Iterators nicht sofort verlassen
wird. Sofern die Funktion wie mean frei von Seiteneffekten
ist, spielt das aber keine beachtenswerte Rolle.