Kinds of types in Scala, part 1: types, what are they? - Mateusz Kubuszok

At a time though, Bertrand Russell proposed another way to avoid the paradox:

• each term should be assigned a type. It is usually denoted with a colon: 2 : nat
• if we wanted to define a function we would define on which types it operates: e.g. double: nat → nat

f:X→Y read as: f is a function from X (domain) to Y (codomain).

• terms can be converted using explicitly defined rules: e.g. 2+2↠4 means that 2+2 reduces to 4, so it has the same type.

In Scala

val a: A
def f(a: A): B

When it comes to Scala syntax, we won’t talk about a judgment. Instead, we would talk about a type ascription. Notation for function type also comes from the type theory: 'double:int→int' becomes:

val double: Int => Int

Scala has also the notion of the top and bottom types. The top type - a type we don’t have any assertions about, which contains any other type - is 'Any'. In Java, the closest thing would be an 'Object', except it is not a supertype for primitives. Scala’s 'Any' is a supertype for both objects ('AnyRef') and primitives ('AnyVal'). When we see 'Any' as an inferred type, it usually means we messed up and combined two unrelated types.

The bottom type - a type which is a subtype of all others, and has no citizen - in Scala is 'Nothing'. We cannot construct a value of type'Nothing', so it often appears as a parameter of empty containers or functions that can only throw.

(Quite often I see that 'Null' is mentioned as another bottom type in Scala together with 'Nothing'. It is a type extending everything that is an 'Object' on JVM. So it is kind of like 'Nothing' without primitives, 'Unit/void', and functions that only throws).

Also, a word about functions. In Scala we make a distinction between a function and a method. A 'function type' is a value, which can be called:

val double: Int => Int = x => x * 2

A method, on the other hand, is not a value. It cannot be assigned, or directly passed, though via a process called eta-expansion a method can be turned into a function.

def double(x: Int): Int = x * 2
// val y = def double(x: Int): Int = x * 2 - error!
val y = { def double(x: Int): Int = x * 2 } // Unit
// however
val z: Int => Int = double _ // works!

Less accurate, but simpler version: a function is an instance of some 'Function0', 'Function1', …, 'Function22' trait, while a method is something bound to a JVM object. We make a distinction because authors of Scala haven’t solved the issue in a more elegant way.

Oh, and one more thing. With a method, you can declare a argument as 'implicit'. You cannot do that with function. For now. It will be possible with implicit function types in Dotty.

Type inference and Least Upper Bounds

This hierarchy of types is quite important when it comes to type inference. We expect it to provide us with the most concrete type possible, while it has to comply to any type restriction it was imposed for a given case. Let’s take a look at a few cases:

val s = "test"

def a(b: Boolean) = if (b) Some(12) else None

Here, the returned value is one of two types 'Some[Int]' or 'None.type' (a type of 'None' companion object). How to decide the common type for these two?

Let’s build a graph of a type hierarchy:

       Any
        |
      AnyRef
        |
   +----+------+  
   |           |
 Equals  java.io.Serializable
   |           |
Product   Serializable  
   |           |
   +----+------+
        |
     Option[T]
        |
  +-----+-----+          
  |           |
Some[T]    None.type

Algebraic Data Types

When we think of types as a sets, there are 2 special constructions, that help us build new sets from existing ones, which complement each other. One is a Cartesian product and the other is a disjoint union/disjoint set sum.

Let’s start with a Cartesian product. We can define it as a generalization of an ordered pair. A set of ordered pairs (A,B) would be a set of values (a,b), such as a∈A,b∈B, which we could distinct by its position inside a brackets. More formally, we could define an ordered pair as (Kuratowski’s definition):

(a,b)={{a},{a,b}}

Such definition help us indicate the order using construction that itself has no distinction of order (that is a set).

Cartesian product generalizes the idea. It an operator which takes 2 sets and creates a set of tuples for them:

A×B={(a,b):a∈A,b∈B}

{x:p(x)} is a set builder notation meaning: a set made of elements xx for which a predicate p(x) is true

Such definition is not associative ((A×B)×C≠A×(B×C), which we can easily check:

((1,2),3)={{{{1},{1,2}}},{{{1},{1,2}},3}}

(1,(2,3))={{1},{1,{{2},{2,3}}}}

type IntTwice = (Int, Int)
case class TwoInts(first: Int, second: Int)
type IntList = List[Int]
// all of the above are products

('IntList' is a type alias, another name for existing type. We could use 'List[Int]' instead of 'IntList' and it would make no difference to Scala).

The other construct - a disjoint union, sum type or coproduct - a is sum of finite number of sets, where no two sets have a non-empty intersection. Types are also tagged, that is we can always say from each subset originated any value of the union.

Scala 2.x doesn’t allow to actually build up an union from already existing types. If we want to let compiler know that types should form a coproduct, we need to use a sealed hierarchy:

sealed trait Either[+A, +B] {}
case class Left[+A, +B](a: A) extends Either[A, B]
case class Right[+A, +B](b: B) extends Either[A, B]

sealed trait Option[+A] {}
case class Some[A](value: A) extends Option[A]
case object None extends Option[Nothing]

The 'sealed' keyword makes sure that no new subtype of said class can be created outside the current file, and so compiler will always know all types that directly inherit the trait (and form a disjoint union). This allows pattern matching to be exhaustive: compiler can tell us that we didn’t matched all components of the union.

Dotty will introduce the union types, which will let us build an union out of already existing types.

def f(intOrString: Int | String) = intOrString {
  case i: Int    => ...
  case s: String => ...
}

Product types and sum types together are known as algebraic data types. They are the foundation the data modeling in functional programming build upon.

They also allow us to use generic programming in Scala with libraries like shapeless.

Compound and intersection types

trait Str { def str: String }
trait Count { def count: Int }

def repeat(cd: Str with Count): String =
  Iterator.fill(cd.count)(cd.str).mkString

repeat(new Str with Count {
  val str = "test"
  val count = 3
})
// "testtesttest"

It follows the mathematical definition exactly:

x∈A∩B⟺x∈A∧x∈B⟺x∈B∧x∈A⟺x∈B∩A

which mean that the order of composing type using 'with' does not matter.

val sc: Str with Count
val ca: Count with Str
def repeat(sc) // works as expected
def repeat(ca) // also works!

Well, at least when it comes to types. Since we can compose types this way we have to face a diamond problem sooner or later.

trait A { def value = 10 }
trait B extends A { override def value = super.value * 2 }
trait C extends A { override def value = super.value + 2 }
(new B with C {}).value // ???
(new C with B {}).value // ???

How would Scala deal with such cases? The answer is a trait linearization:

trait X extends A with B with C

is the same as

trait AnonymousB extends A {
  // B overrides A
  override def value = super.value * 2
}
trait AnonymousC extends AnonymousB {
  // C overrides AnonymousB
  override def value = super.value + 2
}
trait X extends AnonymousC

(implementation wise, types 'B' and 'C' are not lost). If we switch the order:

trait Y extends A with C with B

then it is as if we

trait AnonymousC extends A {
  // C overrides A
  override def value = super.value + 2
}
trait AnonymousB extends AnonymousC {
  // C overrides AnonymousB
  override def value = super.value * 2
}
trait Y extends AnonymousC

It should be obvious now, that

(new B with C {}).value // (10 * 2) + 2 = 22 
(new C with B {}).value // (20 + 2) * 2 = 24

In Dotty 'intersection types' will be denotes using '&'. Documentation claims that it will differ from 'with' in a way, that Dotty want to guarantee, that there will be no difference between 'A & B' and 'B & A' (operator is commutative). Currently, while 'A with B' can be used in place of 'B with A' and it just works., their behavior might be different due to change of order in trait linearization. Dotty will also handle parametric types intersection and intersection of properties types ('List[A] & List[B] = List[A & B]'). Because 'with' has no such guarantees we call types created with it compound types instead.

Classes

Because class does not has to be set, we can talk e.g. about class of all sets.

{x:isSet(x)}

This one is special. In lambda calculus, there are no constants, no nullary functions, and no multi-parameter functions. Everything is a single argument function returning another single argument function (therefore currying is the only way of achieving function with arity ≥≥ 1).

Similarly, in category theory, each arrow (function abstracted away from its body) goes from one object to one object (function domains/codomains abstracted away from specific values).

In such situation, we would have to implement somehow functions returning no (meaningful) value as well as functions taking no parameters (nullary). Category theory names such irrelevant garbage input an initial object or void. It assumes that for every object there is you can create an arrow from void to the object (for every type there is a nullary function returning a value of this type). Since you never have the need to actually pass any value of void type (it won’t be used anyway), the set might be pretty much empty, and an actual implementation can work around it (category theory don’t care about the values, remember?). Thus the name void.

Similarly, there is also a final object or unit, for each object there is an arrow from an object to unit (for every type there is function that could be feed with values of this type and don’t return anything useful). If it only serves the purpose of being returned, we don’t attribute it with anything meaningful. No matter how many values of this type exists, we cannot tell them apart. For us, the unit might be as well be a singleton. Thus the name unit.

While creators of Scala didn’t see a point in making void an actual type (and making people confuse it with Java’s void), they did want to make sure that every function returns something. That something is '()', the sole citizen of an 'Unit' type.

Summary

We talked a bit about what are (concrete) types, how they are represented in Scala, and we learned a thing or two about type theory and some minimum about categories

In next post, we’ll see what are parametric types, type constructors and what constraints we can put on parameters to make the type system our friend.'

This article was written by Mateusz Kubuszok and posted originally on kubuszok.com