Implementing a trait function that returns generic

Question

In the following code, the trait called LimitCollection has a function that returns a type that implements Iterator trait.

struct Limit {}

impl Limit {
    fn is_violated(&self) -> bool {
        todo!()
    }
}

trait LimitCollection {
    fn get_violated_limits<'a, I>(&'a self) -> I
    where
        I: Iterator<Item = &'a Limit>;
}

Now I'd like to make something that implements the trait but the compiler complains that there is mismatch between the type that I return and the generic return type: "expected type parameter I, found struct Filter"

struct ConcreteLimitCollection {
    limits: Vec<Limit>,
}

impl LimitCollection for ConcreteLimitCollection {
    fn get_violated_limits<'a, I>(&'a self) -> I
    where
        I: Iterator<Item = &'a Limit>,
    {
        self.limits.iter().filter(Limit::is_violated)
    }
}

Is there any way to make this construct work, preferably without resorting to dynamic allocation?

Netwave · Accepted Answer · 2022-05-17 14:43:47Z

4

Usually you would use an associated type , in this case we would have some lifetimes involved (we need a GAT, generic associated type). Sadly what it is needed is not stabilized yet:

#![feature(generic_associated_types)]

struct Limit {}

impl Limit {
    fn is_violated(&self) -> bool {
        todo!()
    }
}

trait LimitCollection {
    type Output<'a>: Iterator<Item = &'a Limit> where Self: 'a;
    fn get_violated_limits<'a>(&'a self) -> Self::Output<'a>;
}

struct ConcreteLimitCollection {
    limits: Vec<Limit>,
}

impl LimitCollection for ConcreteLimitCollection {
    type Output<'a> = Box<dyn Iterator<Item = &'a Limit> + 'a> where Self: 'a;
    
    fn get_violated_limits<'a>(&'a self) -> Self::Output<'a> {
        Box::new(self.limits.iter().filter(|l| l.is_violated()))
    }
}

Playground

Disclaimer, I used Box<dyn Iterator<Item = &'a Limit> + 'a> even if you did not wanted to use dinamic allocation, but in this case you would just have to fulfill the whole Filter<...> type. Just did used a Boxed iterator for the example simplicity.

@SvenMarnach fitted the types :

impl LimitCollection for ConcreteLimitCollection {
    type Output<'a> = std::iter::Filter<std::slice::Iter<'a, Limit>, fn(&&Limit) -> bool>;
    
    fn get_violated_limits<'a>(&'a self) -> Self::Output<'a> {
        self.limits.iter().filter(|l| l.is_violated())
    }
}

Playground

edited May 17, 2022 at 14:43

answered May 17, 2022 at 9:09

Netwave

43.1k6 gold badges69 silver badges110 bronze badges

Sign up to request clarification or add additional context in comments.

11 Comments

Sven Marnach Over a year ago

I don't think it's possible to fully specify the type in this case.

Netwave Over a year ago

@SvenMarnach, yeah, it would be complicated and convoluted saying the least.

Sven Marnach Over a year ago

It's not actually that complicated – I think the type could be described as Filter<slice::Iter<'a, Limit>, fn(&Limit) -> bool> – but I think you will hit some limit of the type system here.

Chayim Friedman Over a year ago

@SvenMarnach This is not a GAT problem, just that filter()'s callback takes &Self::Item and Self::Item is &Limit, so two references. The fully-specified type is for<'b> fn(&'b &'a Limit) -> bool. play.rust-lang.org/…. Of course, this uses a function pointer; the real type is a closure and needs TAIT.

Sven Marnach Over a year ago

@ChayimFriedman Indeed, this is just a double reference. The closure does not capture anything, so it coerces to a function pointer. Using fn(&&Limit) -> bool, this actully works just fine.

|

Masklinn · Accepted Answer · 2022-05-17 09:11:25Z

Is there any way to make this construct work, preferably without resorting to dynamic allocation?

A generic type means the caller decides what the type is, because I (the type) is an input parameter so the caller should be able to pass in whatever they want as long as it fulfills the constraints.

But that's not the case here, you give the caller no choice.

The way to give the caller no choice, but to give the trait implementer a choice is an associated type.

Sadly as Netwave notes, here this requires a generic associated type (as Iterator is generic over the 'a lifetime), and GATs are not stable.

Two ways around that are to parameterize the trait itself, and to implement the trait for a reference rather than the type. https://stackoverflow.com/a/33756123/8182118 has examples and discussions of the possibilities.

Collectives™ on Stack Overflow

Implementing a trait function that returns generic

2 Answers 2

11 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

11 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related