Why do you need higher kinds?

Question

Some languages allow for classes and functions with type parameters (such as List<T> where T may be an arbitrary type). For example, you can have a function like:

List<S> Function<S, T>(List<T> list)

Some languages however allow this concept to be extended one level higher, allowing you to have a function with the signature:

K<S> Function<K<_>, S, T>(K<T> arg)

Where K<_> itself is a type like List<_> that has a type parameter. This "partial type" is known as a type constructor.

My question is, why do you need this ability? It makes sense to have a type like List<T> because all List<T> are almost exactly the same, but all the K<_> can be entirely different. You can have an Option<_> and a List<_> that have no common functionality at all.

Answer 1

Since no one else has answered the question, I think I'll give it a go myself. I'm going to have to get a bit philosophical.

Generic programming is all about abstracting over similar types, without the loss of type information (which is what happens with object-oriented value polymorphism). In order to do this, the types must necessarily share some sort of interface (a set of operations, not the OO term) that you can use.

In object-oriented languages, types satisfy an interface by virtue of classes. Each class has its own interface, defined as part of its type. Since all classes List<T> share the same interface, you can write code that works no matter which T you choose. Another way to impose an interface is an inheritance constraint, and although the two seem different, they are sort of similar if you think about it.

In most object-oriented languages, List<> is not a proper type in itself. It has no methods, and thus has no interface. It is only List<T> that has these things. Essentially, in more technical terms, the only types you can meaningfully abstract over are those with the kind *. In order to make use of higher-kinded types in an object-oriented world, you have to phrase type constraints in a manner consistent with this restriction.

For example, as mentioned in the comments, we can view Option<> and List<> as "mappable", in the sense that if you have a function, you could convert an Option<T> into an Option<S>, or a List<T> into a List<S>. Remembering that classes cannot be used to abstract over higher-kinded types directly, we instead make an interface:

IMappable<K<_>, T> where K<T> : IMappable<K<_>, T>

And then we implement the interface in both List<T> and Option<T> as IMappable<List<_>, T> and IMappable<Option<_>, T> respectively. What we've done, is using higher-kinded types to place constraints on the actual (non-higher-kinded) types Option<T> and List<T>. This is how it's done in Scala, though of course Scala has features such as traits, type variables, and implicit parameters that make it more expressive.

In other languages, it is possible to abstract over higher-kinded types directly. In Haskell, one of the highest authorities on type systems, we can phrase a type class for any type, even if it has a higher kind. For example,

class Mappable mp where
    map :: mp a -> mp b

This is a constraint placed directly on an (unspecified) type mp which takes one type parameter, and requires it be associated with the function map that turns an mp<a> into an mp<b>. We can then write functions that constrain higher-kinded types by Mappable just like in object-oriented languages you could place an inheritance constraint. Well, sort of.

To sum things up, your ability to make use of higher-kinded types depends on your ability to constrain them or to use them as part of type constraints.