arrays - patron - recorrer lista de objetos java

Usar iteradores genéricos en lugar de tipos de listas específicos

Question

Soy muy nuevo en Rust, proveniente de C # / Java / similar.

En C # tenemos IEnumerable<T> que se puede utilizar para iterar casi cualquier tipo de matriz o lista. C # también tiene una palabra clave de yield que puede usar para devolver una lista perezosa. Aquí hay un ejemplo ...

// Lazily returns the even numbers out of an enumerable
IEnumerable<int> Evens(IEnumerable<int> input)
{
    foreach (var x in input)
    {
        if (x % 2 == 0)
        {
            yield return x;
        }
    }
}

Este es un ejemplo tonto, por supuesto. Sé que podría hacer esto con la función de map de Rust, pero me gustaría saber cómo crear mis propios métodos que acepten y devuelvan iteradores genéricos.

Por lo que puedo deducir, Rust tiene iteradores genéricos que se pueden usar de manera similar, pero están por encima de mi comprensión. Veo Iter , IntoIterator , IntoIterator types, y probablemente más en la documentación, pero no hay una buena manera de entenderlos.

¿Alguien puede dar ejemplos claros de cómo crear algo como arriba? ¡Gracias!

PD El aspecto perezoso es opcional. Me preocupa más la abstracción de listas y tipos de matriz específicos.

Answer 1

Implemente el rasgo de Iterator para la estructura que debería servir como iterador. Solo necesitas implementar el next método. Los otros métodos tienen implementaciones predeterminadas.

No es posible crear un iterador que funcione con cualquier contenedor. La maquinaria del sistema tipo necesaria para esto aún no existe.

Answer 2

Aquí está la versión completa de Map , y aquí está la función que la construye.

Una implementación mínima sería algo así como

fn map<I, E, B, F>(i: I, f: F) -> Map<I, F> where
    F: FnMut(E) -> B,
    I: Iterator<Item=E>
{
    Map {iter: i, f: f}
}

pub struct Map<I, F> {
    iter: I,
    f: F,
}

impl<B, I: Iterator, F> Iterator for Map<I, F> where F: FnMut(I::Item) -> B {
    type Item = B;

    fn next(&mut self) -> Option<B> {
        self.iter.next().map(|a| (self.f)(a))
    }
}

Enlace de Playpen. Tenga en cuenta que el map utilizado dentro del iterador es el método de la Option ; esto no se define recursivamente!

No es muy conveniente escribir, ¡pero vaya rápido!

Ahora, para escribir esto para un tipo "enumerable" arbitrario, uno cambiaría el map a

fn map<I, E, B, F>(i: I, f: F) -> Map<I::IntoIter, F> where
    F: FnMut(E) -> B,
    I: IntoIterator<Item=E>
{
    Map {iter: i.into_iter(), f: f}
}

IntoIterator es básicamente IEnumerable , solo que en lugar de GetEnumerator hay into_iter .

Answer 3

Primero, olvídate de IntoIterator y otros rasgos o tipos. El rasgo de iteración central en Rust es Iterator . Su definición recortada es la siguiente:

trait Iterator {
    type Item;  // type of elements returned by the iterator
    fn next(&mut self) -> Option<Self::Item>;
}

Como probablemente sepa, puede pensar en un iterador como cursor dentro de alguna estructura. next() método next() avanza este cursor hacia adelante, devolviendo un elemento al que apuntaba previamente. Naturalmente, si la colección está agotada, no hay nada que devolver, por lo que next() devuelve Option<Self::Item> , no solo Self::Item .

Iterator es un rasgo, por lo que puede implementarse por tipos específicos. Tenga en cuenta que el propio Iterator no es un tipo apropiado que puede usar como un valor de retorno o un argumento de función; debe usar tipos concretos que implementen este rasgo.

La declaración anterior puede sonar demasiado restrictiva, ¿cómo usar tipos de iteradores arbitrarios? pero debido a los genéricos, esto no es así. Si desea que una función acepte iteradores arbitrarios, simplemente haga que sea genérica en el argumento correspondiente y agregue un Iterator vinculado al parámetro de tipo correspondiente:

fn iterate_bytes<I>(iter: I) where I: Iterator<Item=u8> { ... }

Volver iteradores de funciones puede ser difícil, pero ver a continuación.

Por ejemplo, hay un método en &[T] , llamado iter() , que devuelve un iterador que produce referencias en el sector. Este iterador es una instancia de esta estructura. Puede ver en esa página cómo se implementa Iter para Iter :

impl<''a, T> Iterator for Iter<''a, T> {
    type Item = &''a T;
    fn next(&mut self) -> Option<&''a T> { ... }
    ...
}

Esta estructura contiene una referencia al sector original y algún estado de iteración dentro de él. Su método next() actualiza este estado y devuelve el siguiente valor, si hay alguno.

Cualquier valor cuyo tipo implemente Iterator se puede utilizar en un bucle for ( for bucle, de hecho, funciona con IntoIterator , pero ver a continuación):

let s: &[u8] = b"hello";
for b in s.iter() {
    println!("{}", b);   // prints numerical value of each byte
}

Ahora, el rasgo de Iterator es en realidad más complejo que el anterior. También define una gran cantidad de métodos de transformación que consumen el iterador al que son llamados y devuelve un nuevo iterador que de alguna manera transforma o filtra los valores del iterador original. Por ejemplo, el método enumerate() devuelve un iterador que arroja valores del iterador original junto con el número posicional del elemento:

let s: &[u8] = b"hello";
for (i, b) in s.iter().enumerate() {
    println!("{} at {}", b, i);   // prints "x at 0", "y at 1", etc.
}

enumerate() se define así:

trait Iterator {
    type Item;
    ...
    fn enumerate(self) -> Enumerate<Self> {
        Enumerate {
            iter: self,
            count: 0
        }
    }
    ...
}

Enumerate es solo una estructura que contiene un iterador y un contador dentro de ella y que implementa Iterator<Item=(usize, I::Item)> :

struct Enumerate<I> {
    iter: I,
    count: usize
}

impl<I> Iterator for Enumerate<I> where I: Iterator {
    type Item = (usize, I::Item);

    #[inline]
    fn next(&mut self) -> Option<(usize, I::Item)> {
        self.iter.next().map(|a| {
            let ret = (self.count, a);
            self.count += 1;
            ret
        })
    }
}

Y así es como se implementan la mayoría de las transformaciones de iterador: cada transformación es una estructura de envoltura que envuelve el iterador original e implementa el rasgo de Iterator delegando en el iterador original y transformando el valor resultante de alguna manera. Por ejemplo, s.iter().enumerate() del ejemplo anterior devuelve un valor de tipo Enumerate<Iter<''static, u8>> .

Tenga en cuenta que mientras enumerate() se define directamente en el rasgo de Iterator , también puede ser una función independiente:

fn enumerate<I>(iter: I) -> Enumerate<I> where I: Iterator {
    Enumerate {
        iter: iter,
        count: 0
    }
}

El método funciona de manera muy similar: solo usa un parámetro de tipo de Self implícito en lugar de uno explícitamente nombrado.

Puede preguntarse qué es el rasgo de IntoIterator . Bueno, es solo un rasgo de conversión de conveniencia que puede implementarse por cualquier tipo que se pueda convertir a un iterador:

pub trait IntoIterator where Self::IntoIter::Item == Self::Item {
    type Item;
    type IntoIter: Iterator;

    fn into_iter(self) -> Self::IntoIter;
}

Por ejemplo, &''a [T] se puede convertir a Iter<''a, T> , por lo que tiene la siguiente implementación:

impl<''a, T> IntoIterator for &''a [T] {
    type Item = &''a T;
    type IntoIter = Iter<''a, T>;

    fn into_iter(self) -> Iter<''a, T> {
        self.iter()  // just delegate to the existing method
    }
}

Este rasgo se implementa para la mayoría de los tipos de contenedores y referencias a estos tipos. De hecho, es utilizado por for bucles - un valor de cualquier tipo que implementa IntoIterator se puede utilizar in cláusula in :

let s: &[u8] = b"hello";
for b in s { ... }

Esto es muy agradable desde el punto de vista del aprendizaje y la lectura porque tiene menos ruido (en forma de métodos tipo iter() ). Incluso permite cosas como estas:

let v: Vec<u8> = ...;

for i in &v { /* i is &u8 here, v is borrowed immutably */ }
for i in &mut v { /* i is &mut u8 here, v is borrowed mutably */ }
for i in v { /* i is just u8 here, v is consumed */ }

Esto es posible porque IntoIterator se implementa de forma diferente para &Vec<T> , &mut Vec<T> y solo Vec<T> .

Cada Iterator implementa IntoIterator que realiza una conversión de identidad ( into_iter() simplemente devuelve el iterador al que se llama), por lo que también puede usar las instancias de Iterator for bucles.

En consecuencia, tiene sentido usar IntoIterator en funciones genéricas porque hará que la API sea más conveniente para el usuario. Por ejemplo, la función enumerate() desde arriba podría reescribirse como tal:

fn enumerate<I>(source: I) -> Enumerate<I::IntoIter> where I: IntoIter {
    Enumerate {
        iter: source.into_iter(),
        count: 0
    }
}

Ahora puede ver cómo se pueden usar genéricos para implementar transformaciones con tipado estático fácilmente. Rust no tiene nada que ver con el yield C # / Python (pero es una de las características más deseadas, ¡así que un día puede aparecer en el idioma!), Por lo tanto, debe envolver explícitamente los iteradores de origen. Por ejemplo, puede escribir algo análogo a la estructura Enumerate anterior que hace la tarea que desea.

Sin embargo, la forma más idiomática sería utilizar combinators existentes para hacer el trabajo por usted. Por ejemplo, su código puede escribirse de la siguiente manera:

let iter = ...;  // iter implements Iterator<Item=i32>
let r = iter.filter(|&x| x % 2 == 0);  // r implements Iterator<Item=i32>
for i in r {
    println!("{}", i);  // prints only even items from the iterator
}

Sin embargo, el uso de combinadores puede volverse feo cuando desee escribir funciones de combinador personalizadas porque muchas de las funciones combinatorias existentes aceptan cierres (por ejemplo, el filter() anterior), pero los cierres en Rust se implementan como valores de tipos anónimos, por lo que solo no hay forma de escribir la firma de la función que devuelve el iterador:

fn filter_even<I>(source: I) -> ??? where I: IntoIter<Item=i32> {
    source.into_iter().filter(|&x| x % 2 == 0)
}

Hay varias formas de evitar esto, una de ellas es el uso de objetos de rasgo :

fn filter_even<''a, I>(source: I) -> Box<Iterator<Item=i32>+''a>
    where I: IntoIterator<Item=i32>, I::IntoIter: ''a
{
    Box::new(source.into_iter().filter(|&x| x % 2 == 0))
}

Aquí ocultamos el tipo de iterador real devuelto por filter() detrás de un objeto de rasgo. Tenga en cuenta que para hacer que la función sea totalmente genérica tuve que agregar un parámetro de por vida y un límite correspondiente al objeto de I::IntoIter Box y al tipo asociado de I::IntoIter . Esto es necesario porque I::IntoIter puede contener vidas arbitrarias dentro de él (al igual que Iter<''a, T> tipo anterior), y tenemos que especificarlos en el tipo de objeto de rasgo (de lo contrario, la información de por vida se perdería).

Los objetos de rasgo creados a partir del rasgo de Iterator implementan Iterator ellos mismos, por lo que puede continuar utilizando estos iteradores como de costumbre:

let source = vec![1_i32, 2, 3, 4];
for i in filter_even(source) {
    println!("{}", i);  // prints 2 and 4
}