Open Stebalien opened 8 years ago
/cc @bluss @iopq
I'm currently not able to use the library version of the function because of this limitation and I have to "specialize" manually by adding my own definition. This defeats the point of having libraries for functional programming in Rust, since the code doesn't compile due to this limitation.
@iopq
That's an inherent limitation - generic type parameters can only be instantiated monomorphically:∀T. fn(T) -> T
can't be instantiated to ∀'a. fn(&'a u32) -> &'a u32
.
@arielb1,
Then how does id_wrapped
work? To the best of my understanding, it's doing exactly what you're saying can't be done.
@Stebalien
id_wrapped
uses a lifetime parameter, not a type parameter. It starts as being ∀T ∀'a. fn(&'a T) -> &'a T
.
@arielb1 Sorry, I should have explained further. id_wrapped
is instantiated exactly once, therefore, it's body must be defined (in the executable) exactly once. Therefore, the rust compiler must be able to somehow tell that id::<'a, T>
is defined for all 'a
because the caller, id_wrapped
, is defined for all 'a
and is instantiated exactly once.
Here, I'm asking that rust use this knowledge to infer that <typeof id>: for<'a> Fn(&'a T) -> &'a T
.
As a trait object? The problem is that <typeof id>
, which is basically System F's ∀T. T -> T
(except for irrelevant fn-item vs. fn-ptr issues), is not really a type within Rust's trait/type system. Rust types can not contain higher-rank type parameters, and this is not expected to change in the nearby future (see: impredicativity). So when you use a Rust type, it is always instantiated to a type with no higher-ranked type parameters.
id_wrapped
works because it uses a skolemized type, rather than a higher-ranked one.
@arielb1 Types which are higher-rank over lifetimes only don't suffer from impredicativity issues, no? You can't self-reference because they aren't of the correct kind for the higher-rank parameter.
Not saying they wouldn't be complicated to implement, just that I don't think they necessarily introduce decidability problems.
Triage: this still fails to compile.
Triage: current output
error: implementation of `FnOnce` is not general enough
--> src/main.rs:11:5
|
11 | has_hrl(id);
| ^^^^^^^ implementation of `FnOnce` is not general enough
|
= note: `fn(&'2 ()) -> &'2 () {id::<&'2 ()>}` must implement `FnOnce<(&'1 (),)>`, for any lifetime `'1`...
= note: ...but it actually implements `FnOnce<(&'2 (),)>`, for some specific lifetime `'2`
Rust has trouble seeing that a generic function is "generic" over higher ranked lifetimes. This behavior is best described by example. Given:
Rust complains:
However, the
has_hrl(id_wrapped)
andhas_hrl(|x| id(x))
calls demonstrate that, at some level, the rust type checker infers thatid
implementsfor<'r> Fn(&'r ()) -> &'r ()
. That's why I filed this as a bug instead of an RFC issue. However, I can move this if you feel that it's too much of a feature request.My motivation is functional programming. Not being able to infer that a generic function is defined for some HRL makes it impossible to use such functions with, e.g.,
Iterator::filter
.