Why are Fn*s parameterized over inputs?

[kristof]

I’ve written out this post here as well: https://www.reddit.com/r/rust/comments/3mqfqm/why_is_the_argument_type_of_the_fn_family_of/

Shouldn’t the definition of FnOnce, et al, be something more like

trait Fn {
    type Input: Tuple;
    type Output;
}

Then, that makes

Fn(I) -> O 

sugar for

Fn<Input=(I,), Output=I>

If this discrepancy seems unnecessary and obtuse, I offer some reasoning. Parameterized traits in Rust represent possibly open relations between types. All floats are related to integral types through the Add trait implementations for floats, but f32 and f64 are also reflexively related to themselves by the very same trait! Convenient. Convertable types T to V are related by the type relation Into for T. The flexibility in this is that for any type V, I can always add a new instance of Into or Add for type T (satisfying coherence, of course). This is because relations need not be right unique! This is also convenient.

Of course this is undesirable for sets of types that relate many associated types. We wouldn’t want many different Iterator implementations for any concrete iterating struct, after all. Thus for any multiparameter traits where one or more of the types are uniquely determined by any number of the previous types, we move those types into the trait members as associated types.

What does this have to do with closures and functions? For any function-like type F, its input and output types are uniquely determined by the type F. I don’t see this changing, ever, unless Rust accepts variadic functions (which I hope it does not), so it makes no sense for F to have a parameterized input rather than an associated one.

So let’s say this change actually happened. Does anything get easier, or become possible? And why do I care about this so much?

Related to the Higher Kinded Types discussion in Rust’s community, I have been investigating using Haskell’s constraint kinds to implement certain traits in Rust. This solves a lot of problems and in my opinion it is actually imperative for Rust to adopt because there are so many trait constraints in Rust compared to Haskell. For instance, in Haskell, every type is comonoidal (Copy), but most value types in Rust are linear unless specified otherwise! So being able to let trait implementations specify their own constraints is absolutely necessary if HKTs are going to be anything more than a limited-functionality curiosity. (For an example of where this pops up and why it is important, see “The Constrained Monad Problem”.)

Now here’s the bit about functions. If you wanted to specify fn traits at the implementation level, you inevitably need the input types just to write out a valid constraint because the traits are parameterized over the input type, not associated with them into families. So I have to write “Fn<(T,)>”, because a bare Fn will not do. But what is “T”? If one is writing a trait over constructor types, i.e the very reason for wanting HKTs in the first place, then one does not have access to the input type of the function in the first place!

Okay, you say, then make the impl of the trait be generic over T. But T appears nowhere in the top of the trait definition, nor should it because it is a trait over constructors, not “filled” types. So this kind of abstraction becomes impossible while function-like Fs are parameterized over the inputs instead of being associated with them.

[nikomatsakis]

I’ve probably written this up before, but it is necessary for the Args type parameter to be an input into the trait in order to support higher-ranked trait bounds. For example, if we wish to have a type T that supports the signature:

T: for<'a> Fn(&'a i32) -> &'a i32

Now, if we were using your approach, this would be equivalent to something like:

T: for<'a> Fn<Args=&'a i32, Ret=&'a i32> // leaving out the tuple for simplicity

The thing is, we can project any associated type independently. So we might do T::Ret (or, in more detail, <T as Fn>::Ret) to get the return type. But really, to know the return type, we have to know the argument type. There is nothing linking the argument/return types to be linked together. In fact, if we tried that approach, you wouldn’t even be able to implement the Fn trait and have it return a reference. This is because of the rules in RFC 447, which are intended to prevent examples like the one above, where you have a lifetime 'a that appears in an output type of a trait but not any of its input types.

In contrast, given the current setup, when we extract out the return type as we have to write something like <T as Fn<&'b i32>>::Ret – i.e., we have to supply the input type at the same time. Now the result of Ret is well-defined, it must be &'b i32.