Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Higher kinded polymorphism #324

Open
rust-highfive opened this issue Sep 25, 2014 · 106 comments
Open

Higher kinded polymorphism #324

rust-highfive opened this issue Sep 25, 2014 · 106 comments
Labels
A-typesystem Type system related proposals & ideas postponed RFCs that have been postponed and may be revisited at a later time. T-lang Relevant to the language subteam, which will review and decide on the RFC.

Comments

@rust-highfive
Copy link

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.

@nrc nrc added the postponed RFCs that have been postponed and may be revisited at a later time. label Sep 25, 2014
@larroy
Copy link

larroy commented Dec 28, 2014

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
Copy link

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
Copy link
Contributor

Gankra commented Jan 2, 2015

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
Copy link
Member

huonw commented Jul 1, 2015

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

@int-index
Copy link

Why is no one working on this?

@antonkatz
Copy link

Are there any status updates at this time?

@steveklabnik
Copy link
Member

@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
Copy link
Contributor

ticki commented Dec 7, 2015

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

@steveklabnik
Copy link
Member

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

@tiziano88
Copy link

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
Copy link
Contributor

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
Copy link

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

@comex
Copy link

comex commented Dec 8, 2015

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
Copy link

Wadler's law in action...

@tiziano88
Copy link

@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
Copy link
Member

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
Copy link

@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
Copy link
Member

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
Copy link
Member

RalfJung commented Dec 8, 2015

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
Copy link
Contributor

ticki commented Dec 8, 2015

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
Copy link
Contributor

ticki commented Dec 8, 2015

@antonkatz
Copy link

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
Copy link

burdges commented Dec 9, 2015

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
Copy link

@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
Copy link
Contributor

ticki commented Dec 10, 2015

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

@glaebhoerl
Copy link
Contributor

It's not enough to make sure they're behind pointers in the fn signature, you also have to make sure they're not used in any way that's not behind-a-pointer in the function body either (copied to the stack, calling another function that's not "only-behind-pointers-safe", etc.). Unless you handle size/alignment completely dynamically...

@jmegaffin
Copy link

@glaebhoerl I don't see any issue with doing it dynamically. Performance will be a little worse, of course, but that's unavoidable. It's only not worse in languages like Haskell because they don't do any monomorphization in the first place.

If you want to use a generic function polymorphically, you just compile it to be dynamic where necessary. Any generic functions that are called that depend on a polymorphic type must in turn be compiled to be dynamic and then used at that call site. That should be enough.

@withoutboats
Copy link
Contributor

It sounds like we'd have to restrict this to object safe bounds and represent this the same as trait objects - that is for<T: Read> fn(&T) would be no different in representation from fn(&Read). In which case I don't see any expressive difference from trait objects either.

@glaebhoerl
Copy link
Contributor

@jmegaffin Wait. If you handle size/alignment dynamically then do you even need the "behind a pointer" restriction in the signature? I would think that "statically require every type-instantiation to have the same representation" ("behind a pointer") so that you don't need anything extra at runtime (i.e. analogous to the uniform boxed representation of most extant GCed languages), and "actually deal with all the statically-unknown representations at runtime instead" (so-called "intensional type analysis"), are two disjoint approaches.

@DemiMarie
Copy link

What about higher kinded lifetimes?

Lifetime parameters are always erased, so the problems with runtime representation simply vanish. And the problem can be much harder to work around, often requiring unnecessary copying.

@tioover
Copy link

tioover commented Sep 18, 2017

RFC #1598 is merged

This is an incremental step toward a more general feature commonly called "higher-kinded types," which is often ranked highly as a requested feature by Rust users.

@Centril Centril added the T-lang Relevant to the language subteam, which will review and decide on the RFC. label Feb 23, 2018
@cruhl
Copy link

cruhl commented Oct 1, 2018

Has there been any recent movement around this issue?

@steveklabnik
Copy link
Member

The foundational work in the compiler is being done to enable this. So not directly, but in a broad sense, yes.

@skeet70
Copy link

skeet70 commented Oct 15, 2018

@steveklabnik any links to what work is ahead before HKTs would be directly possible? I tried searching around in the rust issues and rfcs but couldn't figure out what the status is.

@withoutboats
Copy link
Contributor

withoutboats commented Oct 15, 2018

@steveklabnik any links to what work is ahead before HKTs would be directly possible? I tried searching around in the rust issues and rfcs but couldn't figure out what the status is.

The answer depends on what you mean by "directly." Work is underway to implement generic associated types (GATs), described in RFC #1598 and tracked in this tracking issue: rust-lang/rust#44265 Generic associated types are capable of representing the same type relationships as the higher kinded type class polymorphism in Haskell (for example) - what is normally called "HKT". But its not exactly the same feature, its just equally expressive.

There is no work underway on introducing a mechanism for polymorphism over higher kinded terms other than through generic associated types, and I don't currently see much impetus to add a separate faculty other than GATs.

Niko Matsakis wrote a blog series exploring the relationship between GATs and HKT, the last post contains links to all the previous ones: http://smallcultfollowing.com/babysteps/blog/2016/11/09/associated-type-constructors-part-4-unifying-atc-and-hkt/ (he calls GATs "ATCs" in that series)

EDIT: Looking at Niko's blog post again, I strongly recommend it. Its an excellent representation of our thinking about HKT in Rust right now.

@steveklabnik
Copy link
Member

@skeet70 i was typing a response but @withoutboats just beat me to it; GATs are not exactly this but can provide similar things.

"impl Trait in Traits" is also, in my understanding, equivalent to HKT.

It is true that we have no immediate plans to offer HKT directly at the time.

@jadbox
Copy link

jadbox commented Sep 22, 2019

I'd love to see something like Archery baked into the language. It would allow people to easily and ergonomically abstract over Rc and Arc types.

@ibraheemdev
Copy link
Contributor

ibraheemdev commented Nov 26, 2020

The foundational work in the compiler is being done to enable this. So not directly, but in a broad sense, yes

Is there no update or proposal regarding this after two years?

@steveklabnik
Copy link
Member

Correct, those underlying features are still being worked on, and have not stabilized yet. Things take time.

@ibraheemdev
Copy link
Contributor

ibraheemdev commented Dec 2, 2020

Emulating HKTs with GATs on nightly gives us a nice looking (incorrect due to not constraining the return type to Self, but still shows that it may be possible) Monad:

#![feature(generic_associated_types)]

trait Monad {
    type Start;
    type End<B>: Monad;
    
    fn bind<B>(self, f: impl Fn(Self::Start) -> Self::End<B>) -> Self::End<B>;
}

It can be implemented for Option<T> like so:

impl<A> Monad for Option<A> {
    type Start = A;
    type End<B> = Option<B>;
    
    fn bind<B>(self, f: impl Fn(A) -> Option<B>) -> Option<B> {
        self.and_then(f)
    }
}


fn main() {
    let monad = Some(1).bind(|x| Some(x * 2));
    println!("{:?}", monad); // Some(2)
}

@orium
Copy link
Member

orium commented Dec 2, 2020

Yes, but that definition of monad is not precise enough. You can implement a monad where bind() accepts a function that return another type of monad, instead of "Self".

@MikailBag
Copy link

I think family pattern allows one to express monad precisely, although it's verbose (playground):

#![feature(generic_associated_types)]

trait MonadFamily {
    type M<T>;
    
    fn pure<T>(value: T) -> Self::M<T>;

    fn bind<T, U, F>(this: Self::M<T>, f: F) -> Self::M<U>
    where
        F: Fn(T) -> Self::M<U>;
}

struct Maybe;

impl MonadFamily for Maybe {
    type M<T> = Option<T>;
    
    fn pure<T>(value: T) -> Option<T> {
        Some(value)
    }
    
    fn bind<T, U, F>(this: Option<T>, f: F) -> Option<U>
    where
        F: Fn(T) -> Option<U>,
    {
        this.and_then(f)
    }
}

fn play_with_monad<M: MonadFamily>() where M::M<i32>: std::fmt::Debug{

    let x = M::pure::<i32>(1);
    let x = M::bind(x, |x| M::pure(2*x));
    println!("{:?}", x);
}

fn main() {
    play_with_monad::<Maybe>();
}

@strega-nil
Copy link

I think the biggest issue with that is that style (@MikailBag) is that you can't pass only one type parameter if there's more than one; otoh, doing C++ style tag structs:

#![feature(generic_associated_types)]

trait Monad /* : Applicative (for pure/return, doesn't matter for this example) */ {
    type S<T>;

    fn bind<T, U, F>(_: Self::S<T>, f: F) -> Self::S<U>
    where
        F: FnOnce(T) -> Self::S<U>;
}

struct OptionMonad;
impl Monad for OptionMonad {
    type S<T> = Option<T>;
    fn bind<T, U, F>(opt: Self::S<T>, f: F) -> Self::S<U>
    where
        F: FnOnce(T) -> Self::S<U>
    {
        match opt {
            Option::Some(x) => f(x),
            Option::None => Option::None,
        }
    }
}

fn bind<M, T, U, F>(_: M, x: M::S<T>, f: F) -> M::S<U>
where
    M: Monad,
    F: FnOnce(T) -> M::S<U>
{
    M::bind(x, f)
}

fn main() {
    let x = bind(OptionMonad, Some(1), |x| Some(x * 2));
    println!("{:?}", x);
}

@ibraheemdev
Copy link
Contributor

ibraheemdev commented Jan 23, 2021

Just thinking about syntax, what about having HKTs represented as a bound on Self?

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

@fosskers
Copy link

fosskers commented Jun 21, 2021

Yeah, why is it that Self can't have a type parameter? I'd love to write this:

pub trait Void {
    fn void(self) -> Self<()> {
        todo!()
    }
}

@ibraheemdev
Copy link
Contributor

ibraheemdev commented Jun 21, 2021

@fosskers Because it's not a trivial feature to implement, no one has done the design work, and there are other accepted, more important rfcs to work on. GATs (available on nightly) represent most of the useful part of higher kinded types, and can be used to emluate real HKTs in a limited capacity via the family pattern: http://smallcultfollowing.com/babysteps/blog/2016/11/03/associated-type-constructors-part-2-family-traits/

@wangbyby
Copy link

Does any pr related to HKTs? Thx.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
A-typesystem Type system related proposals & ideas postponed RFCs that have been postponed and may be revisited at a later time. T-lang Relevant to the language subteam, which will review and decide on the RFC.
Projects
None yet
Development

No branches or pull requests