generics - What is a higher kinded type in Scala?

Question

You can find the following on the web:

1. Higher kinded type == type constructor?

   class AClass[T]{...} // For example, class List[T]
   

   Some say this is a higher kinded type, because it abstracts over types which would be compliant with the definition.

   Higher kinded types are types which take other types and construct a new type

   These though are also known as type constructor. (For example, in Programming in Scala).

2. Higher kinded type == type constructor which takes type constructor as a type parameter?

   In the paper Generics of a Higher Kind, you can read

   ... types that abstract over types that abstract over types ('higher-kinded types') ..."

   which suggests that

   class XClass[M[T]]{...} // or
   
   trait YTrait[N[_]]{...} // e.g. trait Functor[F[_]]
   

   is a higher kinded type.

So with this in mind, it is difficult to distinguish between type constructor, higher kinded type and type constructor which takes type constructors as type parameter, therefore the question above.

Answer 1

Let me make up for starting some of this confusion by pitching in with some disambiguation. I like to use the analogy to the value level to explain this, as people tend to be more familiar with it.

A type constructor is a type that you can apply to type arguments to "construct" a type.

A value constructor is a value that you can apply to value arguments to "construct" a value.

Value constructors are usually called "functions" or "methods". These "constructors" are also said to be "polymorphic" (because they can be used to construct "stuff" of varying "shape"), or "abstractions" (since they abstract over what varies between different polymorphic instantiations).

In the context of abstraction/polymorphism, first-order refers to "single use" of abstraction: you abstract over a type once, but that type itself cannot abstract over anything. Java 5 generics are first-order.

The first-order interpretation of the above characterizations of abstractions are:

A type constructor is a type that you can apply to proper type arguments to "construct" a proper type.

A value constructor is a value that you can apply to proper value arguments to "construct" a proper value.

To emphasize there's no abstraction involved (I guess you could call this "zero-order", but I have not seen this used anywhere), such as the value 1 or the type String, we usually say something is a "proper" value or type.

A proper value is "immediately usable" in the sense that it is not waiting for arguments (it does not abstract over them). Think of them as values that you can easily print/inspect (serializing a function is cheating!).

A proper type is a type that classifies values (including value constructors), type constructors do not classify any values (they first need to be applied to the right type arguments to yield a proper type). To instantiate a type, it's necessary (but not sufficient) that it be a proper type. (It might be an abstract class, or a class that you don't have access to.)

"Higher-order" is simply a generic term that means repeated use of polymorphism/abstraction. It means the same thing for polymorphic types and values. Concretely, a higher-order abstraction abstracts over something that abstracts over something. For types, the term "higher-kinded" is a special-purpose version of the more general "higher-order".

Thus, the higher-order version of our characterization becomes:

A type constructor is a type that you can apply to type arguments (proper types or type constructors) to "construct" a proper type (constructor).

A value constructor is a value that you can apply to value arguments (proper values or value constructors) to "construct" a proper value (constructor).

Thus, "higher-order" simply means that when you say "abstracting over X", you really mean it! The X that is abstracted over does not lose its own "abstraction rights": it can abstract all it wants. (By the way, I use the verb "abstract" here to mean: to leave out something that is not essential for the definition of a value or type, so that it can be varied/provided by the user of the abstraction as an argument.)

Here are some examples (inspired by Lutz's questions by email) of proper, first-order and higher-order values and types:

                   proper    first-order           higher-order

values             10        (x: Int) => x         (f: (Int => Int)) => f(10)
types (classes)    String    List                  Functor
types              String    ({type λ[x] = x})#λ   ({type λ[F[x]] = F[String]})#λ

Where the used classes were defined as:

class String
class List[T]
class Functor[F[_]]

To avoid the indirection through defining classes, you need to somehow express anonymous type functions, which are not expressible directly in Scala, but you can use structural types without too much syntactic overhead (the #λ-style is due to https://stackoverflow.com/users/160378/retronym afaik):

In some hypothetical future version of Scala that supports anonymous type functions, you could shorten that last line from the examples to:

types (informally) String    [x] => x              [F[x]] => F[String]) // I repeat, this is not valid Scala, and might never be

(On a personal note, I regret ever having talked about "higher-kinded types", they're just types after all! When you absolutely need to disambiguate, I suggest saying things like "type constructor parameter", "type constructor member", or "type constructor alias", to emphasize that you're not talking about just proper types.)

ps: To complicate matters further, "polymorphic" is ambiguous in a different way, since a polymorphic type sometimes means a universally quantified type, such as Forall T, T => T, which is a proper type, since it classifies polymorphic values (in Scala, this value can be written as the structural type {def apply[T](x: T): T = x})