Pre-RFC: Generalized higher-ranked trait bounds

Summary

Extend higher-ranked trait bounds to types.

Motivation

When working with closures, it would be useful if anonymous functions could have generic bodies that were reusable across multiple different parameter types. This would broadly speed up development and reduce human error by getting rid of redundancy, and may have other use cases that I haven't considered.

For example, say you have a Filter trait and you want to reuse the same function body for a few different Filter types:

struct Counter<I> {
    a: fn(I, FilterAll) -> usize,
    b: fn(I, FilterTrue) -> usize,
}

fn counter<I, F>(f: fn(I, F) -> usize) -> Counter<I>
where
    I: Iterator<Item=bool>,
    F: Filter,
{
    let a: fn(I, FilterAll) -> usize = f;
    let b: fn(I, FilterTrue) -> usize = f;
    Counter { a, b }
}

let c = counter(|iter, filter| {
    iter.filter(|x| filter.has(x))
        .count()
});

As I see it, this would be a natural extension to higher-ranked trait bounds in which the parameters are part of the type itself:

let f: for<'a> fn(&'a i32, &'a i32) -> &'a i32 = |a, b| {
    if a > b { a } else { b }
};

Specifics

Types can be referenced with unspecified generic parameters. For instance, for<T> Option<T> would count as a type in the same way that for<'a> fn(&'a i32) does.

fn assert_is_some(option: for<T> Option<T>) {
    assert!(option.is_some());
}

In this case, for<T> Option<T> is known to be covariant over T and therefore can't be downcast into a more specific Option<_>. However, any subtype such as Option<i32> can be implicitly upcast into for<T> Option<T>, in much the same way that &'static i32 can be upcast into &'a i32:

assert_is_some(Some(123));

These higher-ranked parameters can also be bounded by traits or lifetimes to refine their possible subtypes.

Referencing a generic function without specifying its generic parameters would produce the type for<..> fn(..), similar to how it does for lifetimes. Function types are contravariant over their parameters, and therefore can be downcast into a function type with more specific parameters (but not the other way around).

fn sum<T>(a: T, b: T) -> T
where
    T: std::ops::Add<Output = T>
{
    a + b
}

let f: for<T: std::ops::Add<Output=T>> fn(T, T) -> T
    = sum;

assert_eq!(f(1_i32, 2), 3);
assert_eq!(f(1_u64, 2), 3);

It's also possible that type identifiers like Option by itself could be sugar for for<T> Option<T>, in the same way that Ref is sugar for for<'a> Ref<'a>. However, this might make code harder to follow and could lead to confusion by new users, so it's tentative.

Alternatives

In the original example, one could instead add a separate argument for each case (fn(I, FilterAll) -> bool and fn(I, FilterTrue) -> usize), and simply force users to either copy-paste their closure or reuse it with a function. However, this means that adding more cases to Counter would require a new constructor and possibly a breaking change.

Another option is to use an enum instead of a generic type, but this comes at a runtime cost in terms of performance and variant enforcement.

Allowing for<T> Option<T> seems very odd to me, as it should represent a type that's both a Option<()>, Option<i32>, Option<String> etc etc at the same time, which is not possible.

Even for<T> fn(T) doesn't seem possible for the same reason, since function pointers are a single type (as generic function when monomorphized correspond multiple function pointers, one for each monomorphization, this is also the reason why generic methods make traits non-object-safe).

The way you describe it, it seems to just be another generic parameter of the function (but then why not put it on the function rather than the type).

The only situation I can see this work would be with trait bounds and where clauses, which is exactly where this is already being implemented Add experimental support for `for<T>` binders in limited positions · Issue #81 · rust-lang/types-team · GitHub

3 Likes

I imagine the generic bound would become part of the type itself, where for<T> Option<T> acts as a standalone supertype for Option<()>, Option<i32>, etc. each of which can be upcast into for<T> Option<T>. Similar to the standalone type for<'a> fn(&'a i32) that acts as a subtype for fn(&'static i32), fn(&'_ i32), etc.

Option<T> itself would only be usable with the most generic impls for Option<T>, as if impl<T> Option<T> {..} was really for a specific type called for<T> Option<T>. Downcasting for<T> Option<T> into a specific Option<i32> would be impossible, unless it's as a contravariant parameter (for<T> fn(Option<T>) can be converted into fn(Option<i32>) because the function only operates on generic options).

I'm not sure how difficult this would be to actually implement, but it seems to extend the existing interface that Rust already has for lifetimes on function pointer types.

Regardless I think that "for<T> binders in limited positions" thing would probably solve the motivation for this post anyways, so I'm looking forward to that. Thank you my dearest friend

This doesn't check out. You say that for<'a> fn(&'a i32) acts as a subtype of fn(&'static i32), fn(&'_ i32) etc, but then want for<T> to be a supertype of Option<()>, Option<i32> etc?

Moreover if it was a supertype, how would it be represented in memory?

I knew I was missing something obvious - yeah this probably wouldn't work just because of the memory layout problem.

Also the subtyping would respect variance where function pointer types are contravariant over their parameters (the subtype relationship is inverted), whereas most types like Option<T> are covariant and just inherit the relationship

I don't think contravariance has anything to do with higher ranked function pointers/trait bounds. fn(&'a i32) -> &'a i32 is invariant in 'a, but for<'a> fn(&'a i32) -> &'a i32 is still a subtype of fn(&'static i32) -> &'static i32, fn(&'_ i32) -> &'_ i32 etc etc.

1 Like

That's true, but I think this must be something to do with the output type being constrained by the input type.

I would think that if a function returned a standalone reference like 'static, you would be able to upcast that into a function that returns any lifetime. Just like if I had a function that just returns Dogs I should be able to upcast that into a function that returns Animals. While on the other hand if I had a function that takes a generic Animal and then return that same Animal (guaranteed), I should be able to use that as a function that takes a Dog and returns that same Dog