Why is there no `Iterable` trait for container that have an `iter()` method

Many containers have an iter() method. I think that I read somewhere that GAT or something was required to correctly write an Iterable trait, but I don’t understand why. So I tried to implement it.

trait Iterable {
    type Iter: Iterator;
    fn iter(&self) -> Self::Iter;
}

fn debug_any_collection<'a, Collection>(collection: &'a Collection)
where
    &'a Collection: Iterable,
    <<&'a Collection as Iterable>::Iter as Iterator>::Item: std::fmt::Debug,
{
    for e in collection.iter() {
        eprintln!("{:?}", e); 
    }   
}

From this short experimentation, it seems that the main blocker is specialization. I’ve used type_alias_impl_trait, but that only for simplifying the implementation, I could have done without. Am I missing something? I guess that GAT aren’t needed unlike what I remembered?

IntoIterator is that trait, which is often implemented three ways:

  • C: IntoIterator for getting owned T items
  • for<'a> &'a C: IntoIterator to get shared &'a T items like iter() does
  • for<'a> &'a mut C: IntoIterator for &'a mut T items like iter_mut().
10 Likes

Effectively. I was sure that IntoIterator could only produce owned items (I even used it as a starting point for the code I wrote). I guess that types like Vec have an iter() method only because it’s much easier to write my_vec.iter() than (&my_vec).into_iter()?

You need GATs to implement something like IntoIterator on the collection type instead of its reference. The closest you can get otherwise has to return a boxed trait object:

trait RefIter: IntoIterator {
    fn iter(&'_ self)->Box<dyn Iterator<Item = &'_ Self::Item> + '_>;
}

impl<T,I> RefIter for T
where T:IntoIterator<Item=I>,
      for<'a> &'a T: IntoIterator<Item=&'a I>
{
    fn iter(&'_ self)->Box<dyn Iterator<Item = &'_ I> + '_> {
        Box::new(<&Self as IntoIterator>::into_iter(self))
    }
}

(Playground)

1 Like

I think the issue with GAT comes up if you want to write a trait for iterating by reference, implemented on the Collection itself rather than on &Collection (edit: as @2e71828 said). Then the type Iter and type Item don't have the named lifetime they need, but with GAT they could be type Iter<'a> = ...

Rayon has IntoParallelRefIterator<'data> which skirts the issue by forcing the lifetime into the trait, but that's annoyingly infectious. It's still implemented based on IntoParallelIterator for &C.

2 Likes

I realize that I tried to implement my Iterable trait both for &'a Vec<T> and &'a Vec<Box<T>> which requires specialization. How does the std library does it for IntoIterator?

Why would you need to treat Boxes differently than any other contained type?

1 Like

Mmmm. Indeed it works, but I have no idea why. I would have expected that Vec<Box<T>>::iter() would yield &Box<T> and not &T (hence the need for a specialization). I guess that there is an implicit deref somewhere that convert the &Box<T> into &T?

Moving ownership of what?...
Could be a value or a borrow... the latter creates some confusion when you are moving a borrow.

... especially when you can reuse the collection because moving a borrow creates a copy (I think... need to confirm).

1 Like

A Vec<Box<T>>::iter does yield &Box<T> as item type.

4 Likes

Because Vec doesn’t implement the method iter, Rust calls deref to see if it can find the method “there”... Also, the “subtyping” coercion “works”. I can do the same thing calling iter on mut Vec and &mut Vec to yield &T.

Check-out the left panel on slide 9 to see the all the ways you can generate &T... range of starting points -> single implementation of iter on &[T].

1 Like

Not, GAT is not required. Here's an example without GAT.

Yes, it is messy/ugly, but it doesn't use GAT. Yes, I still look forward to GAT to avoid this mess.

HRTBs have the additional limitation that T must be 'static: this fails because for<'a> T: 'a implies T: 'static. So even for lifetime-only genericity, GATs still provide more expressivity than HRTBs currently allow.

Reference: Solving the Generalized Streaming Iterator Problem without GATs

Ah, missed that, interesting. Thankfully my suggestion works for my cases.

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.