rfcs
rfcs copied to clipboard
rust-lang
Higher kinded polymorphism
For earlier discussion, see https://github.com/rust-lang/rust/issues/8922
This issue was labelled with: A-typesystem, I-wishlist in the Rust repository
Rust doesn't support higher kinded polymorphism, despite being a common feature in many functional programming languages. As far as I know, it is a commonly requested feature from people in the FP crowd.
To fully support the idioms that HKP supports we would also need implicits, this would be also useful for passing the execution context to futures for example
Can someone tell the status of higher kinded polymorphism in Rust? When will this feature be added to the language approximately? I read related issue but nevertheless couldn't find any new information.
No one is currently implementing it, and no one has made a solid specification of what it would look like. If it happens, it will not be for a long time.
Search keywords: higher kinded types, HKT, monad, functor. (cc https://github.com/rust-lang/rfcs/issues/1185#issuecomment-117812357)
@antonkatz not yet. Lots of work is going into implementing the MIR/HIR RFCs, which enable more typesystem features by making the internal representations easier to operate on.
@steveklabnik I wonder what it would look like. Do anyone have any ideas about how the semantics, design, and syntax would be?
Nobody has come up with that stuff yet, no, or at least, no serious proposals.
OK, let's talk about syntax as a light starter then.
Looking at the proposals made so far for Swift in https://github.com/typelift/swift/issues/1, I personally do not find any of them particularly appealing or suitable for Rust.
Currently I would be leaning towards something like the following (using classic Functor/List example):
Trait declaration
trait<A> Functor {
fn fmap<B>(&self, f: Fn(A) -> B) -> Self<B>;
}
Here Self is inferred to be of kind * -> *, based on the generic parameters to trait, therefore it always needs to have the appropriate number of generics when used in the function signature, so that the kind of the concrete types is always * (in this case, a return type of Self on its own would not be allowed). self is of type Self<A>.
~~Note that I think this means that this syntax can only express only one "layer" of extra type arguments, and could not easily express kinds higher than that (e.g. * -> * -> *).~~
Edit: That is incorrect, the syntax can easily support extra "flat layers", just by adding extra generic arguments to trait, e.g. trait<A,B,C> would make Self of kind * -> * -> * -> *.
Also, HKT would only exist in the context of a trait declaration (e.g. a function outside of a trait could not have a return type of kind * -> *, e.g. List); this restricts the scope of the proposal and simplifies the implementation, but we should consider tradeoffs and alternatives.
Trait implementation
impl<A> Functor for List<A> {
fn fmap<B>(&self, f: Fn(A) -> B) -> List<B> { ... }
}
Cross-pasting from the duplicate issue I opened:
There is some previous discussion about HKTs, type lambdas, type inference, and so on in the comments on the default type parameters RFC.
Given that
:at the type level is already taken for trait bounds, here is my basic idea for the syntax of kinds.The discussion and referenced papers from this Scala issue may also be relevant for us.
Also possibly related to @glaebhoerl's proposal: https://ghc.haskell.org/trac/ghc/wiki/DependentHaskell/Phase1
trait<A> Functor {
To me this looks confusingly similar to trait Functor<A>. (And what relationship does that A have with the one in the Fn?)
Alternate strawman: trait Functor : for<T> type
@comex : yes that may be confusing at first, but I think it could make sense:
-
trait Foo { fn bar() -> Baz<A> }:Ais a concrete type (this assumes thatAis the actual name of a struct, for instance);Baz<A>is always a concrete type. -
trait Foo { fn bar<A>() -> Baz<A> }:Ais a generic type that has to be supplied (or inferred) when callingbar. -
trait Foo<A> { fn bar() -> Baz<A> }:Ais a generic type that has to be supplied (or inferred) when implementingFoo. -
trait<A> Foo { fn bar() -> Baz<A> }: Foo has kind* -> *;Adoes not have to be provided in the trait impl; the trait impl abstracts over this type variable, and uses it to collapse the kind of the trait:Selfhas kind* -> *,Self<A>has kind*.
The pattern here is that, as the introduction of the generic type moves from right to left, the binding of that type parameter to a concrete type happens later and later.
Having a decent syntax for expressing higher kinded traits is important, but I am sure there are more pressing challenges that need to be solved when it comes to figuring out the intricacies of semantics, and how these interacts with the existing features of the type system. Do we need to wait for a more solid, formal foundation for the type system, perhaps post MIR? How does the feature interact with type inference?
How will libraries look once they can take advantage of higher kinded polymorphism? Can we have some interesting examples of what might be possible on the library front to help guide the design process?
@bjz yes I think we definitely need to wait for MIR before we can have a decent idea of how this may be implemented and how it interacts with the rest of the type system, that's why I suggested to start thinking about (or just playing around with) syntax for the time being. If you think this issue is not appropriate to discuss that, I am happy to move the discussion somewhere else.
Good point about providing examples of what would be possible with HKTs that is currently impossible or not ideal, it will be useful also to guide the discussion about semantics once we get closer to that.
Yeah, having a good base of concrete examples might help guide syntax, and figure out desirable semantics. At least it is something that can be done in the mean time, and would really help with eventually crafting high quality RFC.
A fairly simply, but IMHO interesting example is improving the API for iterators: With HKT, we could define the Item associated type to be of kind Lft -> Type, and then have
fn next<'a>(&'a mut self) -> Option<Self::Item<'a>>
This flexibility is needed, e.g., when writing a safe Doubly-Linked-List with Rc and RefCell, and I also recently wrote a blog post that defined a "stream" API that was essentially this, except that it had to work with current Rust as thus ended up being rather convoluted... Here's the crate doc http://burntsushi.net/rustdoc/fst/trait.Streamer.html. The blog post that linked there is http://blog.burntsushi.net/transducers/.
One thing that's important is consistencies. HKT is a very powerful concepts, and will probably be used a lot when (if?) they're introduced. Having syntax and semantics which is consistent with Rust's type system is important for such a big change.
Another subject to discuss is how such a change will affect the libraries. How will libstd look with HKTs?
My humble opinion is that HKT is what brings Rust into a whole different league. Rust might just become a contender in the functional programming community.
In general, higher-kinded polymorphism allows functions to be generic over a type constructors. And rust has many type constructors. :)
As @RalfJung said, they allows functions to be generic over the specific pointer management technique, which suggests they might simplify the contentious situation around allocators.
In Haskell, HTKs appear pretty central to handling errors with type constructors, so they might help simplify exception looking constructs in Rust too.
Also, it appears HKTs would improve dealing with Rust's different types of closures too, which I suspect is what @antonkatz means.
@Ticki you're right. I probably don't. I've looked at learning Rust, but this was a deal breaker. I don't often use HKTs, but once in a while, I encounter a problem that can be solved very nicely with HKTs. What I meant by my comment, is that it's hard to ask a functional programmer to write code without HKTs.
@antonkatz Right, HKTs might render big parts of the API obsolete, so sure adding HKTs is a big thing. But they provide a really nifty abstraction allowing very clean API. But I do believe the change is worth it.
So sure, adding HKTs is a drastic move, but due to the power of them, it's worth the price.
What I meant by my comment, is that it's hard to ask a functional programmer to write code without HKTs.
I see. I must have misunderstood the comment.
I experience the lack of HKT mostly for lifetimes; I would be very happy with just a restriction that enables types to be higher-kinded over just lifetime params.
These are needed for encoding read-only or read-write iterators into a trait in a way that's composable (can recursively pass down a value and interchangeably iterate it and mutate it).
HKTs might render big parts of the API obsolete
We kept HKT in mind when stabilizing libstd, so hopefully this is not true, or at least, on a big scale.
@nikomatsakis has some interesting thoughts about HKTs here: https://github.com/rust-lang/rfcs/pull/213#issuecomment-65756753
Just chiming in on syntax because I've been running into HKT struggles lately. I think that it might be desirable to show HKT as type functions explicitly. Examples:
// HashMap<K, V> reads as "HashMap has a K, V" whereas |K, V| Map reads as "K, V completes a Map"
trait |T| Monad {
fn return(obj: T) -> Self<T>;
fn apply<U>(&mut self: Self<Start>, f: F) -> Self<U> where F: FnOnce(T) -> Self<U>;
}
// |T| Option<T> reads as "with T, we can create an Option with T"
impl Monad for |T| Option<T> {
fn return(obj: T) -> Option<T> { Some(obj) }
fn apply<Start, End, F>(&mut self: Self<Start>, f: F) -> Option<End> where F: FnOnce(Start) -> Self<End> { self.and_then(f) }
}
trait Iterable {
// with a lifetime, we can create an Iter
type |'a| Iter;
fn iter<'a>(&self) -> Self::Iter<'a>
}
impl<T> Iterable for Vec<T> {
// an iter is a function which takes a lifetime and returns a vec::Iter<T>
type Iter = |'a| vec::Iter<'a, T>;
}
fn apply_twice<M: Monad, A>(start: M<A>, f: F) where F: Fn(A) -> M<A> {
start.apply(f).apply(f)
}
fn iterate<I, T: Iterable<Iter=I>>(val: &T) where <I as Iterator>::Item: Debug {
for item in val.iter() {
println!("iterating: {}", item);
}
}
fn main() {
let val = Option::return(5);
assert_eq!(apply_twice(val, |x| Some(x + 1)), Some(7));
}
Note that the |T| syntax uses the same syntax as <T>, besides the surrounding characters. This means that it also supports bounds. Additionally, type parameters which are higher-kinded are written using the |U| V syntax, if I can find a reason why we need those. (e.g. fn thing<|U| V>)
Also haven't thought about how HKT trait objects would work at all. I considered type Iter<'a> but I feel like making HKT look alike with each other and distinctly different from other types is a plus.
For now, the syntax doesn't support simplified lambdas (i.e. |T| Option<T> as Option) due to the number of weird rules with elision and default parameters, and the fact that we don't know how to refer to the argument type, but there may be solutions to add that in after the fact. I feel like any system would fundamentally have that problem, though.
