Higher kinded polymorphism syntax


#1

How would it look like in Rust?

I can imagine something like:

struct Node(i32);

struct GraphSearch<T<*>> { frontier: T<Node> }

while you can do things like

struct Node(i32);

struct GraphSearch<T<*: Bound>> { frontier: T<Node> }

I don’t know how one would attach where clauses to it. Maybe with this exact syntax it’s not possible? Have there been other proposals with a different syntax?


#2

Associated type constructors can have the most simple and intuitive syntax:

trait StreamingIterator {
    type Item<'x>;
    fn next<'a>(&'a mut self) -> Option<Self::Item<'a>>;
}

For myself I’ve been using a lambda syntax when considering this feature hypothetically, but I doubt its the best syntax:

trait |A| Monad<A> {
    ...
}

struct GraphSearch<|A| T<A>> {
    ...
}

#3

I like:

enum Option<type T> { ... }

struct Array<type T, const N: usize> { ... }

struct GraphSearch<type<type> T> { frontier: T<Node> }

// and/or:
struct GraphSearch<type T<type>> { frontier: T<Node> }

// and/or:
struct GraphSearch<T<type>> { frontier: T<Node> }

If we wanted perfect symmetry with the value level, the syntax would be Type: Kind (e.g. T: type), mirroring Value: Type (e.g. foo: T), but that’s already used for trait bounds. I believe the best remaining possibility is this vaguely C+±ish prefix syntax. Here the symmetry is with the syntax of type declarations, which is quite nice in its own right.

Even Haskell is moving away from * in kind syntax as overly cryptic, introducing the name Type for the same thing in GHC 8. In Rust the kind of types should just be called type.

It’s also the default, so the explicit type kind-annotation in the first two examples is of course purely optional. It also meshes well with const-generics, as in the second example.

The last three are all equivalent. N.B. I am not suggesting that all three should be supported. They are possibilities. The equivalence between the first two of them can be thought of as currying: the first one being analogous to fn T() -> fn(type) -> type, and the second one to fn T(type) -> type. (This extends consistently to types with more parameters, so that e.g. type T<type, type>, type<type> T<type> and type<type, type> T are also all equivalent.) The last two are equivalent simply by extending the "the default kind is type" rule to "the default ‘return kind’ is type".

Probably we should choose whether we like the first or second form better, and support only one of them, and if we choose the second then we should also allow the third.

I’m not sure what to do about lifetimes. Maybe we should just introduce the lifetime keyword and have it work the same way. (So struct Blah<type RefType<lifetime, type>> { blah: RefType<'static, i32> }; type BlahMut = Blah<&mut>;.) That’s inconsistent with lifetime syntax in the non-higher-kinded case, but type RefType<', type> is… really bad. (If we had adopted my preferred syntax for lifetimes this wouldn’t be an issue. Alas.)


#4

One level down, this would be analogous to writing:

fn some_hof(|n: i32| f(n))

Instead of:

fn some_hof(f: fn(i32))

In other words, |var| expr is the syntax of literals (values) which inhabit types, not of types themselves. So one level back up, it would be the syntax of type literals inhabiting kinds, rather than kinds themselves – that is, if we wanted to add support for type lambdas, which nobody has yet proposed that I’m aware of, this would be the appropriate syntax for them.


#5

Yeah for higher kinded parameters its quite wrong, but I do think its somewhat elegant for handling higher kinded Self parameters of traits, which are not otherwise explicitly declared.


#6

Why type and not Type?


#7

I was thinking of allowing Self to be explicitly declared with for, paralleling impls:

trait Clone { ... }
trait Clone for type { ... }
trait Clone for Self { ... }
trait Clone for type Self { ... }

trait Functor { ... } // maybe we could have kinds inferred in simple cases?
trait Functor for type<type> { ... }
trait Functor for type<type> Self { ... }
trait Functor for type Self<type> { ... }
trait Functor for Self<type> { ... }

(Again, not every syntax has to or should be supported - just brainstorming.)

Per “kind syntax mirrors declaration syntax”, if we only had structs and not enums then it’d be called struct, and vice versa. But we do have both so type seems like the best umbrella over them, and at least type declarations are a thing. Also it’s already a keyword, the other kinds/decls (const, likely lifetime, and possibly trait if we do something like GHC’s ConstraintKinds) are lowercase keywords as well, and it kinda parallels C++'s typename.


#8

*type*: *kind* might actually work if:

  1. Kind literals are syntactically distinct (e.g. fn<kind0, kind1, kind2> -> kind 3).
  2. Named kinds (if we ever get them) live in the same namespace as traits/bounds.

#9

How would a Monad parameter be represented? Could you do fn foo<T: type -> type + Monad>() (or something??) or would you have to do fn foo<T: type -> type>() where T: Monad?


#10

I really like the type<type> syntax but wouldn’t it be consistent to have something like this when defining actual HKTs:

trait<type> Functor {
    fn map<A, B, T>(m: Self<A>, f: F) -> Self<B> where F : Fn(Self<A>) -> Self<B>;
}

trait<type> Monad : Functor {
    fn unit<T>(item: T) -> Self<T>;
    fn bind<A, B, T>(m: Self<A>, f: F) -> Self<B> where F : Fn(A) -> Self<B>;
}

and when used:

fn foo<type<type> M: Monad>() { ... }
// or equivalently:
fn foo<type<type> M>() where M : Monad { ... }

Just thinking …


#11

This reads to me like it’s saying that “the trait Functor is generic over types” – so either that Self is a type, or that there’s an additional type parameter beyond Self. (Whereas we want to say that Self is generic over a type.)


#12

For sure:

  • fn foo<T: (fn<type> -> type) + Monad>()
  • fn foo<T: fn<type> -> type>() where T: Monad

(n.b. not sure whether for or fn is better)


More radically, I’ve been thinking about embracing type: bound with trait bounds being treated at as the universe/sub-kind of types that implement a trait, and + is kind-intersection. This means that

  • fn foo<T>() where T: (fn<Copy> -> Copy) + Functor

could also be OK. Now “real” kinds would be disjoint, so might as well not allow combining them with +, but for other stuff like the above why not!

If we got polykinded traits, we could do the set monad this way.


#13

I’m not sure I follow you. To me this syntax does not suggest that Self a type. There is a difference between:

trait Functor<T> { ... }
   // ^^^^^^^^^^ Self is a type

trait<type> Functor { ... }
         // ^^^^^^^ Self must be provided a type

Now I realize that my proposed syntax suggests Functor has kind type -> trait. This is indeed not very appropriate as it seems Functor<isize> for example cannot really be thought as a trait in any useful manner. I would go for your second proposition trait Functor for type<type> extending trait Clone for type.