The naming of TConstructor is a bit of a stretch. It both names a type constructor and applies it to zero or more type parameters. A more traditional encoding would be:
sealed abstract class Type
case class TConstructor(name : String) extends Type
case class TApply(t1 : Type, t2 : Type) extends Type
case class TVariable(index : Int) extends Type
Array<Int> would be encoded as
However, with the
<> syntax for generics that’s traditional in mainstream languages, it becomes a bit awkward when you have a type like
Map<Int, String> and you need to encode that as
TApply(TApply(TConstructor("Map"), TConstructor("Int")), TConstructor("Int")). That would more naturally map back to
Map<Int><String> — but type constructors are not usually curried in mainstream languages. They are in Haskell, though!
One downside of the representation chosen in the article is that it doesn’t extend naturally to higher kinded types — that is, where type variables may stand for type constructors that aren’t fully applied.