Why does `rev().rev()` work but `rev().skip(1).rev()` does not?

user_474197 0
Viewed 405

As title, in Rust, .rev().rev() works, .rev().skip(1) works, but .rev().skip(1).rev() does not. The following is the demonstration:

// This compiles
fn main() {
    let s = "Hello!";
    println!("{}", &s.chars().rev().skip(1).collect::<String>());
}

// This compiles
fn main() {
    let s = "Hello!";
    println!("{}", &s.chars().rev().rev().collect::<String>());
}

// This *does not* compile
fn main() {
    let s = "Hello!";
    println!("{}", &s.chars().rev().skip(1).rev().collect::<String>());
}

The last one does not compile:

error[E0277]: the trait bound `Chars<'_>: ExactSizeIterator` is not satisfied
 --> src/main.rs:3:45
  |
3 |     println!("{}", &s.chars().rev().skip(1).rev().collect::<String>());
  |                                             ^^^ the trait `ExactSizeIterator` is not implemented for `Chars<'_>`
  |
  = note: required because of the requirements on the impl of `ExactSizeIterator` for `Rev<Chars<'_>>`
  = note: required because of the requirements on the impl of `DoubleEndedIterator` for `Skip<Rev<Chars<'_>>>`

error[E0599]: the method `collect` exists for struct `Rev<Skip<Rev<Chars<'_>>>>`, but its trait bounds were not satisfied
  --> src/main.rs:3:51
   |
3  |        println!("{}", &s.chars().rev().skip(1).rev().collect::<String>());
   |                                                      ^^^^^^^ method cannot be called on `Rev<Skip<Rev<Chars<'_>>>>` due to unsatisfied trait bounds
   |
   = note: the following trait bounds were not satisfied:
           `Skip<Rev<Chars<'_>>>: DoubleEndedIterator`
           which is required by `Rev<Skip<Rev<Chars<'_>>>>: Iterator`
           `Rev<Skip<Rev<Chars<'_>>>>: Iterator`
           which is required by `&mut Rev<Skip<Rev<Chars<'_>>>>: Iterator`

Playground

Could someone explain why this is the case?

rust
3 Answers

Calling .chars() returns an Iterator (Chars) which implements DoubleEndedIterator, which using .rev() requires.

fn rev(self) -> Rev<Self>
where
    Self: DoubleEndedIterator

Then calling .skip() produces a new Iterator (Skip), which only implements DoubleEndedIterator if the Iterator (in this case Chars) implements both DoubleEndedIterator and ExactSizeIterator.

impl<I> DoubleEndedIterator for Skip<I>
where
    I: DoubleEndedIterator + ExactSizeIterator

However, Chars does not implement ExactSizeIterator. So DoubleEndedIterator is not implemented for Skip. So now the requirement for calling .rev() is no longer uphold for the second call.

user_24708180

The rev method returns a structure called Rev<I> where I is whatever iterator you called it on.

For example, my_str.chars() gets you a Chars struct which is an iterator. Calling .rev() gets you Rev<Chars>.

.rev() requires that I be a DoubleEndedIterator (which makes sense, reversing is done by just iterating from the back to the front).

The skip method returns a structure called Skip<I> where similarly, I is whatever iterator you called it on.

This is callable on any iterator (which makes sense).

However, Skip<I> only implements DoubleEndedIterator if I implements DoubleEndedIterator and ExactSizeIterator.

That means, that we can only call .rev on a Skip<I> if I: DoubleEndedIterator + ExactSizeIterator.

One last piece before we look at what you've written: Chars implements DoubleEndedIterator but not ExactSizeIterator since characters are variable length when encoded in utf8.

Taking a look at this whole thing:

s
    .chars() // DoubleEndedIterator
    .rev()   // DoubleEndedIterator
    .skip()  // Doesn't implement DoubleEndedIterator because it doesn't implement ExactSizeIterator
    .rev()   // Err, we need DoubleEndedIterator here.
user_80505140

Two rev() is anyway a noop, Iterator are lazy so the second rev() cancel the first one unless the iterator is consumed between the two call.

To skip the last item of an iterator and then collect it in order, I will do:

use std::iter::{DoubleEndedIterator, FromIterator, Iterator};

fn collect_rev_nth_n_rev<I, C>(items: I, n: usize) -> C
where
    I: DoubleEndedIterator,
    C: FromIterator<<I as Iterator>::Item>,
{
    let mut iter = items.rev();
    iter.nth(n);
    iter.rev().collect()
}

fn main() {
    let result: String = collect_rev_nth_n_rev("Hello!".chars(), 0);
    assert_eq!("Hello", result);
}

nth() is often nicely optimized.

user_70761530
Related