From Type to Kind Projector

Mateusz Kubuszok

Introduction to Types

What is a Type?

Intuitively

A collection of values

types

Example

// type annotation

val i: Int    = 0   // value i = 0 is of type Int
val s: String = "a" // value s = "a" is of type String

def double(x: Int): Int = x * 2

// type ascription


0 : Int // compiles because it is true
"": Int // fails to compile

Subtype & Supertype

subtype

Subtype & Supertype

\[(Member <: User) \\ \Updownarrow \\ \forall_a (a : Member \implies a : User)\]

Subtype & Supertype

trait User
class Member extends User
class Admin extends User

Subtype & Supertype

subtype 2

Subtype & Supertype

class User
class Admin extends User

Least Upper Bound and Type Inference

Example

val i: Int
val x = if (i >= 0) Some(i) // Some[Int]
        else None           // None
// what is the type of x?

Example Type Hierarchy

hierarchy
hierarchy 2

Types of Some(i)

hierarchy some

Types of None

hierarchy none

Common part

hierarchy option

Least Upper Bound

Least Upper Bound of a - the least type T for which judgement a : T is provable to be true

Type Inference - finding the LUB of a value

Example

val i: Int
val x = if (i >= 0) Some(i) // Some[Int]
        else None           // None
// x: Option[Int]

ADT

ADT is either a product or coproduct type. :)

But what are product and coproduct types?

Tuple

A tuple or an ordered pair, is a collection of two elements, where we select one of them as the first.

In set theory we can define them as:

\[(a, b) = \{\{a\}, \{a,b\}\}\]

Cartesian Product of 2

\[A \times B = \{ (a, b): a \in A \land b \in B \}\]

n-tuple

\[(a, b, c) = (a, (b, c)) \\ (a, b, c, d) = (a, (b, (c, d))) \\ ...\]

Cartesian Product of n

Generalization of Cartesian product:

\[A \times B \times C = \{ (a, b, c): a \in A \land b \in B \land c \in C \} \\ A \times B \times C = A \times (B \times C) \\ A \times B \times C \times D = A \times (B \times (C \times D)) \\ ...\]

Product types

type X = (String, Int, Double)
type Y = Tuple3[String, Int, Double]
case class Z(s: String, i: Int, d: Double)
class Z2(val s: String, val i: Int, val d: Double)

import shapeless._
String :: Int :: Double :: HNil

Disjoint union

\[X = Y|Z \iff (x : X \implies x : Y \veebar x : Z)\]

Disjoint union

sealed trait Credentials

final case class LoginPassword(
    login: String,
    password: String
) extends Credentials

final case class AccessToken(
    token: String
) extends Credentials

Union types

\[X = Y|Z \iff (x : X \implies x : Y \lor x : Z)\]

Union types

type My = String | Int

Compound types

In set theory we have set intersection.

What do we have in Scala type system?

Compound 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
})

Compound types

\[x \in A \cap B \\ \Updownarrow \\ x \in A \land x \in B \iff x \in B \land x \in A \\ \Updownarrow \\ x \in B \cap A\]

Compound types

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

Compound types

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 // ???

Compound types

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

Intersection types

\[X = Y&Z \iff (x : X \implies x : Y \land x : Z)\]

Intersection types

type My = String & Int

Classes

Mathematically:

A class is such group of objects for which some predicate (an indicator function) returns true.

Programming:

A recipe for objects + contracts. Instances of that class can be a type.

Unit

(): Unit

Type Constructors

If we have a concrete type - e.g. String - we know it is a set of values.

What about List?

Types and Sets - reminder

  • type - e.g. Int - set of values - e.g. 1, 2, 0, -5, …​

  • function - e.g. Int ⇒ Int - set of pairs (Int, Int), where first value doesn’t repeat - e.g. (1,1,), (2,4), (3,9), …​

  • we can make a pair of sets (types),

  • function can take set (type) as an argument and return set (type) as a value

Types and Sets - reminder

type constructor

Types and Sets - reminder

// [A] declares type parameter A
class Wrapper[A](value: A)

val wrapped1 = new Wrapper[Int](1)
// Wrapper[Int] - Int passed explicitly

val wrapped2 = new Wrapper(2)
// Wrapper[Int] - Int inferred

Examples: Option[A], List[A], Either[L, R].

Summary

  • a type is a set of values

  • a subset, a product set, a set sum and intersection translates to a subtype, a product type, a sum type and an compound/intersection types

  • a class is a type

  • unit exist to avoid special cases

  • on mathematical level a parametric type is a function from type to type

All you need to know about types in Scala

What is a kind?

A type of a type :)

Type constraints

sealed trait User { val id: Int }
case class Member(id: Int, name: String) extends User
case class Admin(id: Int, accss: Set[String]) extends User

Map[id, user] - approach 1

def byId(users: Set[User]): Map[Int, User] =
  users.map { u => u.id -> u }.toMap

Map[id, user] - approach 2

def byId[U](users: Set[U])(getId: U => Int): Map[Int, U] =
  users.map { u => getId(u) -> u }.toMap

Upper Bound

sealed trait User { val id: Int }
case class Member(id: Int, name: String) extends User
case class Admin(id: Int, accss: Set[String]) extends User

Map[id, user] - approach 1

def byId[U <: User](users: Set[U]): Map[Int, U] =
  users.map { u => u.id -> u }.toMap

Map[id, user] - approach 2

byId(users: Set[Member]) // Map[Int, Member]
byId(users: Set[Admin]) // Map[Int, Admin]

Lower Bound

def recover[E, A, B >: A](
    either: Either[E, A])(f: E => B): Either[E, B] =
  either match {
    case Left(e)  => Right(f(e))
    case Right(a) => Right(a)
  }
recover[String, Admin, User](err: Either[String, Admin]) {
    _ =>
  fallback: Member
}
// Either[String, User]

Generalized type constraints

def upcast[A, B](set: Set[A])(
  implicit ev: A <:< B // A is a subclass of B
): Set[B] = set.map(ev(_))

upcast[Member, User](Set(m: Member)) // Set[User]
def update[A, B](set: Set[A])(f: A => B)(
  implicit ev: A =:= B // types are equal
): Set[B] = set.map(f)

val members: Set[Member]

update[Member, Member](members)(identity) // ok
update[Member, User](members) { member =>
  member: User
} // compilation error!

Generalized type constraints

  • <%< - already removed from Scala, meant A is a suptype is is implicitly convertible to B,

  • =:!= - types differ - provided by Shapeless

Type class syntax

trait X[F[_]]

def needX[F[_] : X] = ??? // is equal to
def needX[F[_]](implicit xf: X[F]) = ???

Variance

Mutability and Subtyping

String[] strings = new String[3];
strings[0] = "1";
strings[1] = "2"; // ok so far

Object[] objects = strings; // we can do that as well
objects[2] = (Integer) 3;
// java.lang.ArrayStoreException: java.lang.Integer
List<String> strings = new ArrayList<String>();
strings.add(0, "1");
strings.add(1, "2");

List<Object> objects = strings; // compilation error

Invariance

Situation where:

\[A <: B \\ \neg F[A] <: F[B] \land \neg F[B] <: F[A]\]

is called invariance.

Immutable containers

sealed trait Option[T] {}
case class Some[T](value: T) extends Option[T]
case class None[T]() extends Option[T]
class A
class B extends A

val o: Option[B] = Some(new B)

def withOptA(opt: Option[A]) = ???

withOptA(o) // doesn't work

None[A]() != None[B]() // doesn't make sense

Covariance

Situation where:

\[A <: B \implies F[A] <: F[B]\]

is called covariance.

Covariance

sealed trait Option[+T] {} // + makes the difference
case class Some[+T](value: T) extends Option[T]
object None extends Option[Nothing]
class A
class B extends A

val o: Option[B] = Some(new B)

def withOptA(opt: Option[A]) = ???

withOptA(o) // compiles

(None: Option[A]) == (None: Option[B]) // true

Subscribers

trait Subscriber[A] {

  def apply(value: A): Unit
}
class A
class B extends A

val subscriberA: Subscriber[A]

List(new B).foreach(subscriberA) // compilation fails!

Contravariance

Situation where:

\[A <: B \implies F[B] <: F[A]\]

is called contravariance.

Contravariance

trait Subscriber[-A] { // - makes the difference

  def apply(value: A): Unit
}
class A
class B extends A

val subscriberA: Subscriber[A]

List(new B).foreach(subscriberA) // works!

Variances

Variances - invariance, covariance, contravariance - is related to type parameter, not the whole type.

trait Function1[-A, +B] {

  def apply(arg: A): B
}
val function: Function1[A, B]

def b2b(f: Function[B, B]): Unit
def a2a(f: Function[A, A]): Unit

b2b(function) // accepting more generic argument is ok
a2a(function) // returning more specific result is ok

Existential types

def count[T](seqs: Seq[T]*): Int = seqs.map(_.size).sum
count(Seq(1,2,3), Seq("test")) // 4

Existential types

Universal type

\[\forall_T count: Seq_{Seq_T} \rightarrow int\]

Existential type

\[seq: Seq_? \iff \exists_{T} seq: Seq_T \\ count: Seq_{Seq_?} \rightarrow int\]

Existential types

def count(seqs: Seq[_]*): Int // syntactic sugar for
def count(seqs: (Seq[T] forSome { type T })*): Int

Java also has them!

int count(java.util.List<?>... seqs) {
    return Arrays.stream(seqs)
        .mapToInt(seq -> seq.size())
        .sum();
}

Structural types

type User = { name: string, surname: string }

Structural types

type User = {
  val name: String
  val surname: String
}
case class Somebody(name: String, surname: String)

def needUser(user: User): Unit

needUser(Somebody("test", "test")) // works!

Refined types

trait X { val x: String }
type Y = { val y: Int }
val z: X with Y = new X { val x = "test"; val y = 0 }
new X { val x = "test"; val y = 0 }
// AnyRef with X{val y: Int}

Path-dependent types

case class Card(color: String, value: String)
case class Player(name: String)
class Game {
  def getPlayers: Set[Players] = ???
  def getCards: Set[Cards] = ???
  def playerPlayCard(player: Player, card: Card): Unit = ???
}
val game1: Game
val game2: Game
game1.playerPlayCard(game2.getPlayers.head,
                     game2.getCards.head) // oops!

Path-dependent types

class Game {
  case class Card(color: String, value: String)
  case class Player(name: String)

  def getPlayers: Set[this.Player] = ???
  def getCards: Set[this.Card] = ???
  def playerPlayCard(player: this.Player,
                     card: this.Card): Unit = ???
}
val game1 = new Game
val game2 = new Game
game1.getPlayers // Set[game1.Player]
game2.getPlayers // Set[game2.Player]
game1.playerPlayCard(game2.getPlayers.head,
                     game2.getCards.head) // fails!

Path-dependent types

class X {
  type Y = String
  val y: Y = "y"
}

val x1 = new X
val x2 = new X
def y(x: X)(y: x.Y): Unit = ()

y(x1)(x2.y) // no complaints: x1.Y = String = x2.Y

Path-dependent types

trait X {
  type Y = String
  val y: Y = "y"
}

class X2 extends X

val x1 = new X2
val x2 = new X2

y(x1)(x2.y) // fails!

Path-dependent types

trait X {
  type Y
  val y: Y
}

val x1 = new X {
  type Y = String
  val y: Y = "y"
}
val x2 = new X {
  type Y = Int
  val y: Y = 1
}

Getting rid of path-dependency

def takeAnyPlayer(p: Game#Player): Unit

Kind projectors

type WithFallback[A] = Either[String, A]
def fallbackOnError[A: WithFallback](
    value: Either[String, A]
): Either[String, A] = value match {
  case Left(_)      => implicitly[Either[String, A]]
  case Right(value) => Right(value)
}

Kind projectors

type WithFallback = { type T[A] = Either[String, A] }
def fallbackOnError[A: WithFallback#T](
    value: Either[String, A]
): Either[String, A] = ...

Kind projectors

def fallbackOnError[A: ({ type T[A] = Either[String, A] })#T](
    value: Either[String, A]
): Either[String, A]

Kind projectors

def fallbackOnError[A: Either[String, ?]](
    value: Either[String, A]
): Either[String, A][A]
[T] => Either[String, T]

-Ypartial-unification

def foo[F[_], A](fa: F[A]) = fa.toString

foo[Function1[Int], Int](x => x * 2) // error!
// build.sbt
scalacOptions += "-Ypartial-unification"

Summary

  • we have a quite fine grained control over type parameters and their usage

  • Scala does it best to preserve the type information even if we don’t need it (now)

  • you (and surely some library authors) will use path-dependent types to ensure that some values will be passed only in the right context

More info

Questions?

Thanks!