Associated types vs type parameter conflict


#1

I’m trying to write a FromIterator impl for a generic struct and I struggle to get it working.

This is what I have so far:

pub struct Collect<R, I: Iterator<Item=R>> {
    iter: I,
    cur: Option<R>,
}

impl<R, I: Iterator<Item=R>> FromIterator<R> for Collect<R, I>  {
    fn from_iter<II: IntoIterator<Item=R>>(iter: II) -> Self {
        let iter = iter.into_iter();
        Collect { iter: iter, cur: iter.next() }
    }
}

The compiler error is:

 expected `Collect<R, I>`,
    found `Collect<R, <II as std::iter::IntoIterator>::IntoIter>`
(expected type parameter,
    found associated type) [E0308]

I see why it doesn’t work, the IntoIterator trait wants to define the concrete Iterator type, but I need to know that type already for the concrete Collect type.

Unfortunately the following is also not compiling:

impl<R, I: IntoIterator<Item=R>> FromIterator<R> for Collect<R, I::IntoIter>  {
    fn from_iter(iter: I) -> Self {
        let iter = iter.into_iter();
        Collect { iter: iter, cur: iter.next() }
    }
}
src/iter.rs:82:9: 82:10 error: the type parameter `I` is not constrained by the impl trait, self type, or predicates [E0207]
src/iter.rs:82 impl<R, I: IntoIterator<Item=R>> FromIterator<R> for Collect<R, I::IntoIter>  {
                       ^

And if that error would go away, it would still complain about from_iter not taking a type parameter.

Is there any solution or workaround to this problem?


#2

What you intended to write was: “For any type R, I can take any type that can iterate over R and produce a Collect<R, that iterator>.”

What went wrong was the following:

  1. The trait FromIterator<R> means “For any type that can iterate over R, I can produce my type.”
  2. Collect<R, I> where I: Iterator<Item=R> means “For any type R, the Collect corresponding to R and any iterator over R.”

So what you ended up telling Rust was "For any type R, I can take any type that can iterate over R and produce the Collect corresponding to R and any iterator over R.

Notice that what you actually told Rust contains one more “any” than what you meant to write, which is basically what the message from the compiler says:

 expected `Collect<R, I>`,
    found `Collect<R, <II as std::iter::IntoIterator>::IntoIter>`
(expected type parameter,
    found associated type) [E0308]

It expected your implementation to be able to provide any iterator type I, but the only one it actually provides is the specific iterator type II::IntoIter.

EDIT: sorry I don’t have a solution


#3

Since FromIterator seems incompatible with what you are trying to express, how about something like the following?

impl<R, I: Iterator<Item=R>> Collect<R, I> {
    fn new<II: IntoIterator<Item=R>>(iter: II) -> Collect<R, II::IntoIter> {
        let mut iter = iter.into_iter();
        let cur = iter.next();
        Collect { iter: iter, cur: cur }
    }
}

This expresses the fact that you only know how to produce Collect<R, I> where I is the specific type II::IntoIter.


#4

As @dtolnay says, FromIterator has to work for any iterator type, that’s why it is a type param of the from_iter method. from_iter normally consumes the iterator, so that it doesn’t appear in the type for which FromIterator is implemented anymore.

Not knowing the way in which Collect is supposed to be used, I think the only way you ccan preserve the FromIterator impl is to use a boxed trait object iterator: http://is.gd/txCmPo


#5

Well technically, Collect can take any iterator type. But the problem is, that it requires a different concrete instantiation of Collect which seems to be fundamentally incompatible with how FromIterator is defined.

It will be a generalization of std::io::Chain, which is generic over the types of the inner readers, so I tried to do the same. But also being generic over the iterator type is probably unnecessary.

Using a trait object is exactly the workaround I was looking for. Thanks for the hint. It also feels cleaner like this. From a performance point of view, it’s probably not measurable, at least not for the common use case.

But I still wonder if there’s a way to write FromIterator differently, such that it would allow that kind of dependency…