Iteratori personalizzati in Rust

Nella pagina sugli iteratori hai usato gli iteratori che ti dà la libreria standard: vec.iter(), .map(), .filter(), .sum(). Ma puoi anche creare i tuoi iteratori. Un conto alla rovescia, i numeri di Fibonacci, le pagine di un report, le righe di un formato di file tutto tuo: qualsiasi cosa che consegna valori uno alla volta può essere un iteratore.

La buona notizia: scrivi un solo metodo, next. Rust poi ti regala tutti gli adattatori (map, filter, take, sum, zip e decine di altri). Pensalo come un distributore di biglietti per la coda. Tu costruisci il pezzo che stampa il biglietto successivo. La fila, il display e il cartello «stiamo servendo il numero…» funzionano da soli.

Il tuo primo iteratore: un conto alla rovescia

Per rendere un tipo un iteratore, implementa il trait Iterator. Servono due cose:

• type Item: che tipo di valore consegna l’iteratore (per saperne di più sui tipi associati, vedi Trait avanzati).
• fn next(&mut self) -> Option<Self::Item>: restituisce Some(valore) per il valore successivo, oppure None quando non ce ne sono più.

struct Countdown {
    current: u32,
}

impl Countdown {
    fn new(from: u32) -> Self {
        Countdown { current: from }
    }
}

impl Iterator for Countdown {
    type Item = u32;

    fn next(&mut self) -> Option<u32> {
        if self.current == 0 {
            None // finito
        } else {
            let value = self.current;
            self.current -= 1;
            Some(value)
        }
    }
}

fn main() {
    let mut countdown = Countdown::new(3);

    println!("{:?}", countdown.next());
    println!("{:?}", countdown.next());
    println!("{:?}", countdown.next());
    println!("{:?}", countdown.next());
    println!("{:?}", countdown.next());

    for n in Countdown::new(3) {
        println!("{}...", n);
    }
    println!("Decollo!");
}

Output:

Some(3)
Some(2)
Some(1)
None
None
3...
2...
1...
Decollo!

▶ Provalo tu

Alcune cose da notare:

• next prende &mut self perché modifica l’iteratore. La struct si ricorda a che punto è (current), e ogni chiamata la fa avanzare. Ecco perché countdown deve essere let mut.
• Restituire None significa «ho finito». Un ciclo for chiama next più e più volte e si ferma al primo None.
• Il nostro conto alla rovescia continua a restituire None anche dopo aver finito. È una gentilezza, ma il trait non la richiede: alcuni iteratori potrebbero ricominciare. Se ti serve questa garanzia, chiama .fuse() su qualsiasi iteratore.

Un iteratore infinito: Fibonacci

Un iteratore non deve per forza finire. La successione di Fibonacci (0, 1, 1, 2, 3, 5, 8, …) va avanti all’infinito: ogni numero è la somma dei due precedenti. L’iteratore deve solo ricordare gli ultimi due numeri:

struct Fibonacci {
    current: u64,
    next: u64,
}

impl Fibonacci {
    fn new() -> Self {
        Fibonacci { current: 0, next: 1 }
    }
}

impl Iterator for Fibonacci {
    type Item = u64;

    fn next(&mut self) -> Option<u64> {
        let value = self.current;
        // checked_add restituisce None in caso di overflow, e `?` passa avanti quel None,
        // così l'iteratore finisce invece di andare in crash quando i numeri diventano troppo grandi.
        let new_next = self.current.checked_add(self.next)?;
        self.current = self.next;
        self.next = new_next;
        Some(value)
    }
}

fn main() {
    let first_ten: Vec<u64> = Fibonacci::new().take(10).collect();
    println!("{:?}", first_ten);
}

Output:

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

▶ Provalo tu

La chiave è .take(10). Senza, collect() proverebbe a raccogliere l’intera successione. Con un iteratore infinito, limitalo sempre con qualcosa come take, take_while o find.

Tutti gli adattatori, gratis

Ecco la parte migliore. Il trait Iterator ha circa 75 metodi, e tutti tranne next hanno un’implementazione predefinita costruita sopra next. Quindi, nel momento in cui scrivi next, il tuo tipo può usarli tutti:

struct Countdown {
    current: u32,
}

impl Countdown {
    fn new(from: u32) -> Self {
        Countdown { current: from }
    }
}

impl Iterator for Countdown {
    type Item = u32;

    fn next(&mut self) -> Option<u32> {
        if self.current == 0 {
            None
        } else {
            let value = self.current;
            self.current -= 1;
            Some(value)
        }
    }
}

fn main() {
    let total: u32 = Countdown::new(5).sum();
    println!("Somma: {}", total);

    let evens: Vec<u32> = Countdown::new(10).filter(|n| n % 2 == 0).collect();
    println!("Pari: {:?}", evens);

    let labels: Vec<String> = Countdown::new(3).map(|n| format!("T-{}", n)).collect();
    println!("Etichette: {:?}", labels);

    let multiple = Countdown::new(100).find(|n| n % 7 == 0);
    println!("Primo multiplo di 7: {:?}", multiple);

    let pairs: Vec<(u32, char)> = Countdown::new(3).zip(['a', 'b', 'c']).collect();
    println!("Abbinati: {:?}", pairs);
}

Output:

Somma: 15
Pari: [10, 8, 6, 4, 2]
Etichette: ["T-3", "T-2", "T-1"]
Primo multiplo di 7: Some(98)
Abbinati: [(3, 'a'), (2, 'b'), (1, 'c')]

▶ Provalo tu

Questo è un ottimo esempio del perché i trait di Rust sono così utili. Ci metti un piccolo metodo, e ne esce una cassetta degli attrezzi enorme.

Gli iteratori sono pigri

Adattatori come map e take da soli non fanno niente. Costruiscono solo un «piano». Il lavoro avviene solo quando qualcosa consuma l’iteratore: un ciclo for, collect, sum e così via. Dimostriamolo con un iteratore che stampa qualcosa ogni volta che viene chiamato next:

struct Noisy {
    n: u32,
}

impl Iterator for Noisy {
    type Item = u32;

    fn next(&mut self) -> Option<u32> {
        self.n += 1;
        println!("  chiamato next(), restituisce {}", self.n);
        Some(self.n)
    }
}

fn main() {
    println!("Costruisco la catena...");
    let chain = Noisy { n: 0 }.map(|x| x * 10).take(3);
    println!("Non è ancora partito niente. Ora consumo:");

    for value in chain {
        println!("ricevuto {}", value);
    }
    println!("Fatto");
}

Output:

Costruisco la catena...
Non è ancora partito niente. Ora consumo:
  chiamato next(), restituisce 1
ricevuto 10
  chiamato next(), restituisce 2
ricevuto 20
  chiamato next(), restituisce 3
ricevuto 30
Fatto

▶ Provalo tu

Due lezioni. Primo: costruire la catena non ha stampato niente, nessuna chiamata a next(). Secondo: i valori passano uno alla volta: un next, un map, un ricevuto, poi il valore successivo. Non c’è nessuna lista nascosta nel mezzo. E Noisy non finisce mai, eppure il programma termina: dopo tre elementi, take(3) smette semplicemente di chiedere.

Far funzionare la tua collezione nei cicli for

Finora le nostre struct erano iteratori. Spesso però hai una collezione, cioè una struct che contiene elementi, e vuoi che si possa scorrerla come si scorre un Vec. Per questo implementi IntoIterator. È il trait che un ciclo for usa dietro le quinte: for x in cosa in realtà chiama cosa.into_iter().

Di solito le collezioni offrono tre modi per scorrerle, e conviene vederli sul tuo tipo:

Scrivi	Metodo dietro le quinte	Ogni elemento è	La collezione dopo
for s in &playlist	playlist.iter()	&String (sola lettura)	ancora utilizzabile
for s in &mut playlist	playlist.iter_mut()	&mut String (modificabile)	ancora utilizzabile
for s in playlist	playlist.into_iter()	String (posseduto)	spostata, non c’è più

Ecco una Playlist che li supporta tutti e tre. La nostra struct tiene le canzoni in un Vec, quindi possiamo consegnare gli iteratori del Vec invece di scriverne di nuovi:

struct Playlist {
    songs: Vec<String>,
}

impl Playlist {
    fn iter(&self) -> std::slice::Iter<'_, String> {
        self.songs.iter()
    }

    fn iter_mut(&mut self) -> std::slice::IterMut<'_, String> {
        self.songs.iter_mut()
    }
}

// Fa funzionare `for song in &playlist`
impl<'a> IntoIterator for &'a Playlist {
    type Item = &'a String;
    type IntoIter = std::slice::Iter<'a, String>;

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

// Fa funzionare `for song in &mut playlist`
impl<'a> IntoIterator for &'a mut Playlist {
    type Item = &'a mut String;
    type IntoIter = std::slice::IterMut<'a, String>;

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

// Fa funzionare `for song in playlist` (e consuma la playlist)
impl IntoIterator for Playlist {
    type Item = String;
    type IntoIter = std::vec::IntoIter<String>;

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

fn main() {
    let mut playlist = Playlist {
        songs: vec![String::from("intro"), String::from("main theme"), String::from("outro")],
    };

    for song in &playlist {
        println!("Leggo: {}", song);
    }

    for song in &mut playlist {
        *song = song.to_uppercase();
    }

    println!("La più lunga: {:?}", playlist.iter().max_by_key(|s| s.len()));

    for song in playlist {
        println!("Prendo: {}", song);
    }
    // `playlist` è stata spostata dall'ultimo ciclo, quindi qui non si può più usare.
}

Output:

Leggo: intro
Leggo: main theme
Leggo: outro
La più lunga: Some("MAIN THEME")
Prendo: INTRO
Prendo: MAIN THEME
Prendo: OUTRO

▶ Provalo tu

I titoli delle canzoni restano in inglese perché max_by_key(|s| s.len()) conta i byte. Sono tante righe, ma ogni impl ha la stessa forma: dici cos’è Item, dici che tipo di iteratore restituisci (IntoIter) e lo restituisci. Il 'a è un lifetime (durata): dice «gli elementi presi in prestito vivono quanto la playlist presa in prestito». Puoi copiare questo schema per quasi ogni collezione che avvolge un Vec.

Andare all’indietro e conoscere la lunghezza

Vale la pena conoscere altri due trait. Non ti servono spesso, ma adattatori come .rev() e .len() dipendono da loro:

• DoubleEndedIterator aggiunge next_back, che prende gli elementi dalla fine. Sblocca .rev().
• ExactSizeIterator promette che l’iteratore sa esattamente quanti elementi restano. Sblocca .len(). In Iterator fornisci anche un size_hint preciso.

// Produce low, low+1, ..., high-1 (come il range low..high)
struct Between {
    low: u32,
    high: u32,
}

impl Iterator for Between {
    type Item = u32;

    fn next(&mut self) -> Option<u32> {
        if self.low >= self.high {
            return None;
        }
        let value = self.low;
        self.low += 1;
        Some(value)
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        let left = self.high.saturating_sub(self.low) as usize;
        (left, Some(left))
    }
}

impl DoubleEndedIterator for Between {
    fn next_back(&mut self) -> Option<u32> {
        if self.low >= self.high {
            return None;
        }
        self.high -= 1;
        Some(self.high)
    }
}

impl ExactSizeIterator for Between {}

fn main() {
    let backwards: Vec<u32> = Between { low: 1, high: 6 }.rev().collect();
    println!("{:?}", backwards);

    let mut both_ends = Between { low: 1, high: 6 };
    println!("davanti {:?}, dietro {:?}", both_ends.next(), both_ends.next_back());
    println!("ne restano {}", both_ends.len());
}

Output:

[5, 4, 3, 2, 1]
davanti Some(1), dietro Some(5)
ne restano 3

▶ Provalo tu

Le due estremità si muovono l’una verso l’altra, e l’iteratore finisce quando si incontrano. impl ExactSizeIterator for Between {} è vuoto: len() usa il size_hint che hai già scritto.

Scorciatoie: from_fn e successors

Scrivere una struct e un impl è perfetto per gli iteratori che riusi. Per un iteratore usa e getta, la libreria standard ha due helper in std::iter:

• iter::from_fn(closure): chiama la tua closure ogni volta che serve un valore. La closure restituisce Some(valore) o None, proprio come next.
• iter::successors(primo, closure): parte da un primo valore, e la closure calcola ogni valore successivo a partire dal precedente. Restituire None lo fa finire.

use std::iter;

fn main() {
    // from_fn: la closure tiene il proprio stato (count)
    let mut count = 3;
    let countdown: Vec<u32> = iter::from_fn(|| {
        if count == 0 {
            None
        } else {
            count -= 1;
            Some(count + 1)
        }
    })
    .collect();
    println!("{:?}", countdown);

    // successors: ogni valore si calcola dal precedente
    let powers: Vec<u32> = iter::successors(Some(1u32), |&n| n.checked_mul(10)).collect();
    println!("{:?}", powers);

    // Fibonacci in una riga: porta avanti gli ultimi due numeri come coppia
    let fib: Vec<u64> = iter::successors(Some((0u64, 1u64)), |&(a, b)| Some((b, a + b)))
        .map(|(a, _)| a)
        .take(10)
        .collect();
    println!("{:?}", fib);
}

Output:

[3, 2, 1]
[1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

▶ Provalo tu

powers si ferma da solo: la potenza di dieci successiva, 10.000.000.000, non sta in un u32, quindi checked_mul restituisce None e l’iteratore finisce. Una buona regola: usa queste scorciatoie dentro una sola funzione, e scrivi una struct con un nome quando altro codice deve creare l’iteratore, o quando ha molto stato.

Errori comuni

Dimenticare mut quando chiami next a mano. next modifica l’iteratore, quindi la variabile deve essere mutabile:

let countdown = Countdown { current: 3 };
println!("{:?}", countdown.next());

error[E0596]: cannot borrow `countdown` as mutable, as it is not declared as mutable
  --> src/main.rs:20:22
   |
20 |     println!("{:?}", countdown.next());
   |                      ^^^^^^^^^ cannot borrow as mutable
   |
help: consider changing this to be mutable
   |
19 |     let mut countdown = Countdown { current: 3 };
   |         +++

Il compilatore dice che non può prendere countdown in prestito come mutabile, perché non è dichiarato mut. Aggiungi mut. (Un ciclo for non ne ha bisogno: prende l’iteratore e se ne occupa lui.)

Dimenticare type Item. Il trait deve sapere che cosa consegni:

error[E0046]: not all trait items implemented, missing: `Item`
 --> src/main.rs:5:1
  |
5 | impl Iterator for Countdown {
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^ missing `Item` in implementation
  |
  = help: implement the missing item: `type Item = /* Type */;`

Qui rustc segnala che nell’implementazione manca Item. Aggiungi type Item = u32; (o qualunque cosa produca il tuo iteratore) dentro l’impl.

Raccogliere un iteratore infinito. Fibonacci::new().collect::<Vec<_>>() (senza take) compila senza problemi, ma non finisce mai in modo utile: gira finché i numeri non vanno in overflow, o per sempre se il tuo next non restituisce mai None. Il compilatore non può accorgersene. Quando un iteratore potrebbe essere infinito, aggiungi sempre take, take_while o find prima di consumarlo.

Riepilogo

• Implementa Iterator con type Item e fn next(&mut self) -> Option<Self::Item>. Restituisci None quando hai finito.
• Una volta che esiste next, ottieni gratis map, filter, take, sum, zip e decine di altri metodi.
• Gli iteratori sono pigri: non succede niente finché un ciclo for, collect, sum ecc. non li consuma, e gli elementi passano uno alla volta.
• Implementa IntoIterator per &MioTipo, &mut MioTipo e MioTipo per supportare cicli for che prendono in prestito, prendono in prestito in modo mutabile o consumano.
• DoubleEndedIterator abilita .rev(); ExactSizeIterator abilita .len().
• Per iteratori veloci usa e getta, usa std::iter::from_fn o std::iter::successors.

Verifica veloce

Verifica veloce

1. Che cosa deve restituire next quando l'iteratore non ha più elementi?

0 Un Vec vuoto None Deve andare in panic

2. Dopo aver implementato solo next, puoi chiamare .map() e .sum() sul tuo iteratore?

Sì, sono metodi predefiniti costruiti su next No, devi implementarli uno per uno Solo se implementi anche IntoIterator

3. Nell'esempio sulla valutazione pigra, quando viene chiamato next() per la prima volta?

Quando scrivi .map() Quando scrivi .take(3) Quando il ciclo for comincia a consumare la catena

4. Quale impl fa funzionare for song in &playlist?

impl Iterator for Playlist impl<'a> IntoIterator for &'a Playlist impl IntoIterator for Playlist impl DoubleEndedIterator for Playlist

5. Quale trait ti serve perché .rev() funzioni sul tuo iteratore?

ExactSizeIterator Clone IntoIterator DoubleEndedIterator

Punteggio: 0 / 5

Per approfondire

• Processing a Series of Items with Iterators — The Rust Book (in inglese): come funzionano Iterator e next, e perché gli iteratori sono pigri.
• Il modulo std::iter (in inglese): la guida ufficiale agli iteratori, con una sezione su come implementare i tuoi e su IntoIterator.
• Il trait Iterator — documentazione della std (in inglese): tutti gli adattatori che ottieni gratis una volta scritto next.
• Iterators — Rust by Example (in inglese): un breve esempio di iteratore di Fibonacci che puoi eseguire e modificare.
• std::iter::successors (in inglese): la documentazione per costruire un iteratore da un valore iniziale e una regola per il «successivo».