[stevefan1999]

I wonder if there is any relationship between HKT and C#/Rust generics, from my perspective I always see HKT as "A type that accepts types that generates another type" and generic as "A functor that accepts types that generates another type". That makes me wonder if types and functors are exchangable.

[pdpi]

It's easier to make the parallel between type-level and value-level reasoning.

1 is a value, and int is a concrete type.

function increment(x) { return x + 1 } is a value-level function. You feed it a value x and you get a value back. List<T> is a type-level function: you give it a concrete type T, you get another type back.

function applyTwice(f, x) { return f(f(x)) } is a higher-order function that takes a functions as an input. A higher-kinded type is a higher-order type function.

As a concrete example, consider this pseudo-Java method:

    List<B> map<A,B>(Function<A,B> fn, List<A> as) { ... }

You take a list, and you return a list. Thing is, Java has several list implementations: LinkedList, ArrayList, CopyOnWriteArrayList, and a few others. What I'd like to express is that whatever concrete list type goes in is also the concrete type that comes out. If java allowed it, you could express it like this:

    L<B> map<L<T> extends List<T>,A,B>(Function<A,B> fn, L<A> as) { ... }

This map is generic on L, A, and B, but also L is itself generic, so map is "twice-generic", if you will.

[classified]

Finally an explanation that makes sense. Thank you :)

[pdpi]

In case you're wondering: Where this becomes incredibly powerful is in how it relates to ad-hoc polymorphism. Again, imagine this is pseudo-java.

    // Alternative one: subtype polymorphism. You have to implement Format as part of your type.
    interface Format { String format() }
    
    void printAll<Thing extends Format>(things List<Thing>) { things.forEach(thing => print(thing.format())) }

    // Alternative two: ad-hoc polymorphism. You can implement Format separately from the type you're implementing it for
    interface Format<T> { String format(T t) }
    
    void printAll<Thing>(things List<Thing>, Format<Thing> formatter) { things.forEach(thing => print(formatter.format(thing))) }

Doing ad-hoc polymorphism manually like this is obviously annoying as hell, it's the equivalent of doing dynamic dispatch in C by explicitly passing around vtables, but e.g. Haskell and Rust have direct support for ad-hoc polymorphism through typeclasses and traits respectively. Scala's implicits still require some amount of faffing about, but still make things much easier.

The bit where HKTs come in is when you want to have your interfaces talk about generics:

    // HKT goes here ----V
    interface Iterable<C<_>> { forEach<T>(C<T> collection, Consumer<T> fn) }
    
    
    void printAll<Thing>(things List<Thing>, Format<Thing> fmt, Iterable<List> iter) { iter.forEach(things, thing => print(fmt.format(thing))) }

[ReleaseCandidat]

"A type that accepts types that generates another type" is called a type constructor. And a "kind" is the type of a type constructor, just to have a new name and not needing to call that "type" too. "Generic types" like `Vec<T>` (in Rust) are type constructors, they "generate" a type `Vec<T>` from the type `T`. Type constructors that take one type as argument have the kind `* -> *` (or as Rust-y notation `fn(*) -> *` - read each asterisk as "type". Type constructor that take two types arguments have the kind `* -> * -> *` (Rust-y: `fn(*, *) -> *`). A higher (-order) kinded type takes (for example) a type constructor (here a type constructor which takes just one argument) and generates a type from it: `(* -> *) -> *` (Rust-y: `fn(fn(*) -> *) -> *`.

Edit: I hope now all asterisks are properly escaped ...

[ReleaseCandidat]

Edit2: oh, I guess misunderstood "A type that accepts types that generates another type". If you meant to say "A type that accepts (types that generates another type)", so a type constructor that accepts type constructors and not "(A type that accepts types) that generates another type", which is a type constructor.

[chrisweekly]

Yeah, I think "types that generateS" is either a typo or sloppy English; it should be "types that generate".

I often wonder why it's so common for programmers with an acute awareness and mastery of syntax and grammar in programming languages to just throw all that precision and attention to detail out the window when it comes to natural language.

[DougBTX]

For Rust, pre-GAT, there was no way to “output” a type which could be “called” with further arguments (very fuzzy terminology, sorry, best I can do!) or maybe in other words, you could write functions which retuned values, but not new functions.

Nowadays, GATs support a bigger subset of HKTs, but still not everything as I understand it.

https://blog.rust-lang.org/2022/10/28/gats-stabilization.htm...