Higher kinded polymorphism

[rust-highfive]

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

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.

[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 https://github.com/rust-lang/rfcs/issues/1185#issuecomment-117812357)

[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 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> { ... }
}

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

[tiziano88]

@comex : yes that may be confusing at first, but I think it could make sense:

• trait Foo { fn bar() -> Baz<A> }: A is a concrete type (this assumes that A is the actual name of a struct, for instance); Baz<A> is always a concrete type.
• trait Foo { fn bar<A>() -> Baz<A> }: A is a generic type that has to be supplied (or inferred) when calling bar.
• trait Foo<A> { fn bar() -> Baz<A> }: A is a generic type that has to be supplied (or inferred) when implementing Foo.
• trait<A> Foo { fn bar() -> Baz<A> }: Foo has kind * -> *; A does 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: Self has 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.

[brendanzab]

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?

[tiziano88]

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

[brendanzab]

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.

[RalfJung]

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

[ticki]

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?

[ticki]

Relevant: https://gist.github.com/14427/af90a21b917d2892eace

[antonkatz]

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.

[burdges]

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.

[antonkatz]

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

[ticki]

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

[ticki]

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.

[bluss]

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

[steveklabnik]

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.

[ticki]

@nikomatsakis has some interesting thoughts about HKTs here: https://github.com/rust-lang/rfcs/pull/213#issuecomment-65756753

[ghost]

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.

[burdges]

I'd agree that |T| meshes better with @nikomatsakis's concerns about currying and lifetimes https://github.com/rust-lang/rfcs/pull/213#issuecomment-65756753

I hope Rust avoids the functor morass in OCaML and goes directly for HKTs. It worth checking out section 1.1 here https://ocamllabs.github.io/higher/lightweight-higher-kinded-polymorphism.pdf and maybe https://github.com/ocamllabs/higher

[ticki]

I don't like the |T| syntax, because it is easy to confuse with closures.

[tiziano88]

I also like the idea of different syntax for type variable introduction |T| and consumption <T>, and it looks like it will indeed make it easy to express HKT in some cases.

@Ticki the point is exactly that it mimics the syntax used to introduce arguments in closures, but in the context of type signature only individual type variables may be contained, so there should be no risk of confusion.

[burdges]

Appears HKT in https://gist.github.com/14427/af90a21b917d2892eace meets @nikomatsakis's restriction that the higher-kinded type be a partially applied type, right? It's maybe worth patching it or similar with more explanatory type variable names and writing up a version using the trait |T| ... syntax, or the trait<T> ... syntax if that's your shade.

As an aside, I have not yet really understood the problems that come from using the mere presences of unbound type variables to denote higher-kinds like in Haskell https://hackage.haskell.org/package/base-4.8.1.0/docs/src/GHC.Base.html#Functor I donno if that "[tethers] the compiler's type inference .. to trait resolution". Ignoring that, couldn't one impose the partially applied type restriction at the impl site somehow without necessarily asking for explicit type variables? It's maybe an issue that Rust already assigns a meaning to lifetimes being unbound elsewhere.

[ticki]

As an aside, I have not yet really understood the problems that come from using the mere presences of unbound type variables to denote higher-kinds like in Haskell

There are two problems with that approach: First of all, this is prone to bugs. If you forget to bind some parameter, you can get problems (though, you'd probably for the most time get compile errors, and not mysterious behavior). Secondly, you cannot define bounds for the free parameters, which takes away the power from HKTs.

[tiziano88]

Secondly, you cannot define bounds for the free parameters, which takes away the power from HKTs.

Is this true? Haskell has HKTs but AFAICT no bounds on the "free" type variables (in fact those are not even present in the typeclass declaration, and the kind is normally also inferred by the compiler).

For reference, in Haskell:

class Functor f where
    fmap :: (a -> b) -> f a -> f b

class Functor f => Applicative f where
    pure :: a -> f a
    (<*>) :: f (a -> b) -> f a -> f b

class Applicative m => Monad m where
    (>>=) :: forall a b. m a -> (a -> m b) -> m b
    return :: a -> m a

[burdges]

Afaik, there is no need for bounds on the type variables that give a type a higher-kind. There are bounds on the higher-kinded type itself, expressed by the =>, but expressing bounds on it's variables sounds incorrect. Afaik bounds on the variables could be expressed later, like through the choice of implementations of the class/trait.

Also, there is no real concern about bugs because if you leave the type variables unbound by mistake then you'll always get a type error from the type not being applied correctly. In fact, there is no worry about "[tethering] the compiler's type inference .. to trait resolution" even, because the unbound type variables get applied in the definition.

In other words, one could detect the higher-kind from the appearance of Self<T> in

trait Monad {
    fn return<T>(obj: T) -> Self<T>;
    fn apply<Start, End, F>(&mut self: Self<Start>, f: F) -> Self<End> where F: FnOnce(Start) -> Self<End>;
}

It'd be a type error if either just Self or Self<T,U> appeared in the same trait as Self<T>.

There is still the issue of formalizing this partially applied type restriction, which admittedly I do not yet fully understand, but it sounds like a restriction on impls. In particular, I doubt one could eliminate the |T| from :

impl Monad for |T| Option<T> {
    fn return<T>(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) }
}

In both snippets, we bind all type variables in the fn lines, not the trait or impl lines, since the trait having a higher-kind actually means it's independent polymorphism of the functions, not polymorphism of the implementation as a whole. Haskell is less verbose here, but afaik the function still gets the quantifier. Rust always makes these quantifiers explicit.

Also, impl Monad for |T,R| Meow<T,R> ... is illegal because Monad has Self<T>, not Self<T,U>. And impl Monad for Option<String> ... is similarly forbidden.

In addition, the partially applied type restriction forbids at least stuff like impl Monad for |T| T { ... } but not sure how far that goes. I suppose impl<E> Monad for |T| Result<T,E> { ... } works fine.

Interestingly, you actually could add bounds to the fn lines in the trait definition, which merely limits your impls, so maybe it's unnecessary. I think the more interesting scenarios are when you must apply new bounds in the impl, like maybe M is a Monad only when applied to Send types or only when some lifetimes workout a particular way.

[infinity0]

https://m4rw3r.github.io/rust-and-monad-trait/ Just linking this here because it talks fairly succinctly about the same issues that I ran into whilst playing with 14427's pseudo-HKT gist from above.

[pthariensflame]

Posting to watch. :)

[jplatte]

@pthariensflame There's a subscribe button as well...

[pthariensflame]

@jplatte But it doesn't cause the thread to show up in the “Participating” tab!

[int-index]

But you aren't participating!

[ticki]

Now, he/she is. :wink:.

[infinity0]

I wrote a comment about the need to exclude FnMut/FnOnce from higher-kinded traits, at least initially: https://m4rw3r.github.io/rust-and-monad-trait/#comment-2532714842

[burdges]

An important use case for higher-kinded types would be simultaneously supporting both single-threaded performance with Rcs vs thread safety with Arcs and Send bounds.

It appears that gj and eventual_io are separate projects in part to provide this separation, which represents some fragmentation in Rust's asynchronous IO ecosystem.

[ticki]

@burdges Yes, that is a very important point. Often you can choose between limiting your libraries scope to single-threading, or sacrificing performance in single-threaded applications. Neither of these should be mutually exclusive with a sufficient type system.

[glaebhoerl]

Just for future reference, what Scala's doing right now https://github.com/scala/scala/pull/5102 may be of interest to us (see also very grokkable explanation).

Though it seems like this specifically wouldn't solve the kind of difficulties Rust has prepared for itself by putting the parameters of Result in the order they are in (which is the specific example from the above gist) and default type parameters at the end of type parameter lists.

[tbenst]

Now that MIR is turned on by default, i'm curious if it's now possible to implement HKT in rust? This is the last piece I and many others are waiting on before making the plunge into rust!

[withoutboats]

@tbenst MIR was a hard blocker on some features having to do with lifetimes, but not higher kinded polymorphism as far as I know. The reason Rust does not currently have higher kinded polymorphism has more to do with a desire to be intentional & careful about how the type system is extended.

Being honest, I hear the opinion you express - that some people don't want to use Rust until it supports this feature - much more often than I see current users struggling with a lack of expressiveness because it isn't present. The one exception is associated type constructors with lifetime arguments, which is why I wrote #1598.

[raulraja]

HKTs would bring a lot of typed FP folks to Rust. It's a must feature if you want to encode abstractions once and necessary for most encoding of typeclasses and techniques associated to typed FP. It also opens the door to powerful typelevel generic techniques. Please say yes to HKTs :)