Range is odd when used with floating point types

[Veedrac]

For one,

fn main() {
    // The .take is needed to make this terminate
    let mut bad_range = range(0f32, 1e8).take(1000_000_000);

    let (min, max) = bad_range.size_hint();
    let max = max.unwrap();

    println!(
        "min: {:e} ≤ length: {:e} ≤ max: {:e}",
        min               .to_f64().unwrap(),
        bad_range.count() .to_f64().unwrap(),
        max               .to_f64().unwrap()
    );
}

outputs min: 1e8 ≤ length: 1e9 ≤ max: 1e8.

There's no real decision about what to do when rounding errors means r.next() == r.next(), such as with:

fn main() {
    let mut bad_range = range(1e8f32, 1e8+8.0);
    println!("{}", bad_range.next() == bad_range.next());
}

which currently results in an infinite iterator.

Personally I don't see a big problem with it, but unless floating ranges are banned it should at least avoid breaking size_hint.

Edit:

Further, rounding currently means that the size hints can be wrong. Both the upper bound:

fn main() {
    println!("{}", range(0f32, 1.5f32).count()); // 2
    println!("{}", range(0f32, 1.5f32).size_hint()); // (1, Some(1))
}

and the lower bound:

fn main() {
    println!("{}", range(4194303.8f32, 4194305f32).count()); // 1
    println!("{}", range(4194303.8f32, 4194305f32).size_hint()); // (2, Some(2))
}

[thestinger]

It should just be ported to used a trait with successor / predecessor instead of addition. This would also allow it to work with char despite it not being an arithmetic type. The only thing that would make sense with floats is going to the next possible value.

[vks]

The only thing that would make sense with floats is going to the next possible value.

I disagree. I think this is almost never what you want. Usually you want some finite step size.

Using multiplication instead of addition fixes the rounding errors.

[thestinger]

@vks: It doesn't matter if it's almost never what you want for floating point types, it's the sane definition of the basic generic range function. There's a range_step function if you want to specify a different step than simply the next value. It should work for all enumerated types, including ones that aren't numbers. It doesn't make sense to define it based on increments of the number one.

[Veedrac]

It's worth noting that there aren't any rounding error per se; multiplication would only help as long as you were using a datatype that could hold the required precision. Consider instead 1e300; no normal-sized integer will help you with that.

And then instead of multiplication you might as well just cast to the float.

[vks]

@thestinger That is not what range currently means. It is equivalent to range_step with step size 1. I think what you are proposing should be called differently, because it does not make sense for real numbers (you cannot iterate over them).

@Veedrac I'm not sure I understand. How is 1e300 related to 'normal-sized integers'? What do you mean by 'casting to the float'?

I still think multiplication would solve all the issues you mentioned, because it would yield exactly the expected number of elements (even if some are identical do to lacking precision).

[Veedrac]

@vks So you have X * 1.0f64, where X == 1e300. What's the type of X? If it's integer, it has either overflowed or is big and thus slow. It it's a floating point, how are you incrementing it?

[thestinger]

@vks: The only reason that range currently uses a step size of 1 is because a trait for successors / predecessors didn't exist when it was originally defined. It was always intended to be updated to use a trait like that. Anyway, the implementation of range has to be the same for all types because that's how Rust's generics work. What kind of trait do you propose using instead?

[vks]

@Veedrac I think I understand your point now. The problem seems to be the implementation of size_hint: if you remove it, the code works fine.

@thestinger

It was always intended to be updated to use a trait like that.

Really? That surprises me.

Anyway, the implementation of range has to be the same for all types because that's how Rust's generics work.

Currently it is only defined for types that implement Add, PartialOrd, Clone, One and ToPrimitive (the latter is only needed for size_hint). Why does it have to be implemented for all types?

I'm not convinced that it should be generalized to types that don't implement Add and One. Python does not do that either.

If it is decided to implement it using some kind of successor trait, then I think it should not be implemented for floating point numbers (unless the "successor" of a float x is defined as x + 1).

[thestinger]

Python only has an equivalent to range_step, not range. The range function isn't just a wrapper around range_step, it provides a double-ended iterator intended to be based on predecessors / successors. It uses One and Add as a mostly working hack because the necessary trait didn't exist.

[vks]

About how to fix this issue:
I think there are five possibilities:

1. Add an assertion so that range fails if adding one does nothing. (This may have a huge performance impact.)
2. Implement range for integers only.
3. Implement range using a successor trait. Do or do not implement that trait for floats. (This has the advantage of being able to define range for chars.)
4. Do nothing and accept that size_hint may be wrong and the iterator may not terminate for floats. This behavior should be mentioned in the documentation however.
5. Make size_hint not return an upper bound. (This only fixes the size hint. It would be more correct, because currently the code implicitly assumes x + One::one() != x.)

(I would favor 2. or 3.)

Edit: @thestinger I removed the paragraph about Python's range, because it was talking past each other.

The range function isn't just a wrapper around range_step, it provides a double-ended iterator intended to be based on predecessors / successors.

I don't know what the intention was when range was first implemented. But you could implement (a bit redundantly) DoubleEndedIterator for RangeStep as well, so I don't really see why that shows any intention to be different than range_step.

[Veedrac]

Instead of 1. we could just have range check start != start + one && stop - one != stop on instantiation, which would be fast in most cases. I don't know whether this would optimise out for integers, but if not it should.

[thestinger]

It's not going to optimize out for big integers, and might not optimize out for primitive integers.

[vks]

Instead of 1. we could just have range check start != start + 1 && stop - 1 != stop on instantiation, which would be fast in most cases. I don't know whether this would optimise out for integers, but if not it should.

This is a good idea. It does not really matter whether it optimizes out, because it is only done once. (You don't call range very often.)

[thestinger]

Code size does matter, and making the loop end condition more complex is going to make it harder for LLVM to optimize it down to the same code as the equivalent C loop.

[Veedrac]

The loop would be the same; it's just the creation of the range that would have the check. In other words, it would go here: https://github.com/rust-lang/rust/blob/master/src/libcore/iter.rs#L1952.