Kapitel 15: Iteratoren und funktionale Programmierung

Stellen Sie sich vor, Sie arbeiten in einer Süßwarenfabrik an einem Fließband. Auf der einen Seite kommen unverpackte Pralinen hinein, und Ihre Aufgabe ist es, diese zu prüfen, mit Schokolade zu überziehen, in kleine Förmchen zu setzen und schließlich in Schachteln zu verpacken.

In vielen traditionellen Programmiersprachen würden Sie diese Aufgabe mit einer klassischen Schleife (wie einer for- oder while-Schleife) lösen. Sie würden jede Praline einzeln in die Hand nehmen, die Schritte nacheinander ausführen und sie in die Schachtel legen.

Rust bietet Ihnen mit Iteratoren eine elegantere Methode: Sie definieren ein „Fließband“ (eine Kette von Verarbeitungsschritten) und lassen die Daten hindurchgleiten. Das Besondere daran: Das Fließband bewegt sich keinen Millimeter, solange am Ende niemand steht, der die fertigen Pralinen abnimmt. Dieses Prinzip nennen wir Lazy Evaluation (träge oder faule Auswertung).

In diesem Kapitel bieten wir Ihnen drei verschiedene Perspektiven auf das Thema an. Wählen Sie die Sicht, die am besten zu Ihrem Hintergrund passt:

• Für Anfänger (Einfach): Konzentriert sich auf das Fließband-Prinzip, die drei Iterationsarten (iter(), iter_mut(), into_iter()), einfache Adapter (map, filter, take) und den Konsumenten collect().
• für Profis (Architektur): Behandelt das Schreiben eigener Iteratoren, fortgeschrittene Adapter (skip, zip, flat_map), die Funktionsweise von fold und reduce sowie unendliche Iteratoren.
• Hardware-Sicht (CPU/RAM): Analysiert das Versprechen der Zero-Cost Abstractions, die Vermeidung von Bounds Checks im Vergleich zu klassischen Schleifen und Dynamic Dispatch bei Iteratoren (Box<dyn Iterator>).

Kapitel 15: Iteratoren und funktionale Programmierung – Das Fließband im Code

Stell dir vor, du arbeitest in einer Fabrik für feine Pralinen. Vor dir steht ein großes Fließband. Auf der linken Seite legt eine Maschine rohe, unverpackte Marzipankugeln auf das Band.

Nun hast du verschiedene Stationen am Fließband aufgebaut:

1. Station 1 (Der Aussortierer): Jede Kugel wird gewogen. Ist sie zu klein, fliegt sie vom Band.
2. Station 2 (Der Veredler): Jede Kugel, die übrig bleibt, wird mit flüssiger Vollmilchschokolade überzogen.
3. Station 3 (Der Dekorierer): Jede Kugel bekommt eine kleine Walnuss oben aufgesetzt.

Am Ende des Fließbands steht der Verpacker mit einer leeren Schachtel.

Jetzt kommt das wichtigste Geheimnis dieser Fabrik: Das Fließband bewegt sich keinen Millimeter von allein. Wenn der Verpacker am Ende keine Praline anfordert, bleibt die Maschine stillstehen. Es wird keine Kugel gewogen, keine Schokolade geschmolzen und keine Nuss aufgelegt. Erst wenn der Verpacker eine Praline in seine Schachtel legen möchte, rückt das Band ein Stück vor. Jede Praline durchläuft die Stationen genau dann, wenn sie am Ende gebraucht wird.

Dieses Prinzip nennen wir Lazy Evaluation (träge oder faule Auswertung). In Rust sind Iteratoren genau nach diesem Prinzip gebaut.

1. Lernziele – Das wirst du heute lernen

• Das Konzept des Iterators: Du verstehst, wie Daten Schritt für Schritt fließen.
• Die drei Iterationsarten: Du lernst den Unterschied zwischen .iter(), .iter_mut() und .into_iter() bezüglich des Speichers.
• Einfache Adapter nutzen: Du filterst Daten mit filter() und transformierst sie mit map().
• Daten konsumieren: Du sammelst die fertigen Elemente mit collect() wieder ein.
• Typische Compilerfehler: Du erfährst, wie du Speicherfehler bei Iteratoren verhinderst.

2. Was ist ein Iterator?

Ein Iterator ist in Rust ein Hilfsobjekt, das uns nacheinander Elemente aus einer Sammlung (wie einem Vektor) liefert.

Das Herzstück ist das Iterator-Trait aus der Standardbibliothek. Es hat im Wesentlichen diese einfache Struktur:

#![allow(unused)]
fn main() {
pub trait Iterator {
    // Welchen Typ von Elementen liefert der Iterator?
    type Item;

    // Liefert das nächste Element
    fn next(&mut self) -> Option<Self::Item>;
}
}

Wenn du next() aufrufst, passiert Folgendes:

• Gibt es noch ein Element, erhältst du Some(element).
• Ist das Ende der Sammlung erreicht, erhältst du None.

Schauen wir uns das in einem lauffähigen Beispiel an:

fn main() {
    let obst = vec!["Apfel", "Birne"];
    
    // Wir erzeugen einen Iterator mit .iter()
    let mut obst_iterator = obst.iter();

    // Wir fragen manuell nach den Elementen:
    assert_eq!(obst_iterator.next(), Some(&"Apfel"));
    assert_eq!(obst_iterator.next(), Some(&"Birne"));
    assert_eq!(obst_iterator.next(), None); // Ende!
}

Eine for-Schleife in Rust macht unter der Haube exakt das: Sie wandelt eine Sammlung in einen Iterator um und ruft in einer while let Some(...)-Schleife so lange next() auf, bis None kommt.

3. Die drei Iterationsarten: Wer besitzt die Daten?

Da Rust sehr genau auf die Speicherverwaltung achtet, gibt es drei verschiedene Möglichkeiten, einen Iterator aus einer Sammlung zu erzeugen:

Schauen wir uns den Unterschied im Code an:

fn main() {
    let mut zahlen = vec![1, 2, 3];

    // 1. .iter() -> Wir lesen nur
    for &z in zahlen.iter() {
        println!("Zahl: {}", z);
    }
    // zahlen ist hier immer noch gültig!

    // 2. .iter_mut() -> Wir verdoppeln die Werte im Vektor
    for z in zahlen.iter_mut() {
        *z *= 2; // Dereferenzierung, um den Wert im Speicher zu ändern
    }

    // 3. .into_iter() -> Wir konsumieren den Vektor
    for z in zahlen.into_iter() {
        println!("Konsumiert: {}", z);
    }

    // FEHLER! zahlen existiert hier nicht mehr, da der Besitz übertragen wurde!
    // println!("{:?}", zahlen);
}

4. Adapter: Die Stationen am Fließband

Adapter sind Methoden, die einen Iterator nehmen und einen neuen Iterator zurückgeben. Sie sind die “Bearbeitungsstationen”. Weil sie träge (lazy) sind, tun sie von alleine nichts.

1. filter (Aussortieren)

Lass nur Elemente durch, die eine Bedingung erfüllen:

#![allow(unused)]
fn main() {
let zahlen = vec![1, 2, 3, 4, 5];
// Nur ungerade Zahlen behalten
let ungerade = zahlen.iter().filter(|&&x| x % 2 != 0);
}

2. map (Umformen)

Transformiere jedes Element:

#![allow(unused)]
fn main() {
let zahlen = vec![1, 2, 3];
// Verdoppele jede Zahl
let verdoppelt = zahlen.iter().map(|x| x * 2);
}

3. take (Begrenzen)

Nimm nur die ersten N Elemente:

#![allow(unused)]
fn main() {
let zahlen = vec![10, 20, 30, 40];
let erste_zwei = zahlen.iter().take(2); // liefert 10, 20
}

5. Konsumenten: Die Pralinenschachtel füllen

Damit das Fließband anläuft, brauchen wir einen Konsumenten. Er ruft die Elemente ab und erzeugt das Endergebnis.

Der wichtigste Konsument ist .collect(). Er sammelt die Elemente wieder in eine konkrete Datenstruktur (wie einen Vec). Weil collect so flexibel ist, müssen wir dem Compiler oft sagen, welche Struktur wir wollen:

fn main() {
    let start_zahlen = vec![1, 2, 3, 4, 5, 6];

    // Die gesamte Kette:
    // Wir filtern gerade Zahlen, multiplizieren sie mit 10 und sammeln sie in einen neuen Vektor.
    let ergebnis: Vec<i32> = start_zahlen
        .into_iter()
        .filter(|x| x % 2 == 0) // filtert 2, 4, 6
        .map(|x| x * 10)        // macht daraus 20, 40, 60
        .collect();             // startet das Fließband!

    println!("Ergebnis: {:?}", ergebnis); // [20, 40, 60]
}

6. Compilerfehler-Show: Typische Fehler verstehen

Ein sehr häufiger Fehler betrifft die Besitzverhältnisse beim Umwandeln in einen Iterator.

fn main() {
    let namen = vec![String::from("Thorsten"), String::from("Antigravity")];

    // Wir nutzen into_iter()
    let mut iterator = namen.into_iter();
    
    while let Some(n) = iterator.next() {
        println!("Hallo {}", n);
    }

    // Wir versuchen, die Liste danach nochmals zu nutzen:
    println!("Anzahl: {}", namen.len()); // Compilerfehler!
}

Die Fehlermeldung des Compilers:

error[E0382]: borrow of moved value: `namen`
  --> src/main.rs:11:28
   |
2  |     let namen = vec![String::from("Thorsten"), String::from("Antigravity")];
   |         ----- move occurs because `namen` has type `Vec<String>`, which does not implement the `Copy` trait
3  | 
4  |     let mut iterator = namen.into_iter();
   |                              ----------- `namen` moved due to this method call
...
11 |     println!("Anzahl: {}", namen.len());
   |                            ^^^^^^^^^^^ value borrowed here after move

Die Lösung:

Da wir die Liste danach noch benötigen, dürfen wir den Besitz nicht abgeben. Wir ersetzen into_iter() durch .iter():

#![allow(unused)]
fn main() {
// .iter() leiht die Elemente nur aus. Die Liste bleibt gültig!
let mut iterator = namen.iter();
}

7. Zusammenfassung

1. Iteratoren sind träge Datenfließbänder. Sie berechnen Werte erst, wenn ein Konsument sie anfordert.
2. Das Iterator-Trait verlangt nur die Implementierung der Methode next().
3. .iter() leiht unveränderlich aus, .iter_mut() veränderlich, und .into_iter() konsumiert die Sammlung.
4. Adapter (map, filter, take) transformieren den Datenstrom.
5. Konsumenten (collect, sum) starten den Fluss und sammeln das Ergebnis.

Kapitel 15: Iteratoren und funktionale Programmierung – Deklarative Datenströme und eigene Iteratoren

In der professionellen Software-Entwicklung ermöglichen Iteratoren den Übergang von einem imperativen Programmierstil (wie Schleifen) zu einem deklarativen Programmierstil (beschreiben, was getan werden soll, nicht wie es im Detail auf Maschinenebene abläuft). Dies reduziert Fehlerquellen (z. B. Off-by-One-Fehler bei Schleifen-Indizes) und macht den Code mathematisch sauberer und einfacher zu warten.

1. Lernziele – Das wirst du heute lernen

• Eigene Iteratoren entwerfen: Sie implementieren das Iterator-Trait für benutzerdefinierte Datenstrukturen.
• Fortgeschrittene Adapter anwenden: Sie nutzen skip, zip und flat_map zur Lösung komplexer Transformationen.
• Akkumulatoren nutzen (fold & reduce): Sie aggregieren Datenströme elegant auf einen einzigen Endwert.
• Unendliche Iteratoren steuern: Sie arbeiten sicher mit unendlichen Datenquellen.
• Das IntoIterator-Trait implementieren: Sie machen eigene Typen direkt in for-Schleifen nutzbar.

2. Eigene Iteratoren implementieren

Um das Iterator-Trait für eine eigene Datenstruktur zu implementieren, müssen wir einen assoziierten Typ Item definieren und die Methode next schreiben.

Lassen Sie uns eine Struktur entwerfen, die die Fibonacci-Folge berechnet:

struct Fibonacci {
    aktuell: u64,
    naechste: u64,
}

impl Fibonacci {
    fn new() -> Self {
        Fibonacci { aktuell: 0, naechste: 1 }
    }
}

// Wir implementieren das Iterator-Trait
impl Iterator for Fibonacci {
    // Der Iterator liefert u64-Zahlen
    type Item = u64;

    fn next(&mut self) -> Option<Self::Item> {
        let neuer_wert = self.aktuell + self.naechste;
        self.aktuell = self.naechste;
        self.naechste = neuer_wert;

        // Fibonacci-Zahlen sind theoretisch unendlich,
        // daher geben wir immer Some zurück und niemals None.
        Some(self.aktuell)
    }
}

fn main() {
    // Da der Iterator unendlich ist, MÜSSEN wir ihn mit take begrenzen!
    let erste_fib_zahlen: Vec<u64> = Fibonacci::new()
        .take(8)
        .collect();

    println!("Die ersten 8 Fibonacci-Zahlen: {:?}", erste_fib_zahlen);
    // Ausgabe: [1, 1, 2, 3, 5, 8, 13, 21]
}

3. Fortgeschrittene Adapter: Werkzeuge des Architekten

1. flat_map (Verschachtelungen auflösen)

Wenn Sie eine Struktur transformieren, die wiederum Listen enthält, erzeugt ein einfaches map einen verschachtelten Iterator (z. B. Iterator<Item = Vec<T>>). flat_map wendet die Transformation an und flacht das Ergebnis direkt ab:

fn main() {
    let worte = vec!["Hallo", "Welt"];
    
    // Wir zerlegen jedes Wort in seine Buchstaben und flachen das Ergebnis ab
    let buchstaben: Vec<char> = worte.into_iter()
        .flat_map(|w| w.chars())
        .collect();

    println!("Buchstaben: {:?}", buchstaben);
    // Ausgabe: ['H', 'a', 'l', 'l', 'o', 'W', 'e', 'l', 't']
}

2. inspect (Fehlersuche im Datenstrom)

Da Adapter lazy sind, ist das Debuggen von verketteten Iteratoren manchmal schwierig. inspect erlaubt es Ihnen, eine Funktion aufzurufen (z. B. ein println!), ohne den Datenstrom zu verändern oder die Trägheit aufzuheben:

#![allow(unused)]
fn main() {
let zahlen = vec![1, 2, 3];
let _ergebnis: Vec<i32> = zahlen.into_iter()
    .inspect(|x| println!("Vorher: {}", x))
    .map(|x| x * 2)
    .inspect(|x| println!("Nachher: {}", x))
    .collect();
}

4. Aggregieren mit fold und reduce

fold (Falten mit Startwert)

fold ist der mächtigste Konsument. Jedes Element wird nacheinander mit einem Akkumulator verrechnet:

#![allow(unused)]
fn main() {
let daten = vec![1, 2, 3, 4];
// Summe der Quadrate berechnen: Startwert ist 0
let summe_quadrate = daten.iter().fold(0, |acc, &x| acc + (x * x)); // 30
}

reduce (Falten ohne Startwert)

Nutzt das erste Element der Sequenz als Startwert. Gibt Option zurück (falls der Iterator leer war):

#![allow(unused)]
fn main() {
let daten = vec![10, 20, 30];
let maximum = daten.into_iter().reduce(|acc, x| if x > acc { x } else { acc });
println!("Maximum: {:?}", maximum); // Some(30)
}

5. Das IntoIterator-Trait für eigene Collections

Wenn Sie eine eigene Datenstruktur (z. B. eine custom Liste) entwerfen, möchten Sie, dass Ihre Anwender diese direkt in einer for-Schleife nutzen können. Dazu müssen Sie IntoIterator implementieren:

#![allow(unused)]
fn main() {
struct EigenerStapel {
    elemente: Vec<i32>,
}

// Wir implementieren IntoIterator für das Konsumieren des Stapels
impl IntoIterator for EigenerStapel {
    type Item = i32;
    type IntoIter = std::vec::IntoIter<Self::Item>;

    fn into_iter(self) -> Self::IntoIter {
        self.elemente.into_iter()
    }
}
}

Kapitel 15 - Hardware-Sicht: Iteratoren unter der Lupe von CPU und RAM

Hallo Thorsten! Nachdem wir uns mit der mathematischen Eleganz und den deklarativen Mustern von Iteratoren beschäftigt haben, reißen wir jetzt die Motorhaube auf.

In vielen Programmiersprachen sind Iteratoren ein zweischneidiges Schwert: Sie machen den Code zwar schöner, kosten aber CPU-Zyklen und RAM, da für jeden Schritt Objekte allokiert und virtuelle Methoden aufgerufen werden müssen. Rust verspricht hier Zero-Cost Abstractions (abstraktionsfreie Laufzeitkosten).

Lass uns untersuchen, wie der Compiler Iteratoren übersetzt und warum sie auf Hardware-Ebene oft schneller sind als klassische Schleifen.

1. Die Vermeidung von Bounds Checking (Sicherheitsüberprüfungen)

Ein großer Unterschied zwischen einer klassischen indizierten Schleife und einem Iterator betrifft die Sicherheitsprüfungen des Compilers.

Die klassische Index-Schleife:

#![allow(unused)]
fn main() {
let daten = [1, 2, 3, 4, 5];
for i in 0..daten.len() {
    let x = daten[i]; // Zugriff über Index
    // ...
}
}

Da Rust Speichersicherheit garantiert, darf das Programm niemals über die Grenzen des Arrays hinauslesen (Buffer Overflow). Der Compiler muss daher bei jedem einzelnen Schleifendurchlauf zur Laufzeit prüfen: Ist der Index i kleiner als daten.len()?

• Hardware-Auswirkung: Diese ständigen Vergleiche und Verzweigungen (Bounds Checking) kosten CPU-Zyklen und können das Pipelining des Prozessors stören.

Die Iterator-Alternative:

#![allow(unused)]
fn main() {
let daten = [1, 2, 3, 4, 5];
for x in daten.iter() {
    // Direkter Zugriff über den Iterator
}
}

Ein Iterator weiß intern durch seine Struktur genau, wie viele Elemente er hat. Er greift über sichere, rohe Zeiger auf die Elemente zu und stoppt exakt am Ende.

• Hardware-Auswirkung: Der Compiler analysiert die Iterator-Struktur und entfernt sämtliche Bounds Checks vollständig aus dem Maschinencode. Es gibt keine Laufzeitprüfungen mehr. Das Programm läuft auf nackter Hardware-Geschwindigkeit!

2. Inlining und Loop Unrolling: Der Weg zum flachen Maschinencode

Wenn du Adapterketten mit Closures wie map(|x| x * 2) schreibst, sieht das nach viel Arbeit für die CPU aus. Doch der Compiler optimiert dies radikal:

1. Closure Inlining: Der Compiler kopiert den Code der Closure direkt in den Schleifenkörper. Es gibt keinen Funktionsaufruf, keine Registerverschiebungen und keinen Stack-Overhead.
2. Monomorphisierung des Modul-Typs: Ein Iterator wie Map<Filter<Iter<i32>, Closure1>, Closure2> ist ein extrem komplexer, verschachtelter Typ zur Compilezeit. Der Compiler löst diese Verschachtelung vollständig auf und generiert eine flache, lineare Assemblerschleife.

Tatsächlich kompiliert eine Iterator-Kette im Release-Modus (cargo build --release) zu exakt demselben, hocheffizienten Assembler-Code wie eine handgeschriebene, optimierte C-Schleife.

3. Statischer vs. Dynamischer Dispatch bei Iteratoren

Manchmal steht man vor dem Problem, dass man je nach Bedingung unterschiedliche Iteratoren zurückgeben möchte:

#![allow(unused)]
fn main() {
// Das funktioniert standardmäßig NICHT, da die beiden Zweige 
// unterschiedliche konkrete Typen erzeugen!
/*
fn erstelle_iterator(cond: bool) -> impl Iterator<Item = i32> {
    let daten = vec![1, 2, 3];
    if cond {
        daten.into_iter().map(|x| x * 2) // Typ A
    } else {
        daten.into_iter().filter(|x| x % 2 == 0) // Typ B
    }
}
*/
}

Da Rust zur Compilezeit die exakte Größe und den Typ des Rückgabewerts kennen muss (Statischer Dispatch), verbietet der Compiler das.

Die Lösung: Dynamic Dispatch auf dem Heap

Um dieses Problem zu lösen, müssen wir den Iterator hinter einem Smart Pointer auf dem Heap verstecken (Box) und dynamischen Dispatch nutzen (dyn):

#![allow(unused)]
fn main() {
fn erstelle_iterator(cond: bool) -> Box<dyn Iterator<Item = i32>> {
    let daten = vec![1, 2, 3];
    if cond {
        Box::new(daten.into_iter().map(|x| x * 2))
    } else {
        Box::new(daten.into_iter().filter(|x| x % 2 == 0))
    }
}
}

Die Hardware-Kosten von Dynamic Dispatch:

Wenn Sie Box<dyn Iterator> verwenden, geben Sie das Versprechen der Zero-Cost Abstraction teilweise auf:

1. Heap-Allokation: Die Box erzwingt das Speichern des Iterators auf dem Heap statt auf dem Stack. Das Erstellen kostet Allokationszeit.
2. Vtable-Dereferenzierung: Jeder Aufruf von .next() erfolgt über einen Zeiger in eine virtuelle Methodentabelle (Vtable). Die CPU kann den Aufruf nicht vorab optimieren (Inlining ist unmöglich).
3. Instruction Cache Misses: Der Sprung über die Vtable kann das Vorladen von Instruktionen im CPU-Cache erschweren.

Systemprogrammierer-Regel: Nutzen Sie statischen Dispatch (impl Iterator) wann immer möglich. Verwenden Sie Dynamic Dispatch (Box<dyn Iterator>) nur dann, wenn unterschiedliche Pfade zur Laufzeit unumgänglich sind.

4. Verweis auf Übungen

Sie haben nun gelernt, wie Sie Iteratoren anwenden, eigene Datenströme implementieren und wie der Compiler diese hardwareseitig optimiert. Jetzt ist es an der Zeit, dieses Wissen in der Praxis zu testen.

Wechseln Sie in das Verzeichnis: exercises/04_collections/ (oder ein entsprechendes Iterator-Verzeichnis Ihres Übungs-Workspaces).

Dort finden Sie praktische Aufgaben, bei denen Sie:

1. Klassische Schleifen in funktionale Iterator-Ketten umschreiben müssen.
2. Einen eigenen Generator-Iterator implementieren sollen.
3. Die Speicher-Performance von .iter() und .into_iter() vergleichen.