The iterator binds its associated type not by the first call


#1

Edit: The question is about, mainly, why the iterator did not bind elem to f64 in the first loop, or did it?
Edit #2: Type inference is clear. The question is about associated type of Iterator trait.

I thought elem would bind to f64, because it’s the first, but no. Why iterators behave this way, what feature is it? The first elem is reference, the second was bound through dereferencing, I thought that’s the difference, but what exactly happend and what about the cloned() version?

https://play.rust-lang.org/?version=stable&mode=debug&edition=2015&gist=ff89fba94bdf7892d2711fcf3d5299bc

  fn main() {
  let a = [1., 2., 3., 4., 5.];

  let epsilon = 1e-8;
  for elem in a.iter() {
    let diff: f64 = elem - 6.;
    assert!(diff.abs() < epsilon);
  }
  
  let epsilon = 1e-8;
  for elem in a.iter() {
    let diff: f32 = *elem - 6.;
    assert!(diff.abs() < epsilon);
  }

  let epsilon = 1e-8; 
  for elem in a.iter().cloned() {
    let diff: f32 = elem - 6.;
    assert!(diff.abs() < epsilon);
  }
}

#2

Did you mean f32 in the first one? array.iter() is an iterator of references, but f32 is lenient and has subtraction defined for references, so you don’t have to dereference it. With the second one you dereferenced ot, so it works, in the last one rach element of the iterator is cloned, so that converts the &f32 to a f32


#3

No.

What I was asking is “why the iterator did not bind to f64 in the first loop?”.

As per your answer, if I understand it correctly, it is not true.

Try this piece. It won’t compile. An explicit dereferencing is required in this case because it involves a type binding / conversion through reference. (the wording may not be 100% correct). In the first one, * is not needed because it’s f64.

fn main() {
  let a = [1., 2., 3., 4., 5.];

  let epsilon = 1e-8;
  for elem in a.iter() {
let diff: f32 = elem - 6.;
assert!(diff.abs() < epsilon);
  }
}

#4

I don’t know the exact answer, but my hunch is this is demonstrating (perhaps odd/unexpected) differences in trait resolution. A 1.0 literal defaults to f64 when not inferred otherwise, and perhaps when you have a &f64 which has Sub impls (just not a matching one), the compiler makes a full stop rather than trying to infer &f32.


#5

I’m not sure you were answering “why the iterator didn’t bind to f64 in the first loop?”.

The problem it seems to be the iterator binds it’s associated type (elem) to f32 in the second / third loop (that’s what it seems to me).

see this piece, Sub does assume f64 first, so it works without the other two loops. Remeber you answered my question yesterday? I understand this part now. The problem is that when the other loop exist, like in the original post, rust assumes elem to be f32 in the first loop. Am I just confused?

fn main() {
  let a = [1., 2., 3., 4., 5.];

  let epsilon = 1e-8;
  for elem in a.iter() {
    // let diff: f64 = elem; //mismatch f64 and &flaot
    // let diff: f32 = elem - 6.;  //mismatch f32 and f64
    let diff: f64 = elem -6.;  //ok
    assert!(diff.abs() < epsilon);
  }
}

#6

By the way, 1.0 literal is not f64 unless it’s used somehow. (maybe internally it is)

fn main() {
    let a: i32 = 6.;
    let a: i32 = 6.0f32;
}
error[E0308]: mismatched types
 --> src\main.rs:4:18
  |
4 |     let a: i32 = 6.;
  |                  ^^ expected i32, found floating-point variable
  |
  = note: expected type `i32`
             found type `{float}`

error[E0308]: mismatched types
 --> src\main.rs:6:18
  |
6 |     let a: i32 = 6.0f32;
  |                  ^^^^^^ expected i32, found f32

https://play.rust-lang.org/?version=stable&mode=debug&edition=2015&gist=79e065a288509709c41b11aeab37a512


#7

https://doc.rust-lang.org/reference/tokens.html#floating-point-literals:

Same thing goes for fixed point literals, except they default to i32.

Type inference is a wild beast - it usually Just Works and one doesn’t think about it. But occasionally it surfaces its wild side, and I frankly just quiet it by putting the explicit type ascription(s), as necessary. I’m not aware of any formal definition of how it works, and so it’s a bit difficult to say whether something is a bug, limitation, unfortunate consequence of some interaction of its rules, or by design.


#8

The * is not needed because the operators (in this case -) are implemented for references of floating point numbers as well as the normal values of floating point numbers.

i.e.

impl<'a> std::ops::Sub<f32> for &'a f32 {
    // ...
}

exists, so you don’t need to dereference the the values given by the iterator.
If you try each loop in isolation, then you will get different results. This is why when you just put

It didn’t work, but it you put the other two loops in it will work. This seems to be some odd behavior of type inference, and can be cleared up with a single type annotation.

fn main() {
  let a = [1., 2., 3., 4., 5.];

  let epsilon = 1e-8;
  for elem in a.iter() {
    let elem: &f32 = elem; // this could also be &f64
    let diff: f32 = elem - 6.;
    assert!(diff.abs() < epsilon);
  }
}

#9

Thanks for clarification, but any idea about why the iterator works that way, why it didn’t bind its assciated type to f64 in the first loop? Another wild beast?


#10

The three loops in the original post all work in separation.

Sub assumes f64 that’s why

let a: f64 = elem - 1.; //this works because no type change
let a: f32 = elem - 1.; //doesn't work

The latter statement also works if I put in the other two loops, that’s my main question. It seems to me the iterator binds elem to f32 in the second loop, so f64 in the first loop fails.

The second and third loop has no precedence to each other. If you remove the first loop, and change the order and type of the other two. Always the last loop gets the error. But when you put in the first loop with one of the others, the first loop (f64 one) always gets the error no matter what the order is (that’s what I got if I didn’t do it wrong).

Trait’s associated type is designed to bind to the type in the implementation. And it seems in this case, the f64 loop has an implementation and the type recognized. Then why the iterator skip it and goes for the second? My guess is because elem in the first loop is a reference and in the other two it is a “true” variable. But I don’t know what feature made it work that way.


#11

Exactly, due to how type inference works, they will work separately but not together.


What do you mean by this?


let’s simplify the problem a bit, (I know that you may know this, but I just want to setup some common ground to talk about this).

A)

let elem = 10.0;
let a: f64 = elem - 1.0;

B)

let elem = 10.0;
let a: f32 = elem - 1.0;

Both of these work. Just like how each loop will work in isolation.


C)

let elem = 10.0;
let a: f32 = elem - 1.0;
let b: f64 = elem - 1.0;

D)

let elem = 10.0;
let a: f64 = elem - 1.0;
let b: f32 = elem - 1.0;

Both of these don’t work. Specifically, b, doesn’t compile in both, because elem inferred a different type after the second line with a.

This is similar to when you had all three loops together.


tl dr
in A) and B), there is no conflict in type inference so it works, but in C) and D) there is a conflict in type inference, so it fails.


#12

Sub assumes f64 that’s why

let a: f64 = elem - 1.; //this works because no type change
let a: f32 = elem - 1.; //doesn't work

Sorry it may be unclear, but I meant you should read the first line with the comment together. And it should only be considered with the context of for loop of a iterator. i.e.,

fn main() {
  let a = [1., 2., 3., 4., 5.];

  let epsilon = 1e-8;
  for elem in a.iter() {
    // let diff: f64 = elem; //mismatch f64 and &flaot
    // let diff: f32 = elem - 6.;  //mismatch f32 and f64
    let diff: f64 = elem -6.;  //ok
    assert!(diff.abs() < epsilon);
  }
}

I agree with what you said, execpt that the two pieces below are different.

let elem = 10.0;
let a: f32 = elem - 1.0; //ok
let a = [1., 2., 3.];
for elem in a.iter() {
  let b: f32 = elem; //not compile
}

But let’s put this aside, my main concern is why in the original post, the iterator takes in f32, which is in the latter code, for elem but skips f64 in the first loop.


#13

Okay, so it boils down to this. Type inference for floating point variables is really sort of a hack, and your examples show what, to be honest, feel like a bug.

let _: f32 = 1. - 1.;  // allowed
let _: f32 = &1. - 1.; // type error

What happens in these two cases? I’d describe it as follows:

In the first case, we can rewrite it as

let a = 1.;
let b = 1.;
let c = a - b;
let _: f32 = c;

I imagine that the type checker goes through this and deduces something like the following:

  • After line 1, the type of a is ?float_0, a fresh type inference variable for a floating point literal.
  • After line 2, the type of b is ?float_1, a separate type inference variable.
  • At line 3, when it typechecks a - b, it ends up with a value of type <?float_0 as Sub<?float_1>>::Output.
  • The compiler recognizes this as a special case and deduces that a, b, and c all have the same type, ?float_0.
  • At line 4, it deduces ?float_0 = f32.

Now we change it up slightly:

let a = &1.;  // <-- & added
let b = 1.;
let c = a - b;
let _: f32 = c;

The type checker goes through this and deduces the following:

  • At line 3, when it typechecks a - b, it ends up with a value of type <&(?float_0) as Sub<?float_1>>::Output.
  • It does not recognize this as a special case. As a result, it concludes that ?float_0 is unconstrained, and so it deduces ?float_0 = f64. It quickly further determines that b and c are both f64.
  • At the final line, there is a type error.

This is pretty unintuitive behavior. It’s hard to see why &T - U is not special cased like T - U is.


#14

https://github.com/rust-lang/rust/issues/57447


#15

Good clarification.

But I’m still not sure that explained my main question in the original post, why the iterator did not bind to f64 in the first loop, which is about associated type of iterator trait. I’m new to rust. This is actually the first example (adopted from one in the cook book) I really studied after the book. So bear with me.

The code below works, as you explained,

fn main() {
    let a = [1., 2., 3., 4., 5.];

    let epsilon = 1e-8;
    for elem in a.iter() {
        let diff: f64 = elem - 6.;
        assert!(diff.abs() < epsilon);
    }
}

but the same loop in the original post does not when the other two added behind. If it’s something related to type inference I won’t be surprised. But a.iter() is a trait impl, elem is an associated type of the trait. It should be bound to a concrete type in the impl. Since the preceeding code works, it somehow figures out the type already and could bind it to the trait, and I was expecting the latter two loops get an type error.

The iterator trait definition:

trait Iterator {
    type Item;  //should bind to the type in implementation, once only
    fn next(&mut self) -> Option<Self::Item>;
}

In the original post, it seems to me the iterator binds elem to f32 in the second loop, so f64 in the first loop gets an type error.

The second and third loop has no precedence to each other. If you remove the first loop, and change the order and type of the other two, the last loop always gets the error. But when you put in the first loop with one of the others, the first loop (f64 one) always gets the error no matter what the order is (that’s what I got if I didn’t do it wrong).

Trait’s associated type is designed to bind to the type in the implementation. And it seems in this case, the f64 loop has an implementation and the type recognized (as you explained). Then why the iterator skips it and goes for the second? My guess is that because elem in the first loop is a reference and in the other two it is a “true” variable, so somehow the latter ones take priority. But that behavior seems very weird to me.

Hope it’s clear. Let me know if not. Thanks for reading.


#16

This is not true. When the type checker gets here, that associated type can still contain type inference variables. And it does; the type of a is Vec<?float_0>, so the Item type is &?float_0.

Later, in the second loop, it finds ?float_0 = f32.


#17

I agree with the first half. But when it gets to the highlighted text, it could find out the type is f64. It does when no other loops exist, probably through the Sub operator.

But it seems that the compiler is not settled right here. When it gets to the second loop, it does not force the type f64, but find that f32 is better, i.e., the type checker has a searching and priority mechanism. Though I don’t know if that’s intentional or not. And what’s the cretieria, here seeminly the difference is reference and dereferenced variable. Maybe Rust needs to infer twice in the first loop but only once in the second loop? At this stage I think I can live with it. The rest is just for curiosity.


#18

But when it gets to the highlighted text, it could find out the type is f64 .

Again, this is where you’re off. After it reads that line, it knows nothing more than the following:

// Line 6: typeof(elem): Sub<typeof(6.), Output=typeof(diff)>
&(?float_0): Sub<?float_1, Output=f64>

Now, yes, based on the impls of Sub that exist for primitive floating point types, it could in theory deduce that ?float_0 = ?float_1 = f64. But for some reason, it doesn’t.

Why? I dunno; maybe somebody is banking on us adding impl Sub<f64, Output=f64> for &f32 or something. (…I’m kidding, of course. It’s far more likely just a bug in the compiler.)

Later, it finds the same line in the second loop and determines that:

// Line 12: typeof(*elem): Sub<typeof(6.), Output=typeof(diff)>
?float_0: Sub<?float_2, Output=f32>

and as I noted earlier, this time it IS recognized as a special case, thanks to the & no longer being there. As soon as it sees this, it deduces that ?float_0 = ?float_2 = f32. At some point after this (maybe immediately once it learns the identity of ?float_0, or maybe after it reaches the last line in the function, I dunno), it goes back to validate the trait bound it never finished proving on line 6, which now looks like:

// Line 6: typeof(elem): Sub<typeof(6.), Output=typeof(diff)>
&f32: Sub<?float_1, Output=f64>

The error message suggests that it then recognizes &f32: Sub<?float_1> as another special pattern and deduces that ?float_1=f32, ultimately resulting in the precise error message you see:

error[E0271]: type mismatch resolving `<&f32 as std::ops::Sub<f32>>::Output == f64`

#19

And to complete the banquet, allow me to similarly explain what happens when you remove the 2nd and 3rd loops:

fn main() {
  let a = [1., 2., 3., 4., 5.];

  let epsilon = 1e-8;
  for elem in a.iter() {
    let diff: f64 = elem - 6.;
    assert!(diff.abs() < epsilon);
  }
}

The only reason this snippet works in the absence of the other loops boils down to what I said in my first comment (where I originally misinterpreted what you were doing in the OP). Basically, due to the aforementioned bug, this loop does not constrain the type of a (only the other two do):

  1. Same as in the full example, when the compiler finishes type checking line 6, all it knows is that &(?float_0): Sub<?float_1, Output=f64>. It does not know that elem is &f64 when it finishes looking at this line.
  2. When it reaches the end of the function, there is nothing to constrain ?float_0, so it defaults to f64. (this is different from the full example!)
  3. It sees the second pattern and deduces ?float_1 = f64.
  4. We end up with &f64: Sub<f64, Output=f64>, which is fortuitously correct.

You can easily verify this by taking this snippet and changing the diff: f64 to diff: f32. It will suddenly stop compiling, because &elem will always default to f64 regardless of how you annotate diff.


#20

Okey. Now I understand. You are right, it’s still a type inference problem.

I knew let diff: f32 = elem - 6.; doesn’t work, that’s where I started, I removed the * to see what whould happen and all hell breaks loose.

To summarize, see this piece

fn main() {
  let a = [1., 2., 3., 4., 5.];

  let epsilon = 1e-8;
  for elem in a.iter() {
    // let diff: f32 = elem - 6.;  //won't compile
    // let diff: f32 = *elem - 6.;  //compiles, elem is f32
    let diff: f64 = elem - 6.;  //compiles, elem is float
    // let diff: f64 = *elem - 6.;  // complies, elem is f64
    let () = elem;
    assert!(diff.abs() < epsilon);
  }
}

So, back to a.iterator, elem is not bound to any concrete type in the first loop, it was bound probably in the second loop. And I have a guess just for guessing iteself, Rust complier does not infer type merely by order of code, it perhaps pulls all things together and runs them through a nested if or match to determine and then check them.

Great discusstion. Thank a lot.
p.s. How do you find the type of a variable? The only way I know is to cast it to a wrong type.