[beginner] using .rev() with a range

hello,

i’m having trouble getting the below code to typecheck. the problem seems to be that .rev() changes the type of an iterator. i’m curious about a few things: a) why is this the case that reversing an iterator changes the type? intuitionally, it doesn’t make sense to me. b) what/where should i be looking in the documentation to find a solution? opening the Rev page doesn’t seem to have any answers but i probably just don’t know how to read it: https://doc.rust-lang.org/std/iter/struct.Rev.html

thanks in advance!

fn gimme_range(x: bool) -> std::ops::Range<i8> {
    let a = 0..1;
    if x {
        a
    } else {
        a.rev() // <--- the .rev() call changes the type and fails to compile
    }
}

fn main() {
  println!("{:?}", gimme_range(true))
}

(Playground)

rev comes from the iterator trait, which needs to handle general iterators than just ranges. It makes a new type because internally it needs to swap implementations of Iterator::next, and the best way to do that is with a type.

2 Likes

Well the type of a is std::ops::Range<i8> as it seems you figured out yourself. The type of a.rev() is std::iter::Rev<std::ops::Range<i8>>. As you can see, these are not the same.

You might be used to Iterator<i8> being a type from other languages, but it doesn’t work the same way in rust. Iterator is a trait, which means it’s not what we call a “concrete type”. The Range and Rev types are both concrete. They are a struct or an enum, and the compiler knows their how many bytes they take up when it compiles. (Iterator<i8> is a type, but it is not what we call Sized.)

The reason you can’t return something like an Iterator is that the compiler must know its size to return it. One alternative is to return a Box<dyn Iterator<i8>>, which allocates memory on the heap and puts the iterator there, then returns a pointer to the heap. This way the compiler knows the size of the pointer, and it works. But this is less efficient than returning it directly, because you have to allocate it. Anyway, using a Box, you could write:

fn gimme_range(x: bool) -> Box<dyn Iterator<i8>> {
    let a = 0..1;
    if x {
        Box::new(a)
    } else {
        Box::new(a.rev())
    }
}

Note that with a Box, you allow all types of iterators to be returned. This can be handy in some cases, but we don’t actually need that. We know which two types we might return. Using an enum, you can hardcode the two types you’re interested in, and this way the compiler can look at the two possibilities and compute the size from them. Using an enum would look like this:

fn gimme_range(x: bool) -> Range {
    let a = 0..1;
    if x {
        Range::Forward(a)
    } else {
        Range::Backwards(a.rev())
    }
}

pub enum Range {
    Forward(std::ops::Range<i8>),
    Backwards(std::iter::Rev<std::ops::Range<i8>>),
}
impl Iterator for Range {
    type Item = i8;
    fn next(&mut self) -> Option<i8> {
        match self {
            Range::Forward(range) => range.next(),
            Range::Backwards(range) => range.next(),
        }
    }
}

This method is more efficient than the Box, because it doesn’t allocate memory.

Note that you can avoid all the work involved with writing the enum by using the itertools crate, which provides the Either type. Using this type it looks like this:

use itertools::Either;
use std::ops::Range;
use std::iter::Rev;

fn gimme_range(x: bool) -> Either<Range<i8>, Rev<Range<i8>>> {
    let a = 0..1;
    if x {
        Either::Left(a)
    } else {
        Either::Right(a.rev())
    }
}
8 Likes

Not OP but wanted to say thanks for a very thorough response :slight_smile:

alice, thanks very much for that answer, it is quite helpful!