glide
Capítulo 14 15 min de leitura

Iteradores

stdlib::iter fornece a trait Iterator, conecta o VecIter do Vector a ela e disponibiliza uma família de combinadores como funções livres que transformam, reduzem e constroem valores Vector<T>. Os transformadores são ansiosos (eager): cada um percorre a entrada uma vez e retorna um novo *Vector<U> completamente materializado, em vez de um adaptador lazy.

Importação

import stdlib::iter::*;

Visão geral da superfície pública

Tipo Item
trait Iterator (tipo associado Item, método next)
impl Iterator for VecIter<T>
transformadores iter_map, iter_filter, iter_take, iter_skip, iter_take_while, iter_skip_while
redutores iter_fold, iter_count, iter_any, iter_all, iter_find
redutores numéricos iter_sum_int, iter_max_int, iter_min_int
construtores iter_range, iter_range_step, iter_repeat

VecIter<T> em si é declarado nos builtins (builtins::vector) junto com Vector::iter; este módulo apenas acrescenta a impl de Iterator para ele.

A trait Iterator

pub trait Iterator {
    type Item;
    fn next(self: *Self) -> ?Self::Item;
}

Um tipo é um iterador se consegue entregar o next elemento embrulhado em uma opção — some(x) enquanto houver elementos, none() ao se esgotar. A trait possui um tipo associado, Item, que nomeia o tipo dos elementos.

O módulo fornece uma implementação, para VecIter<T> (o cursor retornado por Vector::iter):

impl<T> Iterator for VecIter<T> {
    type Item = T;
    fn next(self: *VecIter<T>) -> ?T {
        if self.idx >= self.vec.len { return none(); }
        let v: T = self.vec.data[self.idx];
        self.idx = self.idx + 1;
        return some(v);
    }
}

Como a impl vive neste módulo, importar stdlib::iter::* é o que torna v.iter() utilizável através de um bound de trait como fn f<I: Iterator>(it: *I).

VecIter<T>

pub struct VecIter<T> {
    vec: *Vector<T>,
    idx: i32,
}
Campo Tipo Significado
vec *Vector<T> vetor em empréstimo sendo percorrido
idx i32 próximo índice a ser entregue

Você obtém um *VecIter<T> de v.iter() e extrai elementos com .next() até que ele retorne none():

import stdlib::iter::*;

fn main() -> i32 {
    let v: *Vector<i32> = Vector::new();
    defer v.free();
    v.push_all!(10, 20, 30);

    let it: *VecIter<i32> = v.iter();
    while true {
        match it.next() {
            some(x) => println!(x),
            none()  => break,
        }
    }
    return 0;
}

Uma função genérica pode aceitar qualquer iterador via um bound de trait:

import stdlib::iter::*;

fn count_all<I: Iterator>(it: *I) -> i32 {
    let mut n: i32 = 0;
    while true {
        match it.next() {
            some(_) => { n = n + 1; },
            none()  => break,
        }
    }
    return n;
}

fn main() -> i32 {
    let v: *Vector<i32> = iter_range(1, 5);   // [1,2,3,4]
    defer v.free();
    println!(count_all(v.iter()));            // 4
    return 0;
}

Transformadores — retornam um novo *Vector<U>

Cada transformador aloca e retorna um vetor completamente novo que pertence ao chamador. Faça o binding do resultado com let v* = ... para liberação automática ao fim do escopo, ou com um let v: *Vector<T> = ... de ponteiro bruto quando pretender passá-lo a outro auxiliar (veja o callout de erro abaixo).

Função Assinatura Resultado
iter_map fn iter_map<T, U>(v: *Vector<T>, f: fn(T) -> U) -> *Vector<U> aplica f a cada elemento
iter_filter fn iter_filter<T>(v: *Vector<T>, p: fn(T) -> bool) -> *Vector<T> mantém elementos onde p é verdadeiro
iter_take fn iter_take<T>(v: *Vector<T>, n: i32) -> *Vector<T> primeiros n (limitado ao tamanho, n<0→vazio)
iter_skip fn iter_skip<T>(v: *Vector<T>, n: i32) -> *Vector<T> descarta os primeiros n (n<0 tratado como 0)
iter_take_while fn iter_take_while<T>(v: *Vector<T>, p: fn(T) -> bool) -> *Vector<T> prefixo até p retornar false pela primeira vez
iter_skip_while fn iter_skip_while<T>(v: *Vector<T>, p: fn(T) -> bool) -> *Vector<T> sufixo a partir do primeiro elemento em que p é false

iter_map, iter_filter

import stdlib::iter::*;

fn double(x: i32) -> i32 { return x * 2; }
fn keep_pos(x: i32) -> bool { return x > 0; }

fn main() -> i32 {
    let v: *Vector<i32> = iter_range(0 - 3, 5);     // [-3,-2,-1,0,1,2,3,4]
    let m: *Vector<i32> = iter_map(v, double);
    let f: *Vector<i32> = iter_filter(m, keep_pos); // [2,4,6,8]
    let total: i32 = iter_sum_int(f);               // 20
    println!(total);
    return 0;
}

iter_map pode mudar o tipo do elemento (T → U); iter_filter sempre o preserva. Nenhum dos dois muta a entrada — o vetor de origem fica intacto.

iter_take, iter_skip, iter_take_while, iter_skip_while

import stdlib::iter::*;

fn lt3(x: i32) -> bool { return x < 3; }

fn main() -> i32 {
    let v: *Vector<i32> = iter_range(0, 6);   // [0,1,2,3,4,5]
    let a* = iter_take(v, 3);                 // [0,1,2]
    let b* = iter_skip(v, 2);                 // [2,3,4,5]
    let c* = iter_take_while(v, lt3);         // [0,1,2]
    let d* = iter_skip_while(v, lt3);         // [3,4,5]
    println!(a.len(), b.len(), c.len(), d.len());
    return 0;
}

take_while para no primeiro elemento que falha p; skip_while descarta o prefixo de elementos onde p é verdadeiro e mantém tudo a partir do primeiro elemento onde p é falso (incluindo elementos posteriores que porventura satisfaçam p).

Comportamento nos limites

Chamada Entrada [0,1,2,3] Resultado
iter_take(v, 99) n maior que o tamanho limitado → [0,1,2,3]
iter_take(v, 0 - 5) n negativo []
iter_skip(v, 0 - 5) n negativo tratado como 0 → [0,1,2,3]
iter_take_while(v, p) p falso para todos []
iter_skip_while(v, p) p verdadeiro para todos [] 
import stdlib::iter::*;

fn main() -> i32 {
    let v: *Vector<i32> = iter_range(0, 4);   // [0,1,2,3]
    let big* = iter_take(v, 99);              // [0,1,2,3]
    let neg* = iter_take(v, 0 - 5);           // []
    let sk*  = iter_skip(v, 0 - 5);           // [0,1,2,3]
    println!(big.len(), neg.len(), sk.len()); // 4 0 4
    v.free();
    return 0;
}

Encadeando transformadores

Os transformadores consomem um *Vector e retornam um novo, de modo que podem ser encadeados alimentando cada resultado no seguinte. Quando um resultado é consumido por outro auxiliar, faça o binding como um ponteiro bruto simples (let x: *Vector<i32> = ...) e libere cada intermediário você mesmo:

import stdlib::iter::*;

fn double(x: i32) -> i32 { return x * 2; }
fn is_even(x: i32) -> bool { return x % 2 == 0; }

fn main() -> i32 {
    let v: *Vector<i32> = iter_range(1, 7);            // [1,2,3,4,5,6]
    let evens: *Vector<i32> = iter_filter(v, is_even); // [2,4,6]
    let dbl: *Vector<i32> = iter_map(evens, double);   // [4,8,12]
    let total: i32 = iter_sum_int(dbl);                // 24
    println!(total);
    v.free();
    evens.free();
    dbl.free();
    return 0;
}

Redutores — retornam um valor

Os redutores leem o vetor e o colapsam em um único resultado. iter_find retorna uma opção; os demais retornam valores simples. Nenhum deles libera ou muta a entrada.

Função Assinatura Resultado
iter_fold fn iter_fold<T, U>(v: *Vector<T>, init: U, f: fn(U, T) -> U) -> U fold à esquerda; f(acc, item) → novo acc
iter_count fn iter_count<T>(v: *Vector<T>) -> i32 contagem de elementos (igual a v.len())
iter_any fn iter_any<T>(v: *Vector<T>, p: fn(T) -> bool) -> bool true se algum corresponder (curto-circuita)
iter_all fn iter_all<T>(v: *Vector<T>, p: fn(T) -> bool) -> bool true se todos corresponderem; vazio → true
iter_find fn iter_find<T>(v: *Vector<T>, p: fn(T) -> bool) -> ?T primeira correspondência como some(x), senão none() 
import stdlib::iter::*;

fn add(acc: i32, x: i32) -> i32 { return acc + x; }
fn is_even(x: i32) -> bool { return x % 2 == 0; }
fn is_neg(x: i32) -> bool { return x < 0; }
fn is_pos(x: i32) -> bool { return x > 0; }

fn main() -> i32 {
    let v: *Vector<i32> = iter_range(1, 5);   // [1,2,3,4]
    let sum: i32 = iter_fold(v, 0, add);      // 10
    let n: i32 = iter_count(v);               // 4
    let anyNeg: bool = iter_any(v, is_neg);   // false
    let allPos: bool = iter_all(v, is_pos);   // true
    println!(sum, n, anyNeg, allPos);

    match iter_find(v, is_even) {
        some(x) => println!(x),               // 2
        none()  => {},
    }
    return 0;
}

iter_fold — o redutor geral

fold é o redutor mais geral: o tipo do acumulador U é independente do tipo do elemento T, portanto pode construir um valor de qualquer forma. Aqui ele transforma um Vector<i32> em uma string separada por vírgulas:

import stdlib::iter::*;

fn join_csv(acc: string, x: i32) -> string {
    if acc.len() == 0 { return format!("{}", x); }
    return acc.concat(",").concat(format!("{}", x));
}

fn main() -> i32 {
    let v: *Vector<i32> = iter_range(1, 5);   // [1,2,3,4]
    defer v.free();
    let s: string = iter_fold(v, "", join_csv);
    println!(s);                              // 1,2,3,4
    return 0;
}

iter_any/iter_all fazem curto-circuito (param no primeiro acerto / primeira falha); iter_find retorna o primeiro elemento correspondente embrulhado em ?T. iter_fold sempre visita todos os elementos.

Redutores numéricos por tipo

Os genéricos de Glide não restringem primitivos a uma trait Ord/numérica, portanto somar e encontrar extremos são fornecidos como funções concretas de i32.

Função Assinatura Resultado
iter_sum_int fn iter_sum_int(v: *Vector<i32>) -> i32 soma dos elementos (0 para vazio)
iter_max_int fn iter_max_int(v: *Vector<i32>) -> ?i32 maior elemento, none() se vazio
iter_min_int fn iter_min_int(v: *Vector<i32>) -> ?i32 menor elemento, none() se vazio 
import stdlib::iter::*;

fn main() -> i32 {
    let v: *Vector<i32> = Vector::new();
    defer v.free();
    v.push_all!(3, 7, 2, 9, 4);

    match iter_max_int(v) {
        some(m) => println!("max", m),   // 9
        none()  => {},
    }
    match iter_min_int(v) {
        some(m) => println!("min", m),   // 2
        none()  => {},
    }
    println!("sum", iter_sum_int(v));    // 25
    return 0;
}

iter_max_int / iter_min_int retornam ?i32 precisamente para que o caso de vetor vazio tenha uma resposta representável; desembrulhe com match, .has/.val ou ??.

Construtores

Função Assinatura Resultado
iter_range fn iter_range(start: i32, end: i32) -> *Vector<i32> [start, end); vazio se end <= start
iter_range_step fn iter_range_step(start: i32, end: i32, step: i32) -> *Vector<i32> start, start+step, … < end; vazio se step <= 0
iter_repeat fn iter_repeat<T>(value: T, n: i32) -> *Vector<T> n cópias de value; vazio se n <= 0 
import stdlib::iter::*;

fn main() -> i32 {
    let r* = iter_range(0, 5);            // [0,1,2,3,4]
    let s* = iter_range_step(0, 10, 2);   // [0,2,4,6,8]
    let z* = iter_repeat(0, 4);           // [0,0,0,0]
    let t* = iter_repeat("x", 3);         // ["x","x","x"]
    println!(r.len(), s.len(), z.len(), t.len());
    return 0;
}

iter_range é o construtor mais usado para gerar dados de teste e é a entrada canônica para os transformadores e redutores acima. iter_range_step é semi-aberto como iter_range e guarda contra passos não positivos (que de outra forma laçariam para sempre) retornando um vetor vazio.

Casos extremos dos construtores

import stdlib::iter::*;

fn main() -> i32 {
    let a* = iter_range_step(0, 10, 3);    // [0,3,6,9]
    let b* = iter_range_step(10, 0, 1);    // []   (end <= start)
    let c* = iter_range_step(0, 5, 0);     // []   (step <= 0)
    let d* = iter_range_step(0, 5, 0 - 2); // []   (step < 0)
    println!(a.len(), b.len(), c.len(), d.len());  // 4 0 0 0

    let r* = iter_repeat(7, 3);            // [7,7,7]
    let z* = iter_repeat(7, 0);            // []
    let n* = iter_repeat(7, 0 - 4);        // []   (n <= 0)
    println!(r.len(), z.len(), n.len());   // 3 0 0
    return 0;
}

Referência cruzada: formas de método

Todo transformador/redutor que recebe um único *Vector<T> como primeiro argumento possui um método equivalente em Vector<T> (definido em builtins::vector). A função livre e o método fazem a mesma coisa — escolha a que ficar mais legível.

Função livre Método de Vector Notas
iter_map(v, f) v.map(f) o tipo do elemento pode mudar
iter_filter(v, p) v.filter(p)
iter_take(v, n) v.take(n)
iter_skip(v, n) v.skip(n)
iter_take_while(v, p) v.take_while(p)
iter_skip_while(v, p) v.skip_while(p)
iter_fold(v, init, f) v.fold(init, f)
iter_count(v) v.len() iter_count é apenas v.len()
iter_any(v, p) v.any(p)
iter_all(v, p) v.all(p)
iter_find(v, p) v.find(p) retorna ?T
iter_sum_int(v) v.sum() forma de método em Vector<i32>/Vector<f64>
iter_max_int(v) v.max() ?T
iter_min_int(v) v.min() ?T

iter_range/iter_range_step/iter_repeat não têm forma de método — são construtores, não operações sobre um vetor existente.

import stdlib::iter::*;

fn double(x: i32) -> i32 { return x * 2; }
fn is_even(x: i32) -> bool { return x % 2 == 0; }
fn add(acc: i32, x: i32) -> i32 { return acc + x; }
fn is_pos(x: i32) -> bool { return x > 0; }
fn is_neg(x: i32) -> bool { return x < 0; }

fn main() -> i32 {
    let v: *Vector<i32> = Vector::new();
    defer v.free();
    v.push_all!(1, 2, 3, 4, 5);

    let m* = v.map(double);          // [2,4,6,8,10]
    let f* = v.filter(is_even);      // [2,4]
    let h* = v.take(3);              // [1,2,3]
    let t* = v.skip(2);              // [3,4,5]
    println!(m.len(), f.len(), h.len(), t.len());

    println!(v.fold(0, add));        // 15
    println!(v.any(is_neg));         // false
    println!(v.all(is_pos));         // true
    println!(v.sum());               // 15

    match v.max() {
        some(x) => println!("max", x),         // 5
        none()  => {},
    }
    match v.find(is_even) {
        some(x) => println!("first even", x),  // 2
        none()  => {},
    }
    return 0;
}

Recapitulando a posse

  • Transformadores e construtores alocam um novo *Vector de posse do chamador.

    • Faça o binding com let v* = ... para liberação automática ao fim do escopo, ou com um let v: *Vector<T> = ... bruto quando for passá-lo a outro auxiliar.

  • Redutores fazem empréstimo da entrada e não liberam nada; o vetor de entrada

    • permanece válido.

  • Vector::new() produz um *Vector bruto; combine-o com defer v.free() (e

    • use push_all!, que funciona sobre vetores brutos) quando o gerenciar manualmente.

  • v.iter() aloca um *VecIter que faz empréstimo de v; mantenha v vivo

    • durante a iteração e não o redimensione no meio do percurso.