Why does `Fn() -> T` constrain `T` but `Fn(T) -> T` does not

Question

The following code compiles fine:

struct StructA<F>(F);
impl<F, T> StructA<F> where F: Fn() -> T {}

Although T doesn't show up in StructA's type parameters, it is still constrained due to the where clause. This trick is used, for example, in std::iter::Map so Map<I, F> only needs two type parameters while the impl<B, I, F> Iterator for Map<I, F> takes three.

However the following code does not compile:

struct StructB<F>(F);
impl<F, T> StructB<F> where F: Fn(T) -> T {}

error[E0207]: the type parameter `B` is not constrained by the impl trait, self type, or predicates
 --> src/lib.rs:5:9
  |
5 | impl<F, T> StructB<F> where F: Fn(T) -> T {}
  |         ^ unconstrained type parameter

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

Playground Link

This is unintuitive, why would using T in more places make it less constrained? Is this intended or is it a limitation in Rust?

---

Note this also happens with regular traits, i.e. the desugared version of Fn:

trait FnTrait<Args> {
    type Output;
}

// Works
struct StructA<F>(F);
impl<F, T> StructA<F> where F: FnTrait<(), Output = T> {}

// Fails
struct StructB<F>(F);
impl<F, T> StructB<F> where F: FnTrait<(T,), Output = T> {}

Playground Link

Answer 1

Consider if we implement Fn manually (of course this requires nightly)...

#![feature(fn_traits, unboxed_closures)]

struct MyFunction;
impl<T> FnOnce<(T,)> for MyFunction {
    type Output = T;
    extern "rust-call" fn call_once(self, (v,): (T,)) -> T { v }
}

Now imagine your struct:

struct StructA<F>(F);
impl<F: FnOnce(T) -> T, T> StructA<F>{
    fn foo(self) -> T { (self.0)() }
}

let s: StructA<MyFunction> = ...;
s.foo(); // What is `T`?

While the reference says:

Generic parameters constrain an implementation if the parameter appears at least once in one of:

• ...
• As an associated type in the bounds of a type that contains another parameter that constrains the implementation

This is inaccurate. Citing the RFC:

Type parameters are legal if they are "constrained" according to the following inference rules:

• ...
• If <T0 as Trait<T1...Tn>>::U == V appears in the impl predicates, and T0...Tn are constrained and T0 as Trait<T1...Tn> is not the impl trait reference then V is constrained.

That is, all type parameters should that appear in the trait should be constrained, not just one of them.

I've opened an issue in the reference repo.

Related: https://github.com/rust-lang/rust/issues/25041.

Answer 2

You always need to be able to deduce the generic type parameters of an impl from the self type of the impl (and possibly the trait being implemented, if it's a trait impl). In the first case, F: Fn() -> T, it is possible to derive T from the self type StructA<F>. However, with the trait bound F: Fn(T) -> T, this is not possible.

The difference between the two cases results from the fact that the return type of the closure trait Fn is an associated type, while the argument types are generic parameters. In other words, you can only implement Fn() -> T for any type F once, and that implementation will have a fixed return type T. The trait Fn(T) -> T, on the other hand, could be implemented for multiple types T for the same F, so given F you can't deduce what T is in general.

In practice it is of course very uncommon that multiple Fn traits are implemented for the same type, and when only using closures it's even impossible. However, since it's possible, the compiler needs to account for it.