Why do I need `where <I as IntoIterator>::IntoIter: Clone` when using `.cycle` on a generic iterator argument?

#1

Apologies for the long title…

I am working through Advent of Code in Rust and, as an exercise, decided to try to make my solution to day 1 as generic as possible. To me, this meant 2 things:

  1. Operate over any valid numeric type (instead of just i32)
  2. Accept, as an argument, an iterator over this general numeric type

Using compiler error messages, I was able to cobble together the following (working) code:

fn solve_first<N: Add<Output = N> + Default + Hash + Eq + Copy, I: IntoIterator<Item = N>>(inp: I) -> N where
    <I as IntoIterator>::IntoIter: Clone {
    inp.into_iter().fold(N::default(), |acc, x| acc + x)
}

fn solve_second<N: Add<Output = N> + Default + Hash + Eq + Copy, I: IntoIterator<Item = N>>(inp: I) -> N where
    <I as IntoIterator>::IntoIter: Clone {
    let mut inp = inp.into_iter().cycle();
    let mut seen_vals = HashSet::new();
    let mut sum = N::default();
    while !seen_vals.contains(&sum) {
        seen_vals.insert(sum);
        sum = sum + inp.next().unwrap();
    }
    sum
}

For the most part this makes sense to me, except for the where <I as IntoIterator>::IntoIter: Clone part. Without it, I get the following error message:

error[E0277]: the trait bound `<I as std::iter::IntoIterator>::IntoIter: std::clone::Clone` is not satisfied
  --> src/main.rs:<snip>
   |
20 |     let mut inp = inp.into_iter().cycle();
   |                                   ^^^^^ the trait `std::clone::Clone` is not implemented for `<I as std::iter::IntoIterator>::IntoIter`
   |
   = help: consider adding a `where <I as std::iter::IntoIterator>::IntoIter: std::clone::Clone` bound

I don’t really understand what this bound is specifying. I suspect this may be due to my lack of a fundamental understanding between Iterator and IntoIterator.

Any help would be appreciated!

(Also, is there a way to reduce the amount of duplication in the trait bounds for N in the above? Something akin to type aliasing?)

#2

The Clone requirement comes from Iterator::cycle().

Your bound is saying you take a generic type I, which impls IntoIterator - this means that type can produce some other type that implements Iterator; that other type is <I as IntoIterator>::IntoIter associated type. Since that’ll be the Iterator impl you call cycle on, you need to add the Clone bound to it.

#3

Ah okay that makes sense. I think the most confusing part for me was <I as IntoIterator>, but it turns out just having where I::IntoIter: Clone works too, which is much more straightforward syntax. Thanks!

#4

Yup, you don’t need projections when you’ve already indicated what I is and want to refer to its associated type. The error message just gives the “fully expanded” form, with the projection in there.

1 Like