Method not found in Trait impl that returns different kind of Iterator

[Genarito]

I am defining a Trait where different implementations for different Structs can return different types of Iterator.

For the Trait I'm using Associated Types:

// Some types for simplicity
pub type ConsData<T> = Box<dyn Iterator<Item = Tuple<T>>>;
pub type VecOfTuples<T> = Vec<Tuple<T>>;

// My Trait...
pub trait Operation<T> {
    type Iter: Iterator<Item = Tuple<T>> + ExactSizeIterator;

    fn count(&mut self) -> usize;
    fn eval(&mut self) -> Self::Iter;
    fn collect(&mut self) -> VecOfTuples<T> {
        self.eval().collect()
    }
    fn first(&mut self) -> VecOfTuples<T> {
        let mut result: VecOfTuples<T> = Vec::with_capacity(1);
        if let Some(tuple) = self.eval().next() {
            result.push(tuple);
        }
        result
    }
}

I've implemented the Trait succesfully for the type ConsData:

impl<T> Operation<T> for ConsData<T>
where
    Self: ExactSizeIterator<Item = Tuple<T>> + Copy,
{
    type Iter = Self;

    fn eval(&mut self) -> Self::Iter {
        *self
    }

    fn count(&mut self) -> usize {
        self.len()
    }
}

So I could do:

let vector: VecOfTuples<usize> = vec![Tuple::new(1), Tuple::new(2)];
let cons: ConsData<usize> = Box::new(vector.into_iter());
let a: VecOfTuples<usize> = cons.collect();
println!("{:?}", a); // Expected [Tuple(1), Tuple(2)]

But now, when I try to implement the same Trait for a struct called MapOperation which returns a Map Iterator It throws that method collect() is not implemented. Here's my impl for MapOperation:

pub struct MapOperation<O, U, T> {
    data: O,
    map_function: fn(Tuple<U>) -> Tuple<T>,
}

impl<O, T, U> Operation<T> for MapOperation<O, U, T>
where
    O: Operation<U>,
{
    type Iter = Map<<O>::Iter, fn(Tuple<U>) -> Tuple<T>>;

    fn eval(&mut self) -> Self::Iter {
        self.data.eval().map(self.map_function)
    }

    fn count(&mut self) -> usize {
        self.data.count()
    }
}

The definition compiles without errors. But then, when I try to run this:

Fails saying that my MapOperation does not implement the trait Operation.

let a_map_funcion: fn(Tuple<usize>) -> Tuple<(usize, usize, bool)> =
    |tuple| Tuple::new((tuple.0, 4, true));
let operation = MapOperation {
    data: cons,
    map_function: a_map_funcion,
};

let result: VecOfTuples<(usize, usize, bool)> = operation.collect();

Here there is a playground to try the code.

Why It's not working? As I see there is an explicit impl for the MapOperation struct, which contains a ConsData in the data field, which implements Operation too. I'd need a solution that works with any kind of Iterator, here is a constant Vec and Map, but It could be a Filter, FilterMap, etc.

Thanks in advance and sorry about my English

[jameseb7]

The variable operation is an instance of MapOperation, which only implements Operation when its first type parameter implements Operation. The first type parameter is the type of data, which in this case is ConsData. ConsData only implements Operation when it also implements ExactSizeIterator, but ConsData is just a boxed dyn Iterator, so it doesn't necessarily implement ExactSizeIterator. The implementation of Operation for ConsData thus never applies, so the implementation for MapOperation doesn't apply.

The simplest fix is probably to replace Iterator with ExactSizeIterator, and the remove the superfluous bound on the implementation of Operation for ConsData (I think ExactSizeIterator isn't necessarily implemented for a the trait object). This fixes your original problem, but there are then some borrow checker issues. In particular, let a: VecOfTuples<usize> = cons.collect(); is using the implementation of collect() from Iterator, not Operation, so it moves cons. That can be fixed by specifying the trait:

let a: VecOfTuples<usize> = Operation::<usize>::collect(&mut cons);

A more difficult problem to fix is that the eval method for ConsData is moving out of a borrow. That probably wants to output a borrow, but I don't think you can put lifetime parameters into associated types until GAT lands, so you may have to rethink your design.

[Genarito]

Hi @jameseb7! First of all thanks for your answer! Sorry for my lack of knowledge, I didn't realise that the collect and count method were called over the Iterator instead of my custom types. I renamed collect and count to get_collect and get_count respectively. When done, It threw all the erros you mentioned.

It's a shame these functions are not yet mature, I'm reading over Stack Overflow and here about this kind of problems and all I found are RFC without a concrete release date.

I'm trying to change my design to use Placeholders Types, but they are very limited. It would be extremely cool to have GADTs, Polymorfic Recursion and other tools from Functional Programming Paradigm in Rust.

Thank you again!

[jameseb7]

@Genarito

I'm trying to change my design to use Placeholders Types , but they are very limited. It would be extremely cool to have GADTs, Polymorfic Recursion and other tools from Functional Programming Paradigm in Rust.

While GADTs would be nice to have in Rust, I should probably clarify that I meant Generic Associated Types, which would allow for type and lifetime parameters on associated types. I believe you would need a lifetime parameter on the associated type if you want to output a borrow of the iterator in ConsData::eval(). Sorry for any confusion.

[Genarito]

Don't worry, no confusion at all! Thank you. Fortunately I was able to solve the problem with some workarounds. I'll submit a playground with the solution during the week

[Genarito]

Sorry, I was on holidays. Here is my code:

#[derive(Debug, Clone)]
pub struct Tuple<T: ?Sized>(pub T);

impl<T> Tuple<T> {
    pub fn new(x: T) -> Tuple<T> {
        Tuple(x)
    }
}
pub type VecOfTuples<T> = Vec<Tuple<T>>;

pub trait Operation<'a, T: 'a>
where
    T: Clone,
{
    type MyIter: Iterator<Item = Tuple<T>>;

    /// Return the count of elements
    fn get_count(&'a self) -> usize;

    /// Generates the final iterator with all the operations specified in the graph of execution
    fn eval(&'a self) -> Self::MyIter;

    /// Get all the resulting elements of the graph execution
    fn get_collect(&'a self) -> VecOfTuples<T> {
        self.eval().collect()
    }

    /// Returns only the first element
    fn first(&'a self) -> VecOfTuples<T> {
        self.top(1)
    }

    /// Returns N elements of the iterator
    fn top(&'a self, n: usize) -> VecOfTuples<T> {
        self.eval().take(n).collect()
    }
}

// Constant Data!
pub struct ConsData<T> {
    data: std::vec::IntoIter<Tuple<T>>,
}

// Operation implementation for ConsData
impl<'a, T: 'a> Operation<'a, T> for ConsData<T>
where
    T: Clone,
{
    type MyIter = std::vec::IntoIter<Tuple<T>>;

    fn eval(&'a self) -> Self::MyIter {
        self.data.clone()
    }

    fn get_count(&self) -> usize {
        self.data.len()
    }
}

// Implementation for Map
pub struct MapOperation<O, U, T> {
    data: O,
    map_function: fn(Tuple<U>) -> Tuple<T>,
}

impl<'a, O, T, U> Operation<'a, T> for MapOperation<O, U, T>
where
    O: Operation<'a, U>, // Mi parametro O va a devolver un iterador sobre un tipo U
    U: 'a + Clone,       // El tipo U que devuelve mi parametro O es clonable tambien
    T: 'a + Clone,       // Yo voy a devolver un iterador de tipo T que es clonable
{
    type MyIter = Map<<O as Operation<'a, U>>::MyIter, fn(Tuple<U>) -> Tuple<T>>;

    fn eval(&'a self) -> Self::MyIter {
        self.data.eval().map(self.map_function) /* .map(self.map_function) */
    }

    fn get_count(&'a self) -> usize {
        self.data.get_count()
    }
}

Hope It helps!