Using generic iterators instead of specific list types

arrays, iterator, rust, vector

Solution

First, forget about `IntoIterator` and other traits or types. The core iteration trait in Rust is `Iterator`. Its trimmed down definition is as follows:

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

As you probably know, you can think of an iterator as a cursor inside of some structure. `next()` method advances this cursor forward, returning an element it pointed at previously. Naturally, if the collection is exhausted, there is nothing to return, and so `next()` returns `Option<Self::Item>`, not just `Self::Item`.

`Iterator` is a trait, and so it can be implemented by specific types. Note that `Iterator` itself is not a proper type which you can use as a return value or a function argument - you have to use concrete types which implement this trait.

The above statement may sound too restrictive - how to use arbitrary iterator types then? - but because of generics this is not so. If you want a function to accept arbitrary iterators, just make it generic in the corresponding argument, adding an `Iterator` bound over the corresponding type parameter:

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

Returning iterators from functions may be difficult, but see below.

For example, there is a method on `&[T]`, called `iter()`, which returns an iterator which yields references into the slice. This iterator is an instance of this structure. You can see on that page how `Iterator` is implemented for `Iter`:

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

This structure holds a reference to the original slice and some iteration state inside it. Its `next()` method updates this state and returns the next value, if there is any.

Any value whose type implements `Iterator` can be used in a `for` loop (`for` loop in fact works with `IntoIterator`, but see below):

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

Now, `Iterator` trait is actually more complex than the above one. It also defines a lot of transformation methods which consume the iterator they are called on and return a new iterator which somehow transforms or filters values from the original iterator. For example, `enumerate()` method returns an iterator which yields values from the original iterator together with the positional number of the element:

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()` is defined like this:

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

`Enumerate` is just a struct which contains an iterator and a counter inside it and which implements `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
        })
    }
}

And this is how most iterator transformations are implemented: each transformation is a wrapping struct which wraps the original iterator and implements `Iterator` trait by delegating to the original iterator and transforming the resulting value somehow. For example, `s.iter().enumerate()` from the example above returns a value of type `Enumerate<Iter<'static, u8>>`.

Note that while `enumerate()` is defined in `Iterator` trait directly, it can be a standalone function as well:

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

The method works very similarly - it just uses implicit `Self` type parameter instead of an explicitly named one.

You may wonder what `IntoIterator` trait is. Well, it is just a convenience conversion trait which can be implemented by any type which can be converted to an iterator:

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

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

For example, `&'a [T]` can be converted into `Iter<'a, T>`, and so it has the following implementation:

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

This trait is implemented for most container types and references to these types. It is in fact used by `for` loops - a value of any type which implements `IntoIterator` can be used in `in` clause:

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

This is very nice from learning and reading perspective because it has less noise (in form of `iter()`-like methods). It even allows things like these:

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 */ }

This is possible because `IntoIterator` is implemented differently for `&Vec<T>`, `&mut Vec<T>` and just `Vec<T>`.

Every `Iterator` implements `IntoIterator` which performs an identity conversion (`into_iter()` just returns the iterator it is called on), so you can use `Iterator` instances in `for` loops as well.

Consequently, it makes sense to use `IntoIterator` in generic functions because it will make the API more convenient for the user. For example, `enumerate()` function from above could be rewritten as such:

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

Now you can see how generics can be used to implement transformations with static typing easily. Rust does not have anything like C#/Python `yield` (but it is one of the most desired features, so one day it may appear in the language!), thus you need to wrap source iterators explicitly. For example, you can write something analogous to the above `Enumerate` structure which does the task you want.

However, the most idiomatic way would be to use existing combinators to do the work for you. For example, your code may be written as follows:

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
}

However, using combinators may turn ugly when you want to write custom combinator functions because a lot of existing combinator functions accept closures (e.g. the `filter()` one above), but closures in Rust are implemented as values of anonymous types, so there is just no way to write the signature of the function returning the iterator out:

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

There are several ways around this, one of them is using trait objects:

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

Here we hide the actual iterator type returned by `filter()` behind a trait object. Note that in order to make the function fully generic I had to add a lifetime parameter and a corresponding bound to `Box` trait object and `I::IntoIter` associated type. This is necessary because `I::IntoIter` may contain arbitrary lifetimes inside it (just like `Iter<'a, T>` type above), and we have to specify them in the trait object type (otherwise the lifetime information would be lost).

Trait objects created from `Iterator` trait implement `Iterator` themselves, so you can continue using these iterators as usual:

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

Problem

Original source