Defining and implementing the Iterable trait with GATs (original) (raw)

Generic Associated Types Initiative

Defining and implementing the Iterable trait with GATs

Play with this example on the Rust playground.

To express traits like Iterable, we can make use generic associated types -- that is, associated types with generic parameters. Here is the complete Iterable trait:

#![allow(unused)]
fn main() {
trait Iterable {
    // Type of item yielded up; will be a reference into `Self`.
    type Item<'collection>
    where
        Self: 'collection;

    // Type of iterator we return. Will return `Self::Item` elements.
    type Iterator<'collection>: Iterator<Item = Self::Item<'collection>>
    where
        Self: 'collection;

    fn iter<'c>(&'c self) -> Self::Iterator<'c>;
    //           ^^                         ^^
    //
    // Returns a `Self::Iter` derived from `self`.
}
}

Let's walk through it piece by piece...

• We added a 'collection parameter to Item. This represents "the specific collection that the Item is borrowed from" (or, if you prefer, the lifetime for which that collection is borrowed).
• The same 'collection parameter is added to Iterator, indicating the collection that the iterator borrows its items from.
• In the iter method, the value of 'collection comes from self, indicating that iter returns an Iterator linked to self.
• Each associated type also has a where Self: 'collection bound. These bounds are required by the compiler -- if you don't add them, you will get a compilation error. As explained here, this is a compromise that is part of the GATs MVP to give us time to work out the best long-term solution.
  • The bound where Self: 'collection is called an outlives bound -- it indicates that the data in Self must outlive the 'collection lifetime

Implementing the trait

Let's write an implementation of this trait. We'll implement it for the Vec<T> type; a &Vec<T> can be coerced into a &[T] slice, so we can re-use the slice Iter that we defined before (the playground link includes an impl of Iterable for [T] as well, but we'll use Vec here because it's more convenient).

#![allow(unused)]
fn main() {
// from before
struct Iter<'c, T> {
    data: &'c [T],
}

impl<T> Iterable for Vec<T> {
    type Item<'c> = &'c T
    where
        T: 'c;
    
    type Iterator<'c> = Iter<'c, T>
    where
        T: 'c;

    fn iter<'c>(&'c self) -> Self::Iterator<'c> {
        Iter { data: self }
    }
}
}

Invoking it

Now that we have the Iterable trait, we can reference it in our "count twice" function.

#![allow(unused)]
fn main() {
fn count_twice<I: Iterable>(collection: &I) {
    let mut count = 0;
    for _ in collection.iter() {
        count += 1;
    }

    for elem in collection.iter() {
        process(elem, count);
    }
}
}

and we can invoke that by writing code like count_twice(&vec![1, 2, 3, 4, 5, 6]).

Play with the code from this section on the Rust playground.