Higher kinded polymorphism

[rust-highfive]

Issue by tiffany352
Monday Sep 02, 2013 at 01:14 GMT

For earlier discussion, see rust-lang/rust#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.

[larroy]

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

[AlexanderKaraberov]

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.

[Gankra]

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.

[huonw]

Search keywords: higher kinded types, HKT, monad, functor. (cc #1185 (comment))

[int-index]

Why is no one working on this?

[antonkatz]

Are there any status updates at this time?

[steveklabnik]

@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.

[ticki]

@steveklabnik I wonder what it would look like. Do anyone have any ideas about how the semantics, design, and syntax would be?

[steveklabnik]

Nobody has come up with that stuff yet, no, or at least, no serious proposals.

[tiziano88]

OK, let's talk about syntax as a light starter then.

Looking at the proposals made so far for Swift in typelift/swift#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> { ... }
}

[glaebhoerl]

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.

[tiziano88]

Also possibly related to @glaebhoerl's proposal: https://ghc.haskell.org/trac/ghc/wiki/DependentHaskell/Phase1

[comex]

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

[int-index]

Wadler's law in action...