What's the difference between "Generic type" and "Higher-kinded type"?

Question

I found myself really can't understand the difference between "Generic type" and "higher-kinded type".

Scala code:

trait Box[T]

I defined a trait whose name is Box, which is a type constructor that accepts a parameter type T. (Is this sentence correct?)

Can I also say:

1. Box is a generic type
2. Box is a higher-kinded type
3. None of above is correct

When I discuss the code with my colleagues, I often struggle between the word "generic" and "higher-kinde" to express it.

Answer 1

It's probably too late to answer now, and you probably know the difference by now, but I'm going to answer just to offer an alternate perspective, since I'm not so sure that what Greg says is right. Generics is more general than higher kinded types. Lots of languages, such as Java and C# have generics, but few have higher-kinded types.

To answer your specific question, yes, Box is a type constructor with a type parameter T. You can also say that it is a generic type, although it is not a higher kinded type. Below is a broader answer.

This is the Wikipedia definition of generic programming:

Generic programming is a style of computer programming in which algorithms are written in terms of types to-be-specified-later that are then instantiated when needed for specific types provided as parameters. This approach, pioneered by ML in 1973,1 permits writing common functions or types that differ only in the set of types on which they operate when used, thus reducing duplication.

Let's say you define Box like this. It holds an element of some type, and has a few special methods. It also defines a map function, something like Iterable and Option, so you can take a box holding an integer and turn it into a box holding a string, without losing all those special methods that Box has.

case class Box(elem: Any) {
  ..some special methods
  def map(f: Any => Any): Box = Box(f(elem))
}

val boxedNum: Box = Box(1)
val extractedNum: Int = boxedString.elem.asInstanceOf[Int]
val boxedString: Box = boxedNum.map(_.toString)
val extractedString: String = boxedString.elem.asInstanceOf[String]

If Box is defined like this, your code would get really ugly because of all the calls to asInstanceOf, but more importantly, it's not typesafe, because everything is an Any.

This is where generics can be useful. Let's say we define Box like this instead:

case class Box[A](elem: A) {
  def map[B](f: A => B): Box[B] = Box(f(elem))
}

Then we can use our map function for all kinds of stuff, like changing the object inside the Box while still making sure it's inside a Box. Here, there's no need for asInstanceOf since the compiler knows the type of your Boxes and what they hold (even the type annotations and type arguments are not necessary).

val boxedNum: Box[Int] = Box(1)
val extractedNum: Int = boxedNum.elem
val boxedString: Box[String] = boxedNum.map[String](_.toString)
val extractedString: String = boxedString.elem

Generics basically lets you abstract over different types, letting you use Box[Int] and Box[String] as different types even though you only have to create one Box class.

---

However, let's say that you don't have control over this Box class, and it's defined merely as

case class Box[A](elem: A) {
  //some special methods, but no map function
}

Let's say this API you're using also defines its own Option and List classes (both accepting a single type parameter representing the type of the elements). Now you want to be able to map over all these types, but since you can't modify them yourself, you'll have to define an implicit class to create an extension method for them. Let's add an implicit class Mappable for the extension method and a typeclass Mapper.

trait Mapper[C[_]] {
  def map[A, B](context: C[A])(f: A => B): C[B]
}

implicit class Mappable[C[_], A](context: C[A])(implicit mapper: Mapper[C]) {
  def map[B](f: A => B): C[B] = mapper.map(context)(f)
}

You could define implicit Mappers like so

implicit object BoxMapper extends Mapper[Box] {
  def map[B](box: Box[A])(f: A => B): Box[B] = Box(f(box.elem)) 
}
implicit object OptionMapper extends Mapper[Option] {
  def map[B](opt: Option[A])(f: A => B): Option[B] = ???
}
implicit object ListMapper extends Mapper[List] {
  def map[B](list: List[A])(f: A => B): List[B] = ???
}
//and so on

and use it as if Box, Option, List, etc. have always had map methods.

Here, Mappable and Mapper are higher-kinded types, whereas Box, Option, and List are first-order types. All of them are generic types and type constructors. Int and String, however, are proper types. Here are their kinds, (kinds are to types as types are to values).

//To check the kind of a type, you can use :kind in the REPL
Kind of Int and String: *
Kind of Box, Option, and List: * -> *
Kind of Mappable and Mapper: (* -> *) -> *

Type constructors are somewhat analogous to functions (which are sometimes called value constructors). A proper type (kind *) is analogous to a simple value. It's a concrete type that you can use for return types, as the types of your variables, etc. You can just directly say val x: Int without passing Int any type parameters.

A first-order type (kind * -> *) is like a function that looks like Any => Any. Instead of taking a value and giving you a value, it takes a type and gives you another type. You can't use first-order types directly (val x: List won't work) without giving them type parameters (val x: List[Int] works). This is what generics does - it lets you abstract over types and create new types (the JVM just erases that information at runtime, but languages like C++ literally generate new classes and functions). The type parameter C in Mapper is also of this kind. The underscore type parameter (you could also use something else, like x) lets the compiler know that C is of kind * -> *.

A higher-kinded type/higher-order type is like a higher-order function - it takes another type constructor as a parameter. You can't use a Mapper[Int] above, because C is supposed to be of kind * -> * (so that you can do C[A] and C[B]), whereas Int is merely *. It's only in languages like Scala and Haskell with higher-kinded types that you can create types like Mapper above and other things beyond languages with more limited type systems, like Java.

This answer (and others) on a similar question may also help.

Edit: I've stolen this very helpful image from that same answer: