Returning Generic Type Without Syntactic Sugar

Hi all, I was playing around with rust iterator and found this issue. My code was like this:

pub fn foo<'a>(v: &'a Vec<i32>) -> impl Iterator<Item = &'a i32> {
    v.iter().filter_map(|v| Some(v))
}

pub fn bar<'a, T>(v: &'a Vec<i32>) -> T 
where
    T: Iterator<Item = &'a i32>
{
    v.iter().filter_map(|v| Some(v))
}

fn main() {
}

(Playground)

And somehow, I got an error in the bar function, but not the foo function. AFAIK both of them should be identical (the foo version is just the syntactic sugar of the bar version). Here is the error:

   Compiling playground v0.0.1 (/playground)
error[E0308]: mismatched types
 --> src/main.rs:9:5
  |
5 | pub fn bar<'a, T>(v: &'a Vec<i32>) -> T 
  |                -                      -
  |                |                      |
  |                |                      expected `T` because of return type
  |                this type parameter    help: consider using an impl return type: `impl Iterator<Item = &'a i32>`
...
9 |     v.iter().filter_map(|v| Some(v))
  |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected type parameter `T`, found struct `FilterMap`
  |
  = note: expected type parameter `T`
                     found struct `FilterMap<std::slice::Iter<'_, i32>, [closure@src/main.rs:9:25: 9:28]>`

For more information about this error, try `rustc --explain E0308`.
error: could not compile `playground` due to previous error

What is happening here? Why can't I return a generic type T where T is bounded Iterator<Item = &'a i32>? Does it have something to do with the lifetime?

1 Like

No. impl Trait in return position is an existential type, which means "I'm going to give you a type implementing this trait, but I won't tell you what". This means that the function implementation chooses the type.

In contrast, a generic type parameter means that T will be chosen by the caller. Obviously, that may be different from the actual type you are trying to return; what should happen if someone calls bar::<SomeTypeThatIsNotFilterMap>()? The types wouldn't match up, then.

The type you are returning is pronouncedly not generic. It is FilterMap<slice::Iter<i32>>.

As it should be clear from the above explanation, it doesn't.

6 Likes

Ah, I see. That makes sense. So if the impl Trait is in the parameter, then the caller tells what is actual type, but if it's in the return position, the implementation tells what it is.

So, the code below:

pub fn foo<'a>(v: &'a Vec<i32>) -> impl Iterator<Item = &'a i32> {
    v.iter().filter_map(|v| Some(v))
}

is actually a syntactic sugar for

pub fn foo<'a>(v: &'a Vec<i32>) -> FilterMap<slice::Iter<i32>, ...> {
    v.iter().filter_map(|v| Some(v))
}

And rust desugaring it into FilterMap<slice::Iter<i32>,...> by checking the actual type of v.iter().filter_map(|v| Some(v)). Whereas, if we put the impl Trait in the parameter position, rust desugaring it by checking the actual type from the caller side.

Am I understand it correctly?

Exactly. It's pretty confusing or at least inconsistent, so I generally recommend against ever using impl Trait in argument position. Use it in return position only, and use generics when you need generics.

1 Like

Yes.

Yes, it's the same as using a generic type argument, except the type argument is anonymous, smilar to the following:

fn inspect(value: impl std::fmt::Debug) {
    println!("Got value: {value:?}");
}

fn inspect2<_Anonymous>(value: _Anonymous)
where
    _Anonymous: std::fmt::Debug
{
    println!("Got value: {value:?}");
}

fn create() -> impl std::fmt::Debug {
    "One"
}

fn main() {
    inspect(4);
    inspect("Four");
    inspect2(4);
    inspect2("Four");
    let value = create();
    assert_eq!(format!("{value:?}"), "\"One\"");
    // We can't assume the result of `create()` is any particular type:
    // let wont_work: &'static str = create(); 
    // We only know that it implements a particular trait:
    let dyn_ref_to_value: &dyn std::fmt::Debug = &create();
    assert_eq!(format!("{dyn_ref_to_value:?}"), "\"One\"");
}

(Playground)

Note that inspect and inspect2 aren't exactly the same yet, because inspect2 has one type argument while inspect has zero type arguments.

1 Like

Not quite just sugar, because what callers are allowed to do is more restricted. RPIT is also a useful semver tool, because the caller is only allowed to use things from the trait you said you're returning, not things from other traits it implements or from the concrete type.

fn slice_iter_directly() -> std::slice::Iter<'static, i32> {
    (&[]).iter()
}

fn slice_iter_rpit() -> impl Iterator<Item = &'static i32> {
    (&[]).iter()
}

fn main() {
    let it = slice_iter_directly();
    it.len(); // from `ExactSizeIterator` -- works!
    it.as_slice(); // inherent -- works!

    let it = slice_iter_rpit();
    it.len(); // ERROR!
    it.as_slice(); // ERROR!
}

https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=2c0b2eef99bcd50767f7fe98e21961aa

Except that auto traits leak through.

2 Likes

Interesting.. So there is a difference. With impl Trait, the caller returned a more restrictive type, whereas returning the concrete type directly doesn't have additional restriction.

An inconvenient consequence of which is that one has to actively remember to add other, useful traits to the RPIT signature. For example, I remember writing some signal processing code and being too lazy to type out all the sliding window and convolution iterator adapters over the input slice, so I essentially wrote

fn transmogrify(signal: &[f64]) -> impl Iterator<Item = f64> {
    signal.windows(N).map(slow_indiscreet_fourier_transform).other_adaptor()
}

and then I was surprised when I couldn't use the returned iterator in a bi-directional and exact-sized way in my own code. Of course, while I was hammering out the code inline, the concrete types were known locally, and <[u8]>::Iter and co are ExactSizeIterators, so there was no problem. But this moment felt like a (bad) revelation as to how many times I might have written RPIT in library code which is potentially useless to others because it doesn't include some common trait it should.

Sure. Everything that's flexibility for one party is more work for the other party that needs to be able to handle the uncertainty.

Just like tolerances in manufacturing, for example -- ease for the fabricator is more work for the designer, and vice versa.

3 Likes

While a lot of people share your view that APIT vs RPIT is inconsistent ("RPIT is an existential type but APIT is a universal type") I want to explicitly note that jauhararfin's description treats both uniformly: whomever provides the impl Trait decides the concrete type, and whomever receives the impl Trait can only use the guaranteed API of Trait.

3 Likes

But then this should have also been true for generics in argument vs. return position, which it isn't (as it can't be).

impl Trait is similar to Box<dyn Trait> in both positions. It's essentially a pair {type: Trait, value: type}, except for impl Trait the return type must be uniquely determined by input types.

Generics are different because in generics the type is a parameter passed into the function.

It maybe a bit confusing, but it's quite consistent. Arguments are controlled by the one who calls the function but return values are controlled by implementer. Why is it confusing that impl works in the exact same way I don't know, but it's definitely consistent.

Maybe it's confusing because Rust tries to treat generic parameters like normal, imperative-programming-style values while in reality they naturally behave more like Prolog variables, but as long as Chalk is not a thing we, kinda, don't have a choice.

Of course it can be. But for that you need prolog-style resolver and Rust doesn't use one currently.

Whether such change to the language is possible in backward-compatible way or even desirable at all is another question.

But it's definitely theoretically possible.

No, it's not a mere question of a compiler limitation, it's deeper. A generic type parameter is a parameter for a good reason: it's possible to substitute it with potentially many types. (Hence the need for universal quantification in the signature.) For an existential, this is not possible by definition. You can't ask the compiler "I know you are returning a Foo which implements Bar, but I want a Qux, which also implements Bar". It plainly doesn't make any sense. No amount of clever constraint solving changes this, as long as the existential is backed by a static type.

I am aware that you can write a function like

fn into_existential<T: Display>(value: T) -> Box<dyn Display> {
    Box::new(value)
}

which creates an existential backed by a choice of the caller; however, in this case, the choice(s) is/are still being made over the set of generic parameters, and it becomes an implementation detail in the return type (i.e. the caller still doesn't choose the return type, it is what it is).

You can't ask, but that's design decision of Rust, not some fundamental law of universe or math.

After all compiler is able to pick proper generic when you write let x: i32 = x.into(), which means it already works with traits, what makes it impossible to extend that to return types of generics and pick the implementation of generic which produces proper return type?

If you have prolog-style solver then you can even imagine a situation where you accept (𝓧 𝓨) and return (𝓩 𝓣) and here 𝓧 and 𝓩 come from implementation and are calculated on basis of 𝓨 and 𝓣.

I think you implicitly assume that some parameters in type calculations are inputs while some other are outputs, but in Prolog variables don't work that way: the caller decided what would be input and what would be output on per-call basis.

Why into makes sense but generation of generic on basis of what type of result is needed doesn't?

Yes, but once again, it's a design decision of Rust, not something fundamental.

Whether changing it would make resulting language easier or harder to use is different question, of course.