What is a higher kinded type in Scala?

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})

(This answer is an attempt to decorate Adriaan Moors answer by some graphical and historical information.)

Higher kinded types are part of Scala since 2.5.

• Before that Scala, as Java till now, did not allow to use type constructor ("generics" in Java) to be used as type parameter to a type constructor. e.g.

   trait Monad [M[_]]
  

  was not possible.

  In Scala 2.5 the type system had been extended by the ability to classify types on a higher level (known as type constructor polymorphism). These classifications are known as kinds.

  (Picture derived from Generics of a Higher Kind)

  The consequence is, that type constructor (e.g. List) could be used just as other types in type parameter position of type constructors and so they became first class types since Scala 2.5. (Similar to functions which are first class values in Scala).

  In the context of a type system supporting higher kinds, we can distinguish proper types, types like Int or List[Int] from first-order types like List and types of a higher kind like Functor or Monad (types which abstract over types which abstract over types).

  The type system of Java on the other side does not support kinds and therefore has no types of a "higher kind".

  So this has to be seen against the background of the supporting type system.

• In the case of Scala you often see examples of a type constructor like

   trait Iterable[A, Container[_]]
  

  with the headline "Higher kinded types", e.g. in Scala for generic programmers, section 4.3

  This is sometimes missleading, because many refer to Container as higher kinded type and not Iterable, but what is more precise is,

  the use of Container as type constructor parameter of a higher kinded (higher-order) type here Iterable.

The kind of ordinary types like Int and Char, whose instances are values, is *. The kind of unary type constructors like Maybe is * -> *; binary type constructors like Either have (curried) kind * -> * -> *, and so on. You can view types like Maybe and Either as type-level functions: they take one or more types, and return a type.

A function is higher-order if it has an order greater than 1, where the order is (informally) the nesting depth, to the left, of function arrows:

• Order 0: 1 :: Int
• Order 1: chr :: Int -> Char
• Order 2: fix :: (a -> a) -> a, map :: (a -> b) -> [a] -> [b]
• Order 3: ((A -> B) -> C) -> D
• Order 4: (((A -> B) -> C) -> D) -> E

So, long story short, a higher-kinded type is just a type-level higher-order function which abstracts over type constructors:

• Order 0: Int :: *
• Order 1: Maybe :: * -> *
• Order 2: Functor :: (* -> *) -> Constraint—higher-kinded: converts unary type constructors to typeclass constraints