How to write trait which returns an iterator

help
1

I am struggling a bit with generics, traits and return types.

Imagine a simple function like this. I can use impl here to define
the return type.

fn retn_vec_iter(v:&Vec<isize>) -> impl Iterator<Item=&isize>{
    v.iter()
}

Now imagine I want to define this as a trait.

trait Return {
    fn retn_vec_iter<'a, I>(v:&'a Vec<isize>) -> impl Iterator<Item=&'a isize>;
}

I am not allowed to do this unfortunately.

error[E0562]: `impl Trait` not allowed outside of function and inherent method return types
 --> src/main.rs:6:57
  |
6 |     fn retn_vec_iter<'a, I>(&self, v:&'a Vec<isize>) -> impl Iterator<Item=&'a isize>;
  |                                                         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

So, I have tried this instead.

trait Return {
    fn retn_vec_iter<'a, I>(&self, v:&'a Vec<isize>) -> I
        where I: Iterator<Item=&'a isize>;
}

This compiles but if I try to implement it, it fails:

fn retn_vec_iter(v:&Vec<isize>) -> impl Iterator<Item=&isize>{
    v.iter()
}

trait Return {
    fn retn_vec_iter<'a, I>(&self, v:&'a Vec<isize>) -> I
        where I: Iterator<Item=&'a isize>;
}

struct Empty;

impl Return for Empty {
    fn retn_vec_iter<'a, I>(&self, v:&'a Vec<isize>) -> I
        where I: Iterator<Item=&'a isize> {
        retn_vec_iter(v)
    }
}

as the generic version does not have the same return type as the bare
function retn_vec_iter

   |
1  | fn retn_vec_iter(v:&Vec<isize>) -> impl Iterator<Item=&isize>{
   |                                    -------------------------- the found opaque type
...
13 |     fn retn_vec_iter<'a, I>(&self, v:&'a Vec<isize>) -> I
   |                          - this type parameter          - expected `I` because of return type
14 |         where I: Iterator<Item=&'a isize> {
15 |         retn_vec_iter(v)
   |         ^^^^^^^^^^^^^^^^ expected type parameter `I`, found opaque type
   |
   = note: expected type parameter `I`
                 found opaque type `impl std::iter::Iterator`

I think I am doing something wrong here. How do I add a method to
trait that returns an iterator of some type?

2

When you write

trait Return {
    fn retn_vec_iter<'a, I>(&self, v:&'a Vec<isize>) -> I
        where I: Iterator<Item=&'a isize>;
}

You're saying “For whatever type I (that implements Iterator) the calling code chooses, retn_vec_iter will return a value of type I”

You probably can't write that function. The error message you're getting says “you promised to return a value of type I, chosen by the caller, but you're returning this fixed type instead”.

What you want to say (and what -> impl Iterator means) is “return_vec_iter returns some fixed type. I'm not telling you exactly what it is, but that type implements Iterator”.

You can't do exactly that in a trait, but you can do the next best thing, which is to have an associated type on the trait. That lets each implementation specify the particular concrete type that its implementation of retn_vec_iter returns.

The declaration of IntoIterator, which is similar to what you want to do, might help.

7 Likes
3

The other option would be to return a &dyn Iterator. This would be appropriate if there allowed of this iterator is not critical, and simplicity of coding is more important.

4

Okay, yes, that is good! So I can do this.

fn retn_vec_iter<'a>(v:&'a Vec<isize>) -> std::slice::Iter<'a, isize>{
    v.iter()
}

trait Return<'a> {
    type Iter: Iterator<Item=&'a isize>;
    fn retn_vec_iter(&self, v:&'a Vec<isize>) ->
        Self::Iter;
}

struct Empty;

impl<'a> Return<'a> for Empty {
    type Iter = std::slice::Iter<'a,isize>;
    fn retn_vec_iter(&self, v:&'a Vec<isize>) -> Self::Iter {
        retn_vec_iter(v)
    }
}

pub fn main() {

}

What if I want to add some implemented methods to the trait. Say I
extend it to:

fn retn_vec_even_iter(&self, v:&'a Vec<isize>) -> Self::Iter {
        self.retn_vec_iter(v).filter(|n| *n % 2 == 0)
}

trait Return<'a> {
    type Iter: Iterator<Item=&'a isize>;
    type EvenIter: Iterator<Item=&'a isize>;
    fn retn_vec_iter(&self, v:&'a Vec<isize>) ->
        Self::Iter;

    fn retn_vec_even_iter(&self, v:&'a Vec<isize>) -> Self::EvenIter {
        self.retn_vec_iter(v).filter(|n| *n % 2 == 0)
    }
}

which gives me:

  = note: consider constraining the associated type `<Self as Return<'a>>::EvenIter` to `std::iter::Filter<<Self as Return<'a>>::Iter, [closure@src/main.rs:13:38: 13:53]>` or calling a method that returns `<Self as Return<'a>>::EvenIter`

I cannot figure out the syntax this is suggesting? And do I need another associated type or can I reuse them (i.e. do I need EvenIter here)?

5

Here you are saying that the implementor of Return is allowed to pick any EvenIter that is an iterator and retn_vec_even_iter will return that specific type. Something like the following should work:

trait Return<'a> {
    type Iter: Iterator<Item=&'a isize>;
    type EvenIter: Iterator<Item=&'a isize>;
    fn retn_vec_iter(&self, v:&'a Vec<isize>) -> Self::Iter;

    fn retn_vec_even_iter(&self, v:&'a Vec<isize>) -> std::iter::Filter<Self::Iter, fn(&&isize) -> bool> {
        self.retn_vec_iter(v).filter(is_even)
    }
}

fn is_even(i: &&isize) -> bool {
    *i % 2 == 0
}
6

Don't understand that. EvenIter doesn't appear anywhere except in the type declaration.

7

EvenIter isn’t being used at all anymore and that line can be safely removed. The return type std::iter::Filter<Self::Iter, fn(&&isize) -> bool> is the full type returned by Iterator::filter()

8

Writing a definition which uses one associated type per function and has default function definitions would require default associated types to work well. Unfortunately, it's still unstable (and I don't think even implemented unstably?).

There's more details on that here, but the gist is that what you'd really want is a way to say "the default implementation of retn_vec_even_iter depends on a default type for type EvenIter. If you override one, you must override the other". The above feature would introduce a good way to do this, but right now there isn't any.

There are a few ways to work around this, but none are ideal.

@bjorn3's solution is to disregard trait implementors' ability to write better implementations. This is a reasonable tradeoff - it's what Iterator itself does, for instance. You can't implement Iterator and change Iterator::filter to return your own special better type - it always returns an std::iter::Filter.

Another option would be to remove the default implementation. You'd add more boilerplate, but implementors would get to implement it however they way.

The third would be to just return Box<dyn Iterator<Item=&'a isize>> from retn_vec_even_iter. It'd be replacing static dispatch with dynamic dispatch, so you get a slight performance hit, but you can make a default impl and implementors can also override it and supply their own type. If this code isn't a hot path, this is probably what I'd recommend going with.

1 Like
9

Indeed, the compromise of @bjorns3 solution is not good for me. In my real code (I have shown smaller exemplars because my own is too complex), I am hitting these problems because I am replacing what was a concretely implemented struct with a trait because the performance of the default implementation is catastrophically too slow. I would remove the boilerplate indeed, but my current struct has around 30 methods. So if I accept the limitation of a concrete type, there is not point to writing the trait in the first place.

I could remove the default, but I have about thirty of them, so it would be quite a bit hassle to re-implement them all. And, unfortunately, the code is hot path -- that's why I am rewriting it. I guess I could macro this out -- the default implementation is already macrod so that would not be a disaster.

1 Like
10

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.