Last Updated:
Montanhas cobertas de neve
Montanhas cobertas de neve

Uma jornada rumo aos iterators

Ana Hoverbear
Ana Hoverbear gringo

Atenção: este texto foi traduzido, editado e adaptado por @nawarian. Você encontra o texto original, escrito em 2015 em inglês, no blog parceiro Hoverbear.org através deste link.

Uma das minhas funcionalidades favoritas em Rust são os iterators. Eles são uma forma rápida, segura e preguiçosa (lazy) de trabalhar com estruturas de dados, streams e outras aplicações mais criativas.

Você pode brincar com iterators utilizando o website http://play.rust-lang.org/ enquanto navega aqui. Este artigo não substitui a documentação oficial ou a experiência de executar os códigos por si.

Nosso primeiro iterator

Um é pouco, mas dois é bom. Vamos pegar uma lista de valores e dobrá-los!

fn main() {
    // Primeiro temos uma lista de valores
    let entrada = [1, 2, 3];
    // Crie um iterator sobre estes valores
    let iterator = input.iter();
    // Especifique o que fazer ao iterar
    let mapeado = iterator.map(|&x| x * 2);
    // Faça alguma coisa com a saída
    let saida = mapped.collect::<Vec<usize>>();
    println!("{:?}", saida);
}

Já neste exemplo simples, podemos observar algumas coisas interessantes:

  • .iter() pode ser usado com vários tipos diferentes.
  • Precisamos declarar um valor e só depois criar um iterator para ele. Do contrário o valor não vai viver o suficiente para ser iterado. (Iterators são preguiçosos (lazy) e nem sempre são donos de seus valores).
  • .collect::<Vec<usize>>() itera a lista completamente e guarda seus valores num tipo de coleção que especificarmos. (Se você quiser escrever a sua própria estrutura de dados, dá uma olhada aqui)
  • Um iterator pode ser utilizado e encadeado! Você não precisa necessariamente chamar .collect() depois de uma chamada ao .map().

n de cada vez

Você pode acessar o próximo elemento de um iterator com .next(). Se você quiser pegar somente uma porção, pode utilizar .take(n) para criar um novo iterator que percorre os próximos n elementos.

Quer jogar fora alguns dados? Use .skip(n) para pular n elementos.

fn main() {
    let valores = [ 1, 2, 3, 4, 5];
    let mut iter = valores.iter();
    println!("{:?}", iter.next());
    println!("{:?}", iter.skip(2).take(2)
        .collect::<Vec<_>>());
}
// Saída:
// Some(1)
// [4, 5]

Observando o comportamento preguiçoso (lazy)

Eu comentei que iterators são preguiçosos, mas o primeiro exemplo não demonstrou este comportamento. Vamos utilizar .inspect() para observar como Rust se comporta.

fn main() {
    let entrada = [1, 2, 3];
    let iterator = input.iter();
    let mapeado = iterator
        .inspect(|&x| println!("Antes do map:\t{}", x))
        .map(|&x| x * 10) // Isto vai ser entrada...
        .inspect(|&x| println!("Primeiro map:\t{}", x))
        .map(|x| x + 5)   // ... disto.
        .inspect(|&x| println!("Segundo map:\t{}", x));
    mapeado.collect::<Vec<usize>>();
}

A saída é:

Antes do map:    1
Primeiro map:  10
Segundo map: 15
Antes do map:    2
Primeiro map:  20
Segundo map: 25
Antes do map:    3
Primeiro map:  30
Segundo map: 35

Como você pôde perceber, as funções map apenas executam quando o iterator avança. (Do contrário nós veríamos 12310, ...)

Note como .inspect() passa para seu callback um &x em vez de &mut ou o valor em si. Isto evita mutações e assegura que sua inspeção não vai bagunçar a pipeline de dados.

Isto gera uns efeitos colaterais bem bacanas como, por exemplo, iterators infinitos ou cíclicos.

fn main() {
    let entrada = [1, 2, 3];
    // Diz ao iterator para realizar ciclos em si mesmo
    let ciclico = entrada.iter().cycle();
    let saida = ciclico.take(9)
        .collect::<Vec<&usize>>();
    println!("{:?}", saida);
}
// Saída [1, 2, 3, 1, 2, 3, 1, 2, 3]

Algo em comum

Não fique aí achando que [1, 2, 3] e outros slices são as únicas coisas das quais você pode criar iterators.

Muitas estruturas de dados dão implementam esta trait: podemos utilizar VectorsDecDeques! Vejamos algumas coisas que implementam .iter().

use std::collections::VecDeque;

fn main() {
    // Crie um Vector de valores
    let entrada = vec![1, 2, 3];
    let iterator = entrada.iter();
    let mapeado = iterator.map(|&x| {
            return x * 2;
        });
    // Coletar o resultado num RingBuf.
    let saida = mapeado.collect::<VecDeque<_>>();
    println!("{:?}", saida);
}
// Saída [2, 4, 6]

Viu como fizemos o collect num VecDeque? Isto só é possível porque ele implementa FromIterator.

Você deve estar pensando "Ah rá! Aposto que você não consegue usar um HashMap ou uma árvore ou coisa do tipo, Hoverbear!". Errado! É possível, sim!

use std::collections::HashMap;
fn main() {
    // Inicializar um map de entrada
    let mut entrada = HashMap::<u64, u64>::new();
    entrada.insert(1, 10);
    entrada.insert(2, 20);
    entrada.insert(3, 30);
    // Continue...
    let iterator = entrada.iter();
    let mapeado = iterator.map(|(&key, &value)| {
            return (key, value * 10);
        });
    let saida = mapeado.collect::<Vec<_>>();
    println!("{:?}", output);
}
// [(1, 100), (3, 300), (2, 200)]

Quando iteramos um HashMap a função .map() muda para aceitar uma tupla, e .collect() aceita tuplas. E é claro, você também pode fazer um collect de volta para um HashMap (ou qualquer outra coisa).

Você notou como a ordem mudou? Isto acontece porque HashMaps não são necessariamente ordenados. Lembre-se sempre disso!

Tente mudar o código para converter um Vec<(u64, u64)> num HashMap.

Escrevendo um iterator

Tá, nós conseguimos experimentar algumas das coisas que podem implementar iterators. Mas a gente também pode fazer um nosso! Que tal um iterator que conta alguma coisa infinitamente?

struct CountUp {
    current: usize,
}

impl Iterator for CountUp {
    type Item = usize;
    // A única fn que a gente precisa implementar num iterator básico
    fn next(&mut self) -> Option<usize> {
        self.current += 1;
        Some(self.current)
    }
}

fn main() {
    let iterator = CountUp { current: 0 };
    // Este é um iterator infinito, vamos pegar só alguns itens
    let saida = iterator.take(20).collect::<Vec<_>>();
    println!("{:?}", saida);
}
// Saída [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]

Nós não precisamos chamar .iter() aqui. Faz sentido, porque nós já estamos implementando um iterator e não transformando alguma coisa num iterator como fizemos antes.

Tente mudar os valores de current.take().

Viu como nós podemos usar .take() e outras funções sem ter de implementar cada uma separadamente para nosso novo iterator? Se você olhar a documentação do módulo iter, verá que há várias traits como Iterator ou RandomAccessIterator.

Intervalos com o operador Range

Através dos exemplos abaixo você verá o uso da sintaxe x..y, que cria um intervalo (range). Intervalos implementam Iterator então não é necessário chamar .iter() neles. Você também pode usar (0..100).step_by(2) se quiser realizar pular alguns elementos a cada iteração.

Note que intervalos são abertos, não inclusivos.

0..5 == [ 0, 1, 2, 3, 4, ]
2..6 == [ 2, 3, 4, 5, ]

Também é possível utilizar intervalos como índices de coleção:

fn main() {
    let intervalo = (0..10).collect::<Vec<usize>>();
    println!("{:?}", &intervalo[..5]);
    println!("{:?}", &intervalo[2..5]);
    println!("{:?}", &intervalo[7..]);
}
// Saída:
// [0, 1, 2, 3, 4]
// [2, 3, 4]
// [7, 8, 9]

Saquei: utilizar .step_by() não funciona desse jeito já que não implementa Idx, mas Range implementa.

Encadear e compactar iterators

Juntar iterators de formas diferentes nos permite escrever códigos muito expressivos.

fn main() {
    // Demonstrando encadeamento
    let primeiro = 0..5;
    let segundo = 5..10;
    let encadeado = primeiro.chain(segundo);
    println!("Encadeado: {:?}", encadeado.collect::<Vec<_>>());
    // Demonstrando compactação
    let primeiro = 0..5;
    let segundo = 5..10;
    let compactado = primeiro.zip(segundo);
    println!("Compactado: {:?}", compactado.collect::<Vec<_>>());
}
// Chained: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
// Zipped: [(0, 5), (1, 6), (2, 7), (3, 8), (4, 9)]

.zip() te permite juntar iterators. Já o .chain() cria um iterator "extendido".

Sim, também existe o .unzip().

Tente usar .zip() com dois slices do tipo usize e depois fazer um .collect() dessas tuplas para criar um HashMap.

Vamos dar poder à curiosidade

.count().max_by().min_by().all() e .any() são formas comuns de verificar o que há dentro de um iterator.

#![feature(core)] // Isto só funciona com rust nightly no momento em que o artigo foi escrito
#[derive(Eq, PartialEq, Debug)]
enum EspecieDeUrso { Marrom, Preto, Polar, Pardo }

#[derive(Debug)]
struct Urso {
    especie: EspecieDeUrso,
    idade: usize
}

fn main() {
    let ursos = [
        Urso { especie: EspecieDeUrso::Marrom, idade: 5 },
        Urso { especie: EspecieDeUrso::Preto, idade: 12 },
        Urso { especie: EspecieDeUrso::Polar, idade: 15 },
        Urso { especie: EspecieDeUrso::Pardo, idade: 16 },
    ];
    // Max/Min de uma lista.
    let mais_velho = ursos.iter().max_by(|x| x.idade);
    let mais_novo = ursos.iter().min_by(|x| x.idade);
    println!("Mais velho: {:?}\nMais novo: {:?}", mais_velho, mais_novo);

// Algum / Todos let tem_urso_polar = ursos.iter().any(|x| { x.especie == EspecieDeUrso::Polar }); let todos_menores_de_idade = ursos.iter().all(|x| { x.idade <= 18 }); println!("Pelo menos um urso polar?: {:?}", tem_urso_polar); println!("Todos são menores de idade? (<18): {:?}", todos_menores_de_idade);
}
// Saída: // Mais velho: Some(Urso { especie: Pardo, idade: 16 }) // Mais novo: Some(Urso { especie: Marrom, idade: 5 }) // Pelo menos um urso polar?: true // Todos são menores de idade? (<18): true

Tente utilizar o mesmo iterator em todas as chamadas no exemplo acima. .any() (algum) é o único que empresta (borrow) de forma mutável e não funciona igual aos outros. Isto porque esta função talvez não consuma o iterator por completo.

Filter, Map, Redu... não... Fold!

Se você, assim como eu, tem costume de programar em Javascript você provavelmente conhece a sagrada trindade .filter(), .map() e .reduce(). Estas funções também estão disponíveis em Rust, mas .reduce() é chamado de .fold() (e eu meio que prefiro esse nome).

Um exemplo:

fn main() {
    let entrada = 1..10;
    let saida = entrada
        .filter(|&item| item % 2 == 0) // Apenas pares
        .map(|item| item * 2) // Multiplicar por dois.
        .fold(0, |acumulador, item| acumulador + item);
    println!("{}", saida);
}

O snippet acima poderia ser simplificado para:

fn main() {
    let entrada = 1..10;
    let saida = entrada
        .fold(0, |acc, item| {
            if b % 2 == 0 {
                acc + (item*2)
            } else {
                acc
            }
        });
    println!("{}", saida);
}

Estas três funções tornam Rust um tanto flexível quanto expressivo.

Split & Scan

Também tem o scan caso você precise de uma variação de fold que faz um yield do resultado a cada iteração. Isto é bem útil se você precisa de um certo valor acumulado e quiser verificar este valor a cada iteração.

Dividir um iterator em duas partes também é possível. Você pode usar uma função de agrupamento que retorna um boolean com partition.

Vamos usar esses dois conceitos para:

  • dividir um slice grandão;
  • agrupá-lo entre pares e ímpares;
  • somar os grupos progressivamente; e
  • verificar que o pares são sempre menores que a soma dos ímpares, já que pares começam com 0.
fn main() {
    let lista = 0..1000;
    let (par, impar): (Vec<_>, Vec<_>) = lista.partition(|&n| n % 2 == 0);
    let par_scanner = par.iter().scan(0, |acc, &x| { *acc += x; Some(*acc) });
    let impar_scanner  = impar.iter().scan(0, |acc, &x| { *acc += x; Some(*acc) });
    let par_sempre_menor = par_scanner.zip(impar_scanner)
        .all(|(e, o)| e <= o);
    println!("Par sempre menor: {}", par_sempre_menor);
}
// Saída:
// Par sempre menor: true

Scan pode ser utilizado para gerar dados como médias móveis. Isto é útil quando se lê arquivos, dados e sensores. Particionar dados é uma tarefa comum quando se estiver organizando dados.

Outra operação comum é agrupar elementos com base num valor específico. Se você estiver buscando algo como o _.groupBy() do Lodash, calma lá. Considerando que Rust possui BTreeMap, HashMap, VecMap e outros tipos de dados, o nosso método de agrupamento precisa ser genérico.

Vamos ver um exemplo simples. Vamos escrever um iterator infinito que repete o intervalo de 0 a 5. No seu código esse iterator poderia utilizar structs ou tuplas, mas por agora, vamos utilizar somente inteiros.

Vamos agrupá-los em três categorias: zeros, cincos e todo o resto.

use std::collections::HashMap;

#[derive(Debug, PartialEq, Eq, Hash)]
enum Tipo { Zero, Cinco, Outro }

fn main() {
    let valores = 0..6; // [0, 1, 2, 4, 5]
    let ciclico = values.cycle();
    // Agrupar em um HashMap
    let agrupado = ciclico.take(20).map(|x| {
// Retorna uma tupla
match x { x if x == 5 => (Tipo::Cinco, 5), x if x == 0 => (Tipo::Zero, 0), x => (Tipo::Outro, x), } // Acumule os valores }
).fold(HashMap::<Tipo, Vec<_>>::new(), |mut acc, (k, x)| { acc.entry(k).or_insert(vec![]).push(x); acc }); println!("{:?}", agrupado);
}
// Saída: {Zero: [0, 0, 0, 0], Cinco: [5, 5, 5], Outro: [1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, 1]}

É meio que inútil guardar todos os valores replicados. Tente mudar o exemplo acima para retornar o número de ocorrências em vez de valores. Se quiser ir ainda mais longe, tente utilizar este método num valor mais complexo como uma struct, você também pode mudar quais chaves são utilizadas.

Flanqueado

A trait DoubleEndedIterator é útil em alguns casos. Por exemplo, quando você precisa dos comportamentos de uma fila e pilha ao mesmo tempo.

fn main() {
    let mut valores = 0..10;
    println!("{:?}", valores.next());
    println!("{:?}", valores.next_back());
    println!("{:?}", valores.next());
    println!("{:?}", valores.next_back());
}
// Some(0)
// Some(9)
// Some(1)
// Some(8)

Agora vai brincar!

Agora tá na hora de você fazer uma pausa, preparar um cházinho e abrir o Playground. Tente mudar um dos exemplos acima, brinque com algumas outras coisas dos links de documentação abaixo e, no mais, divirta-se.

Se você travar, não se preocupe! Procure na internet se o erro não fizer sentido nenhum pra ti. Rust também tem uma comunidade muito ativa nos domínios *.rust-lang.org assim como no GitHub e no Stack Exchange. Sinta-se [email protected] a me enviar um email ou dar um alô no IRC também.

O que a gente viu é só a superfície... um mundo imenso nos aguarda.

Comments