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.