Make return type of the `Fn` traits an associated type

[nikomatsakis]

I think that the argument types cannot be an associated type, but the return type of the Fn traits can and ought to be.

Why make the return type associated?

It seems right: I don't think I want the ability to have functions overloaded purely on return type. A similar argument was gracefully made by @aturon regarding binary operators recently.

But also, it would make an impl like example (from @alexcrichton) legal:

impl<R,F> Foo for F : FnMut() -> R { ... }

Right now this is illegal because the type R is unconstrained. This is kind of counter-intuitive.

Why not make the argument types associated?

The reason that the argument types cannot be associated is because of HRTB. Imagine we have a constraint like F : Fn(&i32) -> &i32. Now, if both A and R were associated types, we'd have to be able to evaluate independent projections like F::A and F::R but ensure that we got consistent lifetimes in both cases -- unfortunately, we can't do that, because there is nothing linking the lifetimes together. Put another way, if A and R were associated types, then F : Fn(&i32) -> &i32 would be sugared into three predicates internally:

• F : Fn
• for<'a> <F as Fn>::A == &'a i32
• for<'b> <F as Fn>::R == &'b i32

Note that the connection between A and R has been lost. (While implementing associated types, I spent a while trying to make this work out, and it really...just doesn't.)

On the other hand, if we convert just the return type to be an associated type, the example works just fine. We desugar the F : Fn(&i32) -> &i32 example into:

• for<'a> F : Fn<(&'a i32,)>
• for<'a> <F as Fn<(&'a i32,)>>::R == &'a i32

Another reason not to make the argument types associated is that it permits more overloading. For example, the "identity" function works (hat tip: @eddyb):

struct Identity;
impl<A> Fn(A) for Identity {
    type R = A;
    fn call(&self, (arg,): (A,)) -> A {
        arg
    }
}

cc @aturon @huonw

[nikomatsakis]

Nominating because we ought to settle this. Also, it's observable as the @alexcrichton example shows (though it's a backwards compat change, I believe).

[nikomatsakis]

(Also, this seems like a small enough detail that I don't think it merits a full RFC.)

+1. I think making the return type an associated type could allow for a generic implementation of currying too.

[reem]

While I'm in the "unrestricted overloading" camp for unboxed closures, I'm willing to support this if it enables more patterns like Identity and they can't be enabled with the current situation.

Question: would the sugar for unboxed closure bounds change?

If you view traits with associated types as something like type level functions then making the return type of Fn an associated type moves them closer to dependent functions. This should allow for all sorts of flexibility that otherwise wouldn't be possible.

The Identity trick is just a special case of that:

// note: haven't tried compiling this

trait TyFn<In> { type Out; }

enum Identity<A> {}
impl<A> TyFn<A> for Identity<A> { type Out = A; }

enum Dup<A> {}
impl<A> TyFn<A> for Dup<A> { type Out = (A, A); }

trait IsComposite { type Fst; type Snd; }
impl<A, B> IsComposite for (A, B) { type Fst = A; type Snd = B; }
enum Swap<A: IsComposite> {}
impl<A: IsComposite> TyFn<A> for Swap<A> { type Out = (<A as IsComposite>::Snd, <A as IsComposite>::Fst); }

struct Helper<X, TF: TyFn<X>>;
impl<A, TF: TyFn<A>> Fn(A) for Helper<A, TF> {
    type R = <TF as TyFn<A>>::Out;
    …
}

[reem]

I'm convinced.

[jroesch]

@nikomatsakis @darinmorrison 👍

[nikomatsakis]

I've got this ~95% implemented.