Iteradores personalizados em Rust

Na página de Iteradores você usou os iteradores que a biblioteca padrão oferece: vec.iter(), .map(), .filter(), .sum(). Mas você também pode criar os seus próprios iteradores. Uma contagem regressiva, os números de Fibonacci, as páginas de um relatório, as linhas de um formato de arquivo próprio: qualquer coisa que entregue valores um de cada vez pode virar um iterador.

A boa notícia: você só escreve um método, o next. Em troca, o Rust te dá todos os adaptadores (map, filter, take, sum, zip e dezenas de outros) de graça. Pense numa máquina de senhas. Você constrói só a parte que imprime a próxima senha. A fila, o painel e o aviso de “senha atual” funcionam sozinhos.

Seu primeiro iterador: uma contagem regressiva

Para transformar um tipo em iterador, implemente a trait (característica) Iterator. Ela pede duas coisas:

• type Item: o tipo de valor que o iterador entrega (veja Traits avançadas para saber mais sobre tipos associados).
• fn next(&mut self) -> Option<Self::Item>: retorna Some(valor) com o próximo valor, ou None quando os valores acabam.

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 // acabou
        } 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!("Decolar!");
}

Saída:

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

▶ Experimente você mesmo

Algumas coisas para reparar:

• next recebe &mut self porque ele altera o iterador. A struct lembra onde parou (current), e cada chamada avança um passo. Por isso countdown precisa ser let mut.
• Retornar None significa “terminei”. Um laço for chama next repetidas vezes e para no primeiro None.
• A nossa contagem continua retornando None depois de terminar. Isso é educado, mas a trait não exige: alguns iteradores poderiam recomeçar. Se você precisar dessa garantia, chame .fuse() em qualquer iterador.

Um iterador sem fim: Fibonacci

Um iterador não precisa terminar. A sequência de Fibonacci (0, 1, 1, 2, 3, 5, 8, …) continua para sempre: cada número é a soma dos dois anteriores. O iterador só precisa lembrar os dois últimos números:

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 retorna None se houver overflow, e o `?` repassa esse None,
        // então o iterador termina em vez de quebrar quando os números ficam grandes demais.
        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);
}

Saída:

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

▶ Experimente você mesmo

O segredo está no .take(10). Sem ele, o collect() tentaria juntar a sequência inteira. Com um iterador sem fim, sempre coloque um limite com algo como take, take_while ou find.

Todos os adaptadores, de graça

Agora vem a melhor parte. A trait Iterator tem uns 75 métodos, e todos eles, menos o next, têm implementações padrão construídas em cima do next. Então, no momento em que você escreve o next, o seu tipo já pode usar todos eles:

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!("Soma: {}", total);

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

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

    let multiple = Countdown::new(100).find(|n| n % 7 == 0);
    println!("Primeiro múltiplo de 7: {:?}", multiple);

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

Saída:

Soma: 15
Pares: [10, 8, 6, 4, 2]
Rótulos: ["T-3", "T-2", "T-1"]
Primeiro múltiplo de 7: Some(98)
Combinados: [(3, 'a'), (2, 'b'), (1, 'c')]

▶ Experimente você mesmo

Esse é um ótimo exemplo de por que as traits do Rust são tão úteis. Você escreve um método pequeno e ganha uma caixa de ferramentas enorme.

Iteradores são preguiçosos

Adaptadores como map e take não fazem nada sozinhos. Eles só montam um “plano”. O trabalho acontece apenas quando algo consome o iterador: um laço for, collect, sum e assim por diante. Vamos provar isso com um iterador que imprime uma mensagem toda vez que next é chamado:

struct Noisy {
    n: u32,
}

impl Iterator for Noisy {
    type Item = u32;

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

fn main() {
    println!("Montando a cadeia...");
    let chain = Noisy { n: 0 }.map(|x| x * 10).take(3);
    println!("Nada rodou ainda. Agora consumindo:");

    for value in chain {
        println!("recebi {}", value);
    }
    println!("Pronto");
}

Saída:

Montando a cadeia...
Nada rodou ainda. Agora consumindo:
  next() chamado, entregando 1
recebi 10
  next() chamado, entregando 2
recebi 20
  next() chamado, entregando 3
recebi 30
Pronto

▶ Experimente você mesmo

Duas lições aqui. Primeiro, montar a cadeia não imprimiu nada: nenhuma chamada a next(). Segundo, os valores passam um de cada vez: um next, um map, um recebi, e só então o próximo valor. Não existe nenhuma lista escondida no meio do caminho. E Noisy nunca termina, mas o programa termina: depois de três itens, o take(3) simplesmente para de pedir.

Fazendo a sua coleção funcionar em laços for

Até aqui, as nossas structs eram iteradores. Muitas vezes, porém, você tem uma coleção (uma struct que guarda itens) e quer que as pessoas possam percorrê-la, do mesmo jeito que percorrem um Vec. Para isso, você implementa IntoIterator. É a trait que o laço for usa por baixo dos panos: for x in thing na verdade chama thing.into_iter().

As coleções costumam oferecer três jeitos de percorrer, e ajuda ver os três no seu próprio tipo:

Você escreve	Método por trás	Cada item é	A coleção depois
for s in &playlist	playlist.iter()	&String (só leitura)	continua usável
for s in &mut playlist	playlist.iter_mut()	&mut String (pode alterar)	continua usável
for s in playlist	playlist.into_iter()	String (com ownership)	movida, já era

Aqui está uma Playlist que aceita os três. A nossa struct guarda as músicas em um Vec, então podemos entregar os próprios iteradores do Vec em vez de escrever novos:

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

// Faz `for song in &playlist` funcionar
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()
    }
}

// Faz `for song in &mut playlist` funcionar
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()
    }
}

// Faz `for song in playlist` funcionar (e consome a 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!("Lendo: {}", song);
    }

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

    println!("Mais longa: {:?}", playlist.iter().max_by_key(|s| s.len()));

    for song in playlist {
        println!("Pegando: {}", song);
    }
    // `playlist` foi movida pelo último laço, então não dá para usá-la aqui.
}

Saída:

Lendo: intro
Lendo: main theme
Lendo: outro
Mais longa: Some("MAIN THEME")
Pegando: INTRO
Pegando: MAIN THEME
Pegando: OUTRO

▶ Experimente você mesmo

(Os nomes das músicas ficaram em inglês de propósito: max_by_key(|s| s.len()) compara tamanhos em bytes, e letras acentuadas ocupam 2 bytes em UTF-8.)

São muitas linhas, mas cada impl tem o mesmo formato: diga o que é o Item, diga que tipo de iterador você retorna (IntoIter) e retorne esse iterador. O 'a é um lifetime (tempo de vida): ele diz “os itens emprestados vivem tanto quanto a playlist emprestada”. Você pode copiar esse padrão para quase qualquer coleção que embrulhe um Vec.

Andando para trás e sabendo o tamanho

Vale a pena conhecer mais duas traits. Você não vai precisar delas com frequência, mas adaptadores como .rev() e .len() dependem delas:

• DoubleEndedIterator acrescenta o next_back, que pega itens do final. Ela libera o .rev().
• ExactSizeIterator promete que o iterador sabe exatamente quantos itens faltam. Ela libera o .len(). Você também fornece um size_hint exato no Iterator.

// Entrega low, low+1, ..., high-1 (como o intervalo 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!("início {:?}, fim {:?}", both_ends.next(), both_ends.next_back());
    println!("restam {}", both_ends.len());
}

Saída:

[5, 4, 3, 2, 1]
início Some(1), fim Some(5)
restam 3

▶ Experimente você mesmo

As duas pontas andam uma em direção à outra, e o iterador termina quando elas se encontram. O impl ExactSizeIterator for Between {} é vazio: o len() usa o size_hint que você já escreveu.

Atalhos: from_fn e successors

Escrever uma struct e um impl é ótimo para iteradores que você reaproveita. Para algo rápido e de uso único, a biblioteca padrão tem duas funções auxiliares em std::iter:

• iter::from_fn(closure): chama a sua closure (função anônima) cada vez que um valor é necessário. A closure retorna Some(valor) ou None, igualzinho ao next.
• iter::successors(first, closure): começa com um primeiro valor, e a closure calcula cada valor seguinte a partir do anterior. Retornar None encerra o iterador.

use std::iter;

fn main() {
    // from_fn: a closure guarda o próprio estado (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: cada valor é calculado a partir do anterior
    let powers: Vec<u32> = iter::successors(Some(1u32), |&n| n.checked_mul(10)).collect();
    println!("{:?}", powers);

    // Fibonacci em uma linha: carregue os dois últimos números como um par
    let fib: Vec<u64> = iter::successors(Some((0u64, 1u64)), |&(a, b)| Some((b, a + b)))
        .map(|(a, _)| a)
        .take(10)
        .collect();
    println!("{:?}", fib);
}

Saída:

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

▶ Experimente você mesmo

O powers para sozinho: a próxima potência de dez, 10.000.000.000, não cabe em um u32, então checked_mul retorna None e o iterador termina. Uma boa regra: use esses atalhos dentro de uma única função, e escreva uma struct com nome quando outro código precisar criar o iterador, ou quando ele tiver muito estado.

Erros comuns

Esquecer o mut ao chamar next você mesmo. O next altera o iterador, então a variável precisa ser mutável:

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 };
   |         +++

O compilador diz que não consegue pegar countdown emprestada como mutável, porque ela não foi declarada como mutável. Acrescente o mut. (Um laço for não precisa disso: ele toma posse do iterador e cuida disso para você.)

Esquecer o type Item. A trait precisa saber o que você entrega:

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 */;`

A mensagem diz que nem todos os itens da trait foram implementados: falta o Item. Acrescente type Item = u32; (ou o tipo que o seu iterador entrega) dentro do impl.

Coletar um iterador sem fim. Fibonacci::new().collect::<Vec<_>>() (sem take) compila sem problemas, mas nunca termina de um jeito útil: ele roda até os números estourarem, ou para sempre se o seu next nunca retornar None. O compilador não consegue pegar esse erro. Quando um iterador puder ser infinito, sempre acrescente take, take_while ou find antes de consumi-lo.

Resumo

• Implemente Iterator com type Item e fn next(&mut self) -> Option<Self::Item>. Retorne None quando terminar.
• Assim que o next existe, você ganha map, filter, take, sum, zip e dezenas de outros de graça.
• Iteradores são preguiçosos: nada acontece até que um laço for, collect, sum etc. os consuma, e os itens passam um de cada vez.
• Implemente IntoIterator para &MeuTipo, &mut MeuTipo e MeuTipo para aceitar laços for que pegam emprestado, pegam emprestado de forma mutável ou consomem.
• DoubleEndedIterator libera o .rev(); ExactSizeIterator libera o .len().
• Para iteradores rápidos de uso único, use std::iter::from_fn ou std::iter::successors.

Teste o que aprendeu

Teste o que aprendeu

1. O que o next deve retornar quando o iterador não tem mais itens?

0 Um Vec vazio None Ele deve dar panic

2. Depois de implementar só o next, dá para chamar .map() e .sum() no seu iterador?

Sim, eles são métodos padrão construídos em cima do next Não, você precisa implementar cada um Só se você também implementar IntoIterator

3. No exemplo de avaliação preguiçosa, quando o next() é chamado pela primeira vez?

Quando o .map() é escrito Quando o .take(3) é escrito Quando o laço for começa a consumir a cadeia

4. Qual impl faz for song in &playlist funcionar?

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

5. De qual trait você precisa para que o .rev() funcione no seu iterador?

ExactSizeIterator Clone IntoIterator DoubleEndedIterator

Pontuação: 0 / 5

Para saber mais

• Processing a Series of Items with Iterators — The Rust Book (em inglês): como Iterator e next funcionam, e por que os iteradores são preguiçosos.
• Module std::iter (em inglês): o guia oficial sobre iteradores, incluindo uma seção sobre como implementar os seus e sobre IntoIterator.
• The Iterator trait — std docs (em inglês): todos os adaptadores que você ganha de graça depois de escrever o next.
• Iterators — Rust by Example (em inglês): um iterador de Fibonacci curto que você pode rodar e modificar.
• std::iter::successors (em inglês): a documentação para criar um iterador a partir de um valor inicial e de uma regra de “próximo”.