Lending iterator without GAT?

help
1

Hello. I need help understanding the purpose of GAT. The "lending iterator" use case comes up a lot on google searches. I am going through this official tutorial to help me understand it.

It proposes this hypothetical trait definition:

trait Iterable {
    // Type of item yielded up; will be a reference into `Self`.
    type Item;

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

    fn iter<'c>(&'c self) -> Self::Iter;
}

and it claims,

"The fact that the lifetime parameter 'c is declared on the method is not just a minor detail. It is exactly what allows something to be iterated many times"

It goes on to say that this trait could not be implemented as the associated types will not be able to declare the right lifetime, hence the need for GAT.

However, I seem to have written a working example, one that can be iterated multiple times, without GAT?

fn main() {
    let nums = vec![4, 5, 6];
    count_twice(&nums);
}

struct Iter<'c, T> {
    data: &'c [T],
}

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

    fn next(&mut self) -> Option<Self::Item> {
        if let Some((prefix_elem, suffix)) = self.data.split_first() {
            self.data = suffix;
            Some(prefix_elem)
        } else {
            None
        }
    }
}

trait Iterable<'c> {
    type Item;
    type Iter: Iterator<Item = Self::Item>;

    fn iter(&'c self) -> Self::Iter;
}

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

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

fn count_twice<'c, I: Iterable<'c, Item = &'c i32>>(iterable: &'c I) {
    let mut count = 0;
    for _ in iterable.iter() {
        count += 1;
    }

    for i in iterable.iter() {
        process(*i, count);
    }
}

fn process(i: i32, count: i32) {
    println!("{}", i / count);
}

I'm sure I'm misunderstanding. There must be some manner in which my example is worse than the GAT implementation from the official tutorial, but I am unable to see it. Please help! :bowing_man:

2

FYI, this example doesn't feature the pattern usually denoted "lending iterator", it's a different use-case.

That being said, your workaround is totally fine for thus use case, and arguably the example they chose isn't the most convincing. Especially given how they've chosen to pass collection to count_twice by-reference - otherwise one may reasonably wonder how to name the lifetime for the local borrow in a trait bound. But even for that, higher ranked trait bounds are another solution. It's a well-known fact that HRTBs with a trait with normal associated type can effectively simulate GATs that are generic over lifetimes.

GATs generic over types is a different thing - those should have more clearly use cases that are hard to do in the same manner without them. I don't know a great actual concrete example off the top of my head.

3

In fact, some ways of "simulating" them are still a bit more powerful in some ways, compared to the the real GATs (as implemented today).

See also

which does also feature an actual LendingIterator interface, by the way.

1 Like
4

Here's an example from the blog posts introducing GATs (then called ATCs).

https://smallcultfollowing.com/babysteps//blog/2016/11/03/associated-type-constructors-part-2-family-traits/