Distinguish First-order type and Type Constructors

While going through Scala Specification, Topic 3 about Types, I came across this > "We distinguish between first-order types and type constructors, which take type parameters and yield types."
With this my assumption is First-order types are parameterized types that takes only one type to be applied and become concrete. ex:
List[A] that can take only one argument i.e. Int and become concrete type List[Int], while Type constructors can be of higher order(Higher-kinded Types) like Container[] that can take a List as a Parameter and can be used like:
trait Traversable[Container[
], T]
new Traversable(List, Int) that is going to create a List[Int] that is of Traversable type.

I would like to clarify if my assumption is right, also would like to know more about this specific term “first-order types” as this is discussed in Specification but nowhere it’s clear. The scope of it. Tried googling the same to get legitimate source to understand but couldn’t.

In the context of the Scala specification, by first-order types they mean all types that can describe a value or a method. So if val x: X = ??? is valid then X is a first-order type. Or if X is the type of a method it’s also first-order, but that’s a special case. Type constructors are types that take one or more types as parameters. If you apply the type constructor to type arguments you get a first-order type.

So List is a type constructor. List[Int] is a first-order type. Monad (defined as trait Monad[F[_]]) is a type constructor. Monad[List] is a first-order type.
val x: List = ??? is not valid, neither is val x: Monad = ???, but val x: List[Int] = ??? and val x: Monad[List] = ??? do compile.

Be careful though: other sources might use the term “first-order type” in a different way. This is just what is meant by it in the Scala specification.

Note the nomenclature changed to use the term proper type

We distinguish between proper types and type constructors, which take type parameters and yield types.

by Replace “first-order types” with “proper types” #8530

Refering to non type constructors as “first-order types” I think might
be why there’s confusion as to what a “higher-kinded type” is. So I
propose they’re referred to as “proper types” instead.

When unsure we can use :kind command in REPL, for example,

scala> :kind -v Function3[Int, Tuple2[Double, List[Int]], Char, Future[Either[String, Int]]]
(Int, (Double, List[Int]), Char) => scala.concurrent.Future[Either[String,Int]]'s kind is A
*
This is a proper type.

scala> :kind -v cats.Functor
cats.Functor's kind is X[F[A]]
(* -> *) -> *
This is a type constructor that takes type constructor(s): a higher-kinded type.

1 Like