Higher types in Scala
I read functional programming in the Scala book and the Monoids chapter, they talk about the Monoid interface, which looks like this:
trait Monoid[A] {
def op(a1: A, a2: A): A
def zero: A
}
They later define specific Monoid instances by extending this interface. For example,
val intMonoid = new Monoid[Int] {
...
}
val listMonoid = new Monoid[List[Int]] {
...
}
In a few more pages that I read in this chapter 10, I come across "higher types", which, according to the book, represent any type, which itself is a type that can take other types.
trait Foldable[F[_]] {
...
...
}
Thus, the Foldable property corresponds to a higher type book. My question is that Monoid [A] also fits the definition of "higher grade" for me, since it can accept a list [A]. Do I understand correctly? If not, what makes higher-grade types more native to Scala?
Edit: So the unary type constructor takes an argument and creates a type. What about this case?
def listMonoid[A] = new Monoid[List[A]] {
...
...
}
So my listMonoid function is HKT?
source to share
Some terminology:
- correct type (e.g. Int)
- first-order type (for example, List [_]); we could also say first order view
- a type with a higher genus (for example, Monad [M [_])
When you said
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 a trait Monoid
with some type A, which can (as you have noticed) be a simple type, also known as a correct type (for example Int
) or a parameterized type (for example List[Int]
, or even List[Set[Map[Int, Int]]
). This makes it Monoid
a first-order type. You can also say that it is a unary type constructor - it takes one type to get the final type.
Unlike Monoid, some abstractions (like Monad) must be parameterized by the type constructor. Int doesn't work anymore. It must be "some type that another type can produce". An abstraction parameterized by a type constructor (that is, parameterized by a "first-order type") is a higher-genus 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)
Thus, Monad
parameterized by a first-order type (unary type constructor), making itself Monad
a higher-genus type.
Note that Monad
it doesn't really care about the "inner type" itself at the class level, as it will be defined by the op
and methods zero
. You can also say that you need to specify trait Monad[M[A]]
and "fix" the type A at the point of the class definition ListMonad
(for example, fix it to Int), but then you lose flexibility (then yours ListMonad
can only Create and link List[Int]
and you need another class, say for List[String]
) ...
This is in contrast to the monoid, which is not a higher genus type; it doesn't need a type constructor to create a type. If you had to, then you would never have, say Monoid[Int]
, because Int is not a type constructor.
Note also how I said that Monad needs a unary type constructor, that is, it only accepts one type (as opposed to, for example, Map, which takes two). Type constructors are often denoted with asterisks and arrows:
- a first-order unary type constructor is this
* → *
(it takes one type and creates a final type like Set) - first-order
* → * → *
binary type constructor : (binary type constructor, it takes two types to create the final type, like Map) - a unary type with a higher genus
(* → *) → *
(one unary type constructor, like Monad, is required to create the final type)
etc.
Thus, a first order type takes a simple / concrete / correct type and creates a final type, while a higher genus type goes one level up; the final type requires a first order type.
EDIT:
Answering your question in the "edit" part: OK, I think I know what is confusing you. listMonoid
is not a type, so it cannot be of a higher genus. This is the method. Monad[List[Int]]
is a fully legal type. Monad[F[A]]
also fully resolved. However, it Monad
is itself a higher order type.
Let me draw a parallel with functions. If you have a function foo(x: Int)
, then function calls such as foo(42)
or foo(someIntegerValue)
lead to specific values. This is an analogue of Monad[List[Int]]
and Monad[F[A]]
. However, foo
it is itself a function, just as it Monad
is itself a type constructor.
If it foo
takes a simple value (not a function), it is a first-order function; if it takes or returns a function, then it is a higher order function. It's the same with type constructors. If it takes a simple type, then it is a first-order type constructor. Example List
. If another type constructor is required, it is a higher-order type constructor (also known as a higher-genus type). Example Monad
.
Don't mix legal types with type constructors. It makes sense to consider whether the function is foo
higher order or not; it depends on its arguments and the type of the return value. But there is no point in thinking whether it is of foo(42)
a higher order or not; it is not a function, but a function app that leads to a value. Monad[List[Int]]
is not a type constructor, but an application of a type List
constructor to a type constructor Monad
(which has a higher order). Likewise, it is Monoid[List[Int]]
not a type constant, but an application of a type List[Int]
to a type constructorMonoid
(which is first order). Higher-order type constructors are called HKT. It doesn't make sense to talk about HKT and point to a specific allowed type (which was created as a result of using some type constructor).
source to share