Higher Kinded Types in Scala

Question

I'm reading through the Functional Programming in Scala book and in the Monoids chapter, they talk about a Monoid interface that looks like this:

trait Monoid[A] {
 def op(a1: A, a2: A): A
 def zero: A
}

Later on, they define specific Monoid instances by extending this interface. For example.,

val intMonoid = new Monoid[Int] {
  ...
}

val listMonoid = new Monoid[List[Int]] {
  ...
}

A couple more pages that I read through this chapter 10, I come across 'higher kinded types' which according to the book is any type that it self is a type that can take other types.

trait Foldable[F[_]] {
 ...
 ...
}

So the trait Foldable is according to the book a higher kinded type. My question is, the Monoid[A] to me is also fits the 'higher kinded type' definition as it can take a List[A]. Is my understanding correct? If not what makes higher kinded types a higher kinded type in Scala?

Edit: So a unary type constructor takes an argument and produces a type. Now what about this case here?

def listMonoid[A] = new Monoid[List[A]] {
  ...
  ...
}

So is my listMonoid function a HKT?

Answer 1

Some terminology:

• proper type (e.g. Int)
• first-order type (e.g. List[_]); we could also say first-order kind
• higher-kinded type (e.g. Monad[M[_])

When you say

trait Monoid[A] {
  def op(a1: A, a2: A): A
  def zero: A
}

val listMonoid = new Monoid[List[Int]] {
  def op(l: List[Int], l2: List[Int]) =  List(1,2)
  def zero = List(1,2)
}

you are parameterizing the Monoid trait with some type A, which can (as you noticed) be a simple type, also know as proper type (e.g. Int) or a parameterized type (e.g. List[Int], or even List[Set[Map[Int, Int]]). This makes Monoid a first-order type. We can also say that it's a unary type constructor - it takes one type to produce the final type.

Unlike Monoid, some abstractions (e.g. Monad) need to be parameterized by a type constructor. Int doesn't work any more. It needs to be "some type than can produce another type". Abstraction which is parameterized by a type constructor (that is, parameterized by a "first-order type") is a higher-kinded type. Here's an example:

trait Monad[M[_]] {
  def op[A, B](m: M[A], f: A => M[B]): M[B]
  def zero[A](a: A): M[A]
}

object ListMonad extends Monad[List] {
  def op[A, B](m: List[A], f: A => List[B]) = m.flatMap(f)
  def zero[A](a: A) = List[A](a)
}

val listMonad = ListMonad.zero(42)
val result = ListMonad.op(listMonad, (i: Int) => List(i - 1, i, i + 1))

// result = List(41, 42, 43)

So Monad is parameterized by a first-order type (a unary type constructor), which makes Monad itself a higher-kinded type.

Note how Monad doesn't really care about the "inner type" itself on the class level as it will be defined by the methods op and zero. You could also say trait Monad[M[A]] and "fix" the type A at the point of definition of class ListMonad (e.g. fix it to Int), but then you are losing flexibility (your ListMonad will then only be able to construct and flatMap a List[Int] and you would need a different class for, say, List[String]).

This is different than a Monoid which is not a higher-kinded type; it doesn't need a type constructor to produce a type. If it needed it, then you could never have a, say, Monoid[Int], because Int is not a type constructor.

Note also how I said that Monad needs a unary type constructor, meaning it takes only one type (unlike e.g. Map which takes two). Type constructors are often represented with asterisks and arrows:

• unary first-order type constructor is * -> * (it takes a single type and produces the final type, e.g. Set)
• binary first-order type constructor is * -> * -> * (a binary type constructor, takes two types to produce the final type, e.g. Map)
• unary higher-kinded type is (* -> *) -> * (takes a single unary type constructor to produce the final type, e.g. Monad)

etc.

So, first-order type takes a simple/concrete/proper type and produces the final type, while higher-kinded type goes one level above; it takes a first-order type to produce the final type.

EDIT:

Answering your question in "edit" part: OK I think I know what's confusing you. listMonoid is not a type, so it can't be a higher-kinded type. It's a method. Monad[List[Int]] is a fully resolved type. Monad[F[A]] is also fully resolved. However, Monad itself is a higher order type.

Let me pull the parallel to functions. If you have a function foo(x: Int), then function invocations such foo(42) or foo(someIntegerValue) result in concrete values. These are the analogous to Monad[List[Int]] and Monad[F[A]]. However, foo itself is a function, just like Monad itself is a type constructor.

If foo takes a simple value (not a function), it's a first-order function; if it takes or returns a function, then it's a higher-order function. Same with type constructors. If it takes a simple type, it's a first-order type constructor. Example: List. If it takes another type constructor, it's a higher-order type constructor (also know as higher-kinded type). Example: Monad.

Don't mix resolved types with type constructors. It makes sense to think whether function foo is higher-order or not; this depends on its arguments and return type. But it makes no sense to think whether foo(42) is higher-order or not; this is not a function, but a function application, which results in value. Monad[List[Int]] is not a type constructor, but an application of type constructor List to the type constructor Monad (which is higher-order). Similarly, Monoid[List[Int]] is not a type constrcutor, but an application of type List[Int] to the type constructor Monoid (which is first-order). Type constructors of higher order are called HKT. It doesn't make sense to talk about HKT and point at a concrete resolved type (that was created as a result of application of some type constructor).