GADTs By Use Cases

Welcome. This session will introduce you to a very powerful tool in programming. Whereas most introduction start by presenting its theoretical foundations in a very formal way, we chose to present it via short examples and practical use-cases.

This workshop is made of three parts. The last one presents three of the most valuable use-cases. They are the real big powerful use-cases. But do not go there unprepared! This is the last part for a reason: they rely massively on lessons you will learn in the previous parts. Start First Contact, it will show you, via the simplest examples, the core ideas. Its goal is to open your mind to ways of using types and data you may have never imagined possible. Then go to Easy Useful Use Cases: Relations on Types, for the first real-life challenge. Then you are ready for More Advanced Use Cases.

Be sure to read README, it contains precious tips to ease your journey.

README

In this presentation we will assume that:

  • null does not exists!
  • runtime-reflection does not exist! (i.e. isInstanceOf, getClass, etc)

This presentation considers that these features do not exists at all.

Using these features will never lead to a valid answer.

This presentation expects you to have access to something where you can easily write, compile and run Scala code. The best way to do so is opening a R.E.P.L. session. If you have Scala installed on your system, you can easily start one from the command-line by executing scala:

system-command-line# scala
Welcome to Scala 2.13.1 (OpenJDK 64-Bit Server VM, Java 1.8.0_222).
Type in expressions for evaluation. Or try :help.

scala>

If you don’t have Scala installed, you can use the online-REPL https://scastie.scala-lang.org/ .

Stretching

This section is a brief reminder of some definitions and properties about values and types.

Values and Types?

Values are actual piece of data your program manipulates like the integer 5, the boolean true, the string "Hello World!", the function (x: Double) => x / 7.5, the list List(1,2,3), etc. We often like to classify values into groups. These groups are called types. For example:

  • Int is the group of integer values, i.e. values like 1, -7, 19, etc.
  • Boolean is the group containing exactly the values true and false (no more, no less!).
  • String is the group whose values are "Hello World!", "", "I ❤️ GADTs", etc.
  • Double => Double is the group whose values are functions taking any Double as argument and returning some Double.

To indicate that the value v belongs to the type (group of values) T, we write v : T. In Scala, testing if a value v belongs to a type T is very simple: just type v : T in the REPL:

scala> 5 : Int
res7: Int = 5

If Scala accepts it, then v belongs to T. If Scala complains, it most probably does not :

scala> 5 : String
       ^
       error: type mismatch;
        found   : Int(5)
        required: String

How many types?

Let’s now create some types and some of their values (when possible!).

class OneType
  • Question 1: How many types does the line class OneType defines?

    Solution (click to expand)

    As the name suggests, class OneType defines only one type which is the class OneType.

Let’s now consider:

class OneTypeForEvery[A]
  • Question 2: How many types does the line class OneTypeForEvery[A] defines?

    Solution (click to expand)

    As the name suggests, every concrete type A give rise to a distinct type OneTypeForEvery[A].

    For example, a list of integers is neither a list of booleans, nor a list of strings, nor a list of functions, nor … It means the types List[Int], List[Boolean], List[Int => Int], etc are all distinct types.

    The line class OneTypeForEvery[A] defines a type for every concrete type A. There is an infnity of types A, so an infinity of types OneTypeForEvery[A]. Very much list there is an infinity of sorts of lists.

  • Question 3: Give a value that belongs to both OneTypeForEvery[Int] and OneTypeForEvery[Boolean].

    Remember that null does not exist!

    Solution (click to expand) This is actually impossible. Every concrete type A give rise a distinct type OneTypeForEvery[A] that have no values in common with others types OneTypeForEvery[B] for B ≠ A.

How many values?

Considering the following type:

final abstract class NoValueForThisType
  • Question 1: Give a value belonging to the type NoValueForThisType? How many values belong to NoValueForThisType?

    Hint (click to expand)

    • What is a final class? How does it differ from a normal non-final class?
    • What is an abstract class? How does it differ from a concrete class?

Solution (click to expand)

The class NoValueForThisType is declared abstract. It is then forbidden to create an instance of this class:

  scala> new NoValueForThisType
         ^
         error: class NoValueForThisType is abstract; cannot be instantiated

The only way to create an instance of an abstract class is creating a concrete sub-class. But the keyword final forbids creating such sub-classes:

  scala> class ConcreateSubClass extends NoValueForThisType
                                         ^
         error: illegal inheritance from final class NoValueForThisType

There is no way to create an instance of NoValueForThisType.

Let’s take another example:

sealed trait ExactlyOneValue
case object TheOnlyValue extends ExactlyOneValue
  • Question 2: Give a value belonging to the type ExactlyOneValue?

    Solution (click to expand)

    By definition, TheOnlyValue is a value of type ExactlyOneValue.

  • Question 3: How many values belong to ExactlyOneValue?

    Solution (click to expand)

    Just like above, ExactlyOneValue being a trait is abstract. Being sealed, extending it outside of its defining file is forbidden. So TheOnlyValue is the only value of type ExactlyOneValue.

First Contact

This part presents the core ideas. There are actually only two ideas! What you will find here are stripped down examples to illustrate each of these ideas.

Use Case: Evidence of some property

Let’s define a simple sealed trait:

sealed trait ATrait[A]
case object AValue extends ATrait[Char]
  • Question 1: Give a value of type ATrait[Char].

    Solution (click to expand)

    By definition, AValue is a value of type ATrait[Char].

  • Question 2: Give a value of type ATrait[Double].

    Solution (click to expand)

    There is no way to have an instance of type ATrait[Int]. There is actually no way to have an instance of type ATrait[B] for B ≠ Char because the only possible value is AValue which is of type ATrait[Char].

  • Question 3: What can you conclude about a type A if you have a value ev of type ATrait[A] (i.e. ev: ATrait[A])?

    Solution (click to expand)

    The only possible value is AValue, so ev == AValue. Furthermore AValue is of type ATrait[Char] so A = Char.

  • Question 4: In the REPL, enter the following code

    def f[A](x: A, ev: ATrait[A]): Char =
      x
  • Question 5: Now try pattern matching on ev: ATrait[A]

    def f[A](x: A, ev: ATrait[A]): Char =
      ev match {
        case AValue => x
      }

    Is the pattern-matching exhaustive?

    Solution (click to expand)

    The pattern-matching is exhaustive because the only possible actual value for ev is AValue. Furthermore AValue is of type ATrait[Char] which means ev : ATrait[Char] because ev == AValue. So A = Char and x : Char.

  • Question 6: Call f with x = 'w' : Char.

    Solution (click to expand)

    scala> f[Char]('w', AValue)
    res0: Char = w

  • Question 7: Call f with x = 5.2 : Double.

    Solution (click to expand)

    This is impossible because it would require to give a value ev : ATrait[Int] which does not exist!

    scala> f[Double](5, AValue)
                        ^
              error: type mismatch;
                found   : AValue.type
                required: ATrait[Double]

Remark for people fluent in Scala (click to expand)

Using all the nice features of Scala, the production-ready version of the code above is:

sealed trait IsChar[A]
object IsChar {
  implicit case object Evidence extends IsChar[Char]

  def apply[A](implicit evidence: IsChar[A]): IsChar[A] =
    evidence
}

def f[A: IsChar](x: A): Char =
  IsChar[A] match {
    case IsChar.Evidence => x
  }

Use-Case: The only thing I know is it exists

What would you do if you wanted your codebase to log messages, but you want to be sure your codebase do not rely on any implementation details of the logger so that you can change its implementation without risking breaking the codebase?

Take the following logger type UnknownLogger:

sealed trait UnknownLogger
final case class LogWith[X](logs : X, appendMessage: (X, String) => X) extends UnknownLogger

The first logger we will create stores the logs in a String:

val loggerStr : UnknownLogger =
  LogWith[String]("", (logs: String, message: String) => logs ++ message)

The second logger stores them in a List[String]:

val loggerList : UnknownLogger =
  LogWith[List[String]](Nil, (logs: List[String], message: String) => message :: logs)

The third logger directly print the messages to the standard output:

val loggerStdout : UnknownLogger =
  LogWith[Unit]((), (logs: Unit, message: String) => println(message))

Note that these three loggers all have the same type (i.e. UnknownLogger) but they store the logs using different types X (String, List[String] and Unit).

  • Question 1: Let v be a value of type UnknownLogger. Clearly v has to be an instance of type LogWith[X] for some type X. What can you say about the type X? Can you figure out which type X actually is?

    Remember we refuse to use runtime-reflection! (i.e. isInstanceOf, getClass, etc)

    Solution (click to expand)

    We know almost nothing about X. The only thing we know is there exists at least one value (v.logs) of type X. Appart from that X can be any type.

    Not knowing which type X really is very useful to garantee that the code that will use v : UnknownLogger will not rely on the nature of X. If the code knew X was String for example, it could perform some operations we want to forbid like reversing the list, taking only the nth first characters, etc. By hiding the real type X, we force our codebase to not depend on what X is but to use the provided v.appendMessage. So changing the real implementation of the logger won’t break any code.

  • Question 2: Write the function def log(message: String, v: UnknownLogger): UnknownLogger that uses v.appendMessage to append message to v.logs and returns a new UnknownLogger containing the new logs.

    Remember that in Scala, the following pattern (i.e. ac : AClass[t]) is allowed in match/case expressions:

    final case class AClass[A](value : A)
    
    def f[A](v: AClass[A]): A =
      v match {
        case ac : AClass[t] =>
          // The variable `t` is a type variable
          // The type `t` is equal to `A`
          val r : t = ac.value
          r
      }

    Its main benefit is introducing the type variable t. Type variables work like normal pattern variables except that they represent types instead of values. Having t enable us to help the compiler by giving explicit types (like just above, saying r is of type t).

    Solution (click to expand)

    def log(message: String, v: UnknownLogger): UnknownLogger =
      v match {
        case vx : LogWith[x] => LogWith[x](vx.appendMessage(vx.logs, message), vx.appendMessage)
      }

  • Question 3: Execute log("Hello World", loggerStr) and log("Hello World", loggerList) and log("Hello World", loggerStdout)

    Solution (click to expand)

    scala> log("Hello World", loggerStr)
    res0: UnknownLogger = LogWith(Hello World,$$Lambda$988/1455466014@421ead7e)
    
    scala> log("Hello World", loggerList)
    res1: UnknownLogger = LogWith(List(Hello World),$$Lambda$989/1705282731@655621fd)
    
    scala> log("Hello World", loggerStdout)
    Hello World
    res2: UnknownLogger = LogWith((),$$Lambda$990/1835105031@340c57e0)

Remark for people fluent in Scala (click to expand)

Once again, using all the nice features of Scala, the production-ready version of the code above is:

sealed trait UnknownLogger {
  type LogsType
  val logs : LogsType
  def appendMessage(presentLogs: LogsType, message: String): LogsType
}

object UnknownLogger {

  final case class LogWith[X](logs : X, appendMessage_ : (X, String) => X) extends UnknownLogger {
    type LogsType = X
    def appendMessage(presentLogs: LogsType, message: String): LogsType =
      appendMessage_(presentLogs, message)
  }

  def apply[X](logs: X, appendMessage: (X, String) => X): UnknownLogger =
    LogWith[X](logs, appendMessage)
}

Intermediary Conclusion

GADTs are actually only this: simple sealed trait with some case object (possibly none) and some final case class (possible none too!). In the following parts we will explore some major use cases of GADTs

Easy Useful Use Cases: Relations on Types

One easy but very useful benefit of GADTs is expressing relations about types such that:

  • Is type A equal to type B?
  • Is type A a sub-type of B?

Note that, by definition, a type A is always considered a sub-type of itself (i.e. A <: A), very much like an integer x is also considered lesser-than-or-equal to itself x ≤ x.

Use Case: Witnessing Type Equality

sealed trait EqT[A,B]
final case class Evidence[X]() extends EqT[X,X]
  • Question 1: Give a value of type EqT[Int, Int]

    Solution (click to expand)

    scala> Evidence[Int]() : EqT[Int, Int]
    res0: EqT[Int,Int] = Evidence()

  • Question 2: Give a value of type EqT[String, Int]

    Solution (click to expand)

    The class Evidence is the only concrete sub-class of trait EqT and we cannot create another one because EqT is sealed. So any value v : EqT[A,B] has to be an instance of Evidence[X] for some type X, which is of type EqT[X,X]. Thus there is no way to get a value of type EqT[String, Int]

  • Question 3: Given two (unknown) types A and B. What can you conclude if i give you a value of type EqT[A,B]?

    Solution (click to expand)

    If i give you a value v : EqT[A,B], then you know that v is an instance of Evidence[X] for some type X because the class Evidence is the only concrete sub-class of the sealed trait EqT. Actually Evidence[X] is a sub-type of EqT[X,X]. Thus v : EqT[X,X]. Types EqT[A,B] and EqT[X,X] have no value in common if A ≠ X or B ≠ X, so A = X and B = X. Thus A = B.

Remark for people fluent in Scala (click to expand)

In production, it is convenient to define the following equivalent code:

sealed trait EqT[A,B]
object EqT {
  final case class Evidence[X]() extends EqT[X,X]

  implicit def evidence[X] : EqT[X,X] = Evidence[X]()

  def apply[A,B](implicit ev: EqT[A,B]): ev.type = ev
}

Switching between equal types

If A and B are actually the same type, then List[A] is also the same type as List[B], Option[A] is also the same type as Option[B], etc. More generally, for any F[_], F[A] is also the same type as F[B].

  • Question 4: Write the function def coerce[F[_],A,B](eqT: EqT[A,B])(fa: F[A]): F[B].

    Solution (click to expand)

    def coerce[F[_],A,B](eqT: EqT[A,B])(fa: F[A]): F[B] =
      eqT match {
        case _ : Evidence[x] => fa
      }

The Scala standard library already defines a class, named =:=[A,B] (yes, its name is really =:=), representing type equality. You’re strongly encouraged to have a quick look at its documentation (click here). Thankfully, Scala enables to write A =:= B instead of =:=[A,B].

Given two types A and B, having an instance (i.e. object) of A =:= B means that A and B are actually the same type, just like with EqT[A,B]. Remember that A =:= B is just syntactic sugar for the class =:=[A,B].

Instances of A =:= B can be created by the function (<:<).refl[X]: X =:= X (click for docs). The “symbol” <:< is indeed a valid name for an object.

  • Question 5: Using the function coerce above, write the function def toScalaEq[A,B](eqT: EqT[A,B]): A =:= B.

    Hint (click to expand)

    def toScalaEq[A,B](eqT: EqT[A,B]): A =:= B = {
      /* Find a definition for:
            - the type constructor `F`
            - the value `fa : F[A]`
      */
      type F[X] = ???
      val fa : F[A] = ???
    
      /* Such that this call: */
      coerce[F,A,B](eqT)(fa) // is of type `F[B]`
    }

    Solution (click to expand)

    def toScalaEq[A,B](eqT: EqT[A,B]): A =:= B = {
      type F[X] = A =:= X
      val fa: F[A] = (<:<).refl[A]
      coerce[F,A,B](eqT)(fa)
    }

  • Question 6: Using the method substituteCo[F[_]](ff: F[A]): F[B] of objects of class A =:= B, whose documentation is here. Write the function def fromScalaEq[A,B](scala: A =:= B): EqT[A,B].

    Hint (click to expand)

    def fromScalaEq[A,B](scala: A =:= B): EqT[A,B] = {
      /* Find a definition for:
            - the type constructor `F`
            - the value `fa : F[A]`
      */
      type F[X] = ???
      val fa : F[A] = ???
    
      /* Such that this call: */
      scala.substituteCo[F](fa) // is of type `F[B]`
    }

    Solution (click to expand)

    def fromScalaEq[A,B](scala: A =:= B): EqT[A,B] = {
      type F[X] = EqT[A,X]
      val fa: F[A] = Evidence[A]()
      scala.substituteCo[F](fa)
    }

Use Case: Witnessing Sub Typing

In this section, we want to create types SubType[A,B] whose values prove that the type A is a sub-type of B (i.e. A <: B). A similar but different class already exists in the Scala library. It is named <:<[A,B], which is often written A <:< B. Its documentation is here. Because this section is about implementing a variant of this class, please do not use <:<[A,B] to implement SubTypeOf.

  • Question 1: Using only upper bounds (i.e. A <: B) or lower bounds (i.e. A >: B) and no variance annotation (i.e. [+A] and [-A]), create the trait SubTypeOf[A,B] (and all that is necessary) such that:

    There exists a value of type SubType[A,B] if and only if A is a sub-type of B (i.e. A <: B).

    Remember that, by definition, a type A is always considered a sub-type of itself (i.e. A <: A).

    Remember that you should not use the class <:<[A,B].

    Solution (click to expand)

    sealed trait SubTypeOf[A,B]
    final case class SubTypeEvidence[A <: B, B]() extends SubTypeOf[A,B]

    Remark for people fluent in Scala (click to expand)

    In production, it is convenient to define the following equivalent code:

    sealed trait SubTypeOf[A,B]
    object SubTypeOf {
      final case class Evidence[A <: B, B]() extends SubTypeOf[A,B]
    
      implicit def evidence[A <: B, B]: SubTypeOf[A,B] = Evidence[A,B]()
    
      def apply[A,B](implicit ev: SubTypeOf[A,B]): ev.type = ev
    }

Use Case: Avoiding annoying scalac error messages about bounds not respected

In this example, we want to model the diet of some animals. We start by defining the Food type and some of its subtypes:

trait Food
class Vegetable extends Food
class Fruit extends Food

and then the class representing animals eating food of type A (i.e. Vegetable, Fruit, etc):

class AnimalEating[A <: Food]

val elephant : AnimalEating[Vegetable] = new AnimalEating[Vegetable]

Let’s define a function like there are so many in Functional Programming and apply it to elephant:

def dummy[F[_],A](fa: F[A]): Unit = ()
scala> dummy(elephant)
       ^
       error: inferred kinds of the type arguments (AnimalEating,Vegetable) do not conform to the expected kinds of the type parameters (type F,type A).
       AnimalEating's type parameters do not match type F's expected parameters:
       type A's bounds <: Food are stricter than type _'s declared bounds >: Nothing <: Any
             ^
       error: type mismatch;
        found   : AnimalEating[Vegetable]
        required: F[A]
  • Question 1: Why does scalac complains?

    Solution (click to expand)

    The function dummy requires its argument F to accept any type as argument so that we can write F[A] for any type A. On the contrary, AnimalEating requires its argument to be a sub-type of Food. Thus AnimalEating can not be used as dummy’s argument F.

The problem is that, when we defined class AnimalEating[A <: Food], we gave the restriction that A <: Food. So Scala, like Java, forbids us to give AnimalEating anything but a sub-type of Food (including Food itself):

scala> type T1 = AnimalEating[Int]
                 ^
       error: type arguments [Int] do not conform to class AnimalEating's type parameter bounds [A <: Food]

scala> type T2 = AnimalEating[Food]
defined type alias T2

We face a dilemma: to use the function dummy, that we really want to use because it’s a very nice function, we need to remove the constraint A <: Food from the definition of class AnimalEating[A <: Food]. But we still want to say that animals eat food, not integers, boolean or strings!

  • Question 2: How can you adapt the definition class AnimalEating[A] so that:

    • If A is not a sub-type of Food (including Food itself), then it is impossible to create an instance of AnimalEating[A].

    • The class class AnimalEating[A] must remain an open class (i.e. not sealed)! It should be possible for anyone, anywhen, to create freely sub-classes of AnimalEating. Obviously those sub-classes must satisfy the first constraint above.

    Hint (click to expand)

    In Scala, Nothing is a type having no value. Can you create a value of type (Nothing, Int)? Why?

    Solution (click to expand)

    If, to create an instance of AnimalEating[A], we force every creation method to take an extra paramerer of type SubTypeOf[A, Food], then it will only be possible to create an instance of AnimalEating[A] when A is a sub-type of Food:

    class AnimalEating[A](ev : SubTypeOf[A, Food])
    
    val elephant : AnimalEating[Vegetable] = new AnimalEating[Vegetable](SubTypeEvidence[Vegetable, Food])

    To create a value of type AnimalEating[A], we need to call AnimalEating’s constructor. And to call this constructor, we need to provide ev : SubTypeOf[A, Food].

    Now we can apply the dummy function on elephant:

    scala> dummy(elephant)

    In practice, using implicits, we let the compiler fill the parameter ev : SubTypeOf[A, Food] itself.

    Note that you can now express the type AnimalEating[Int] but you won’t be able to create a value of this type.

More Advanced Use Cases

Now that you have seen what GADTs are about and how to use them in real-life, you are ready for the big use-cases below. There are three of them. Each one illustrates one different way to use the power of GADTs. The first one is about expressing effects, which is widely used in every popular IO monads or algebraic effects. Do not worry if you do not know what they are, the section will clarifies it. The second one is about enforcing properties. This point is illustrated by a real-life use-case of enabling functional programming techniques but only on certain types (in the example, types supported by our fictional database). The third one is about simplifying the creation of implicits.

Use Case: Effects!

What we call an effect is sometimes just an interface declaring some functions with no implementation. For example we can define the trait below. Note that none of its function has an implementation.

trait ExampleEffectSig {
  def echo[A](value: A): A
  def randomInt : Int
  def ignore[A](value: A): Unit
}

Implementations of these interfaces are given elsewhere and there can be many of them! This is useful to switch between implementations easily:

object ExampleEffectImpl extends ExampleEffectSig {
  def echo[A](value: A): A = value
  def randomInt : Int = scala.util.Random.nextInt()
  def ignore[A](value: A): Unit = ()
}

Another equivalent way to define ExampleEffectSig is via a sealed trait with some final case class and case object (possibly none!):

sealed trait ExampleEffect[A]
final case class  Echo[A](value: A) extends ExampleEffect[A]
final case object RandomInt extends ExampleEffect[Int]
final case class  Ignore[A](value: A) extends ExampleEffect[Unit]

Once again this is a declaration with no implementation! Once again implementations can be written elsewhere and there can also be many of them:

def runExampleEffect[A](effect: ExampleEffect[A]): A =
  effect match {
    case Echo(value) => value
    case RandomInt   => scala.util.Random.nextInt()
    case Ignore(_)   => ()
  }

Let’s consider a more realistic effect and one possible implementation:

trait EffectSig {
  def currentTimeMillis: Long
  def printLn(msg: String): Unit
  def mesure[X,A](fun: X => A, arg: X): A
}

object EffectImpl extends EffectSig {
  def currentTimeMillis: Long =
    System.currentTimeMillis()

  def printLn(msg: String): Unit =
    println(msg)

  def mesure[X,A](fun: X => A, arg: X): A = {
    val t0 = System.currentTimeMillis()
    val r  = fun(arg)
    val t1 = System.currentTimeMillis()
    println(s"Took ${t1 - t0} milli-seconds")
    r
  }
}
  • Question 1: Just like ExampleEffect is the equivalent of ExampleEffectSig using a sealed trait with some final case class and case object, write the equivalent of EffectSig in the same way. Call this trait Effect.

    Solution (click to expand)

    sealed trait Effect[A]
    final case object CurrentTimeMillis extends Effect[Long]
    final case class  PrintLn(msg: String) extends Effect[Unit]
    final case class  Mesure[X,A](fun: X => A, arg: X) extends Effect[A]

  • Question 2: Write the function def run[A](effect: Effect[A]): A that mimics the implementation of EffectImpl just like runExampleEffect mimics ExampleEffectImpl.

    Solution (click to expand)

    def run[A](effect: Effect[A]): A =
      effect match {
        case CurrentTimeMillis =>
          System.currentTimeMillis()
    
        case PrintLn(msg) =>
          println(msg)
    
        case Mesure(fun, arg) =>
          val t0 = System.currentTimeMillis()
          val r  = fun(arg)
          val t1 = System.currentTimeMillis()
          println(s"Took ${t1 - t0} milli-seconds")
          r
      }

The type Effect[A] declare interesting effects (CurrentTimeMillis, PrintLn and Mesure) but to be really useful, we need to be able to chain effects! To do so, we want to have these two functions:

  • def pure[A](value: A): Effect[A]
  • def flatMap[X,A](fx: Effect[X], f: X => Effect[A]): Effect[A]

Once again we do not care yet about the implementation. Presently all we want is declaring these two operations just like we declared CurrentTimeMillis, PrintLn and Mesure.

  • Question 3: Add two final case classes, Pure and FlatMap, to Effect[A] declaring these operations.

    Solution (click to expand)

    sealed trait Effect[A]
    final case object CurrentTimeMillis extends Effect[Long]
    final case class  PrintLn(msg: String) extends Effect[Unit]
    final case class  Mesure[X,A](fun: X => A, arg: X) extends Effect[A]
    final case class  Pure[A](value: A) extends Effect[A]
    final case class  FlatMap[X,A](fx: Effect[X], f: X => Effect[A]) extends Effect[A]

  • Question 4: Adapt the function run to handle these two new cases.

    Solution (click to expand)

    def run[A](effect: Effect[A]): A =
      effect match {
        case CurrentTimeMillis =>
          System.currentTimeMillis()
    
        case PrintLn(msg) =>
          println(msg)
    
        case Mesure(fun, arg) =>
          val t0 = System.currentTimeMillis()
          val r  = fun(arg)
          val t1 = System.currentTimeMillis()
          println(s"Took ${t1 - t0} milli-seconds")
          r
    
        case Pure(a) =>
          a
    
        case FlatMap(fx, f) =>
          val x  = run(fx)
          val fa : Effect[A] = f(x)
          run(fa)
      }

  • Question 5: Add the two following methods to trait Effect[A] to get:

    sealed trait Effect[A] {
      final def flatMap[B](f: A => Effect[B]): Effect[B] = FlatMap(this, f)
      final def map[B](f: A => B): Effect[B] = flatMap[B]((a:A) => Pure(f(a)))
    }

    And run the follwing code to see if it works:

    val effect1: Effect[Unit] =
      for {
        t0 <- CurrentTimeMillis
        _  <- PrintLn(s"The current time is $t0")
      } yield ()
    
    run(effect1)

    Solution (click to expand)

    sealed trait Effect[A] {
      final def flatMap[B](f: A => Effect[B]): Effect[B] = FlatMap(this, f)
      final def map[B](f: A => B): Effect[B] = flatMap[B]((a:A) => Pure(f(a)))
    }
    final case object CurrentTimeMillis extends Effect[Long]
    final case class  PrintLn(msg: String) extends Effect[Unit]
    final case class  Mesure[X,A](fun: X => A, arg: X) extends Effect[A]
    final case class  Pure[A](value: A) extends Effect[A]
    final case class  FlatMap[X,A](fx: Effect[X], f: X => Effect[A]) extends Effect[A]
    
    def run[A](effect: Effect[A]): A =
      effect match {
        case CurrentTimeMillis =>
          System.currentTimeMillis()
    
        case PrintLn(msg) =>
          println(msg)
    
        case Mesure(fun, arg) =>
          val t0 = System.currentTimeMillis()
          val r  = fun(arg)
          val t1 = System.currentTimeMillis()
          println(s"Took ${t1 - t0} milli-seconds")
          r
    
        case Pure(a) =>
          a
    
        case FlatMap(fx, f) =>
          val x  = run(fx)
          val fa : Effect[A] = f(x)
          run(fa)
      }
    
    val effect1: Effect[Unit] =
      for {
        t0 <- CurrentTimeMillis
        _  <- PrintLn(s"The current time is $t0")
      } yield ()

    When we run run(effect1):

    scala> run(effect1)
    The current time is 1569773175010

Congratulations! You just wrote your first IO monad! There is a lot of scientific words to name the sealed trait Effect[A]: you can call it an algebraic effect, a free monad, an IO, etc. But in the end, it is just a plain simple sealed trait where we just declared some final case class and case object to represent the functions we wanted to have without providing their implementation (CurrentTimeMillis, PrintLn, Mesure, Pure and FlatMap). You can call them virtual methods if you like. What really matters is that we isolated the declaration of the functions from their implementation. Remember that a trait is just a interface after all.

Use Case: Ensuring types are supported by the Database

Databases are great. We can store tables, documents, key/values pairs, graphs, etc. But for any database, there is unfortunately only a limited set of supported types. Take a database you like, I am sure I can find some types it does not support.

In this section we consider the use-case of data structures and code that do not work for (values of) any type but only for some! This problem is not limited to databases but concerns any API that only supports a limited set of types (the vast majority of APIs). How to enforce this constraint? How to adapt the patterns we like to work under this constraint? This is all this section is about.

We consider a fictional database that only supports the following types:

  1. String
  2. Double
  3. (A,B) where A and B are also types supported by the database.

It means that the values stores by the database (in tables, key/value pairs, etc) must follow the rules above. It can store "Hello World" because it is a String which is a supported type by rule 1. Likewise, it can store 5.2 because it is a Double, but it can not store 5 because it is an Int. It can store ("Hello World", 5.2) thanks to rule 3 and also (("Hello World", 5.2) , 8.9) once again by rule 3.

  • Question 1: Define the type DBType[A] such that:

    There exists a value of type DBType[A] if and only if A is a type supported by the database.

    Solution (click to expand)

    The simple version is:

    sealed trait DBType[A]
    final case object DBString extends DBType[String]
    final case object DBDouble extends DBType[Double]
    final case class  DBPair[A,B](first: DBType[A], second: DBType[B]) extends DBType[(A,B)]

    Remark for people fluent in Scala (click to expand)

    Using all the nice features of Scala, the production-ready version of the code above is:

    sealed trait DBType[A]
    object DBType {
      final case object DBString extends DBType[String]
      final case object DBDouble extends DBType[Double]
      final case class DBPair[A,B](first: DBType[A], second: DBType[B]) extends DBType[(A,B)]
    
      implicit val dbString : DBType[String] =
        DBString
    
      implicit val dbDouble : DBType[Double] =
        DBDouble
    
      implicit def dbPair[A,B](implicit first: DBType[A], second: DBType[B]): DBType[(A,B)] =
        DBPair(first, second)
    
      def apply[A](implicit ev: DBType[A]): ev.type = ev
    }

Using DBType, we can pair a value of type A with a value of type DBType[A] which provides an evidence that the type A is supported by the database:

final case class DBValue[A](value: A)(implicit val dbType: DBType[A])

Note that the parameter dbType does not need to be implicit! All that matters is that to create a value of type DBValue[A], we need to provide a value of type DBType[A] which forces A to be a supported type.

A functor is, approximately, a type constructor F[_] like List, Option, DBValue, … for which you can write an instance of the trait

trait Functor[F[_]] {
  def map[A,B](fa: F[A])(f: A => B): F[B]
}

where map(fa)(f) applies the function f to any value of type A contained in fa. For example:

implicit object OptionFunctor extends Functor[Option] {
  def map[A,B](fa: Option[A])(f: A => B): Option[B] =
    fa match {
      case Some(a) => Some(f(a))
      case None => None
    }
}
  • Question 2: Write an instance of Functor[DBValue].

    Solution (click to expand)

    We actually can not! If we try to compile the following code:

    object DBValueFunctor extends Functor[DBValue] {
      def map[A,B](fa: DBValue[A])(f: A => B): DBValue[B] =
        DBValue[B](f(fa.value))
    }

    Scala complains: could not find implicit value for parameter dbType: DBType[B]. Indeed, booleans are not a supported type by the database: they are neither strings, nor number, not pairs. But if we could write a Functor instance for DBValue (i.e. if we could write a map function for DBValue), then we could write:

    val dbValueString  : DBValue[String]  = DBValue("A")(DBString)
    val dbValueBoolean : DBValue[Boolean] = dbValueString.map(_ => true)
    val dbTypeBoooean  : DBType[Boolean]  = dbValueBoolean.dbType

    We would get a value (dbTypeBoooean) of type DBType[Boolean] which would mean that the type Boolean is supported by the database. But it is not! And by definition:

    There exists a value of type DBType[A] if and only if A is a type supported by the database.

    So it is impossible to have a value of type DBType[Boolean] and thus it is impossible to write a function map for DBValue. So there is no way to write a Functor instance for DBValue.

A Generalized Functor is very much like a regular Functor but the map function do not apply to any type A and B but is restricted to the only types A and B satisfying some condition:

trait GenFunctor[P[_],F[_]] {
  def map[A,B](fa: F[A])(f: A => B)(implicit evA: P[A], evB: P[B]): F[B]
}

For example Set (more precisely TreeSet) is not a functor! Indeed there is no way to write a function map that works for any type B (because B need to have an ordering). But if we restrict map to only types B having an ordering, then we can write it.

import scala.collection.immutable._
object TreeSetFunctor extends GenFunctor[Ordering, TreeSet] {
  def map[A,B](fa: TreeSet[A])(f: A => B)(implicit evA: Ordering[A], evB: Ordering[B]): TreeSet[B] =
    TreeSet.empty[B](evB) ++ fa.toSeq.map(f)
}
  • Question 3: Write an instance of GenFunctor[DBType, DBValue]r

    Solution (click to expand)

    object DBValueGenFunctor extends GenFunctor[DBType, DBValue] {
    def map[A,B](fa: DBValue[A])(f: A => B)(implicit evA: DBType[A], evB: DBType[B]): DBValue[B] =
      DBValue[B](f(fa.value))(evB)
    }

What we have done to Functor can be done for many data-structures and patterns. We can often limit the types on which a data-structure or a type-class can operate by adding an extra parameter like ev : DBType[A] to constructors and methods.

Use Case: Simplifying Implicits

This use-case is one the most interesting but unfortunately, not one of the easiest. It illustrates how it is possible to use GADTs to simplify the creation of implicit values. In this example we consider lists of values whose items can be of different types. Theses lists are called heterogeneous lists. They are usually defined in Scala almost like normal lists:

final case class HNil() // The empty list
final case class HCons[Head,Tail](head: Head, tail: Tail) // The `head :: tail` operation

val empty : HNil =
  HNil()

val oneTrueToto : HCons[Int, HCons[Boolean, HCons[String, HNil]]] =
  HCons(1, HCons(true, HCons("toto", HNil())))

val falseTrueFive: HCons[Boolean, HCons[Boolean, HCons[Int, HNil]]] =
  HCons(false, HCons(true, HCons(5, HNil())))

As you can see, there is nothing special about it. We want to define orderings on heterogeneous lists. An ordering is a way to compare two values (of the same type!): they can be equal or one may be lesser than the other. In Scala we can define the trait Order:

trait Order[A] {
  // true if and only if a1 < a2
  def lesserThan(a1: A, a2: A): Boolean

  // a1 and a2 are equal if and only if none of them is lesser than the other.
  final def areEqual(a1: A, a2: A): Boolean = !lesserThan(a1, a2) && !lesserThan(a2, a1)

  // a1 > a2 if and only if a2 < a1
  final def greaterThan(a1: A, a2: A): Boolean = lesserThan(a2, a1)

  final def lesserThanOrEqual(a1: A, a2: A): Boolean = !lesserThan(a2, a1)

  final def greaterThanOrEqual(a1: A, a2: A): Boolean = !lesserThan(a1, a2)
}

object Order {
  def apply[A](implicit ev: Order[A]): ev.type = ev

  def make[A](lg_ : (A,A) => Boolean): Order[A] =
    new Order[A] {
      def lesserThan(a1: A, a2: A): Boolean = lg_(a1,a2)
    }
}

implicit val orderInt    = Order.make[Int](_ < _)
implicit val orderString = Order.make[String](_ < _)

Remember that we will only compare lists of the same type:

  • Lists of type HNil will only be compared to lists of type HNil.
  • Lists of type HCons[H,T] will only be compared to lists of type HCons[H,T].

Comparing lists of type HNil is trivial because there is only one value of type HNil: the empty list HNil(). We want to define several orderings on heterogeneous lists. Here are two possible orderings (but there exists many more!):

  • The lexicographic ordering (i.e. dictionary order: from left to right)

    HCons(h1,t1) < HCons(h2,t2) if and only if h1 < h2 or (h1 == h2 and t1 < t2 by lexicographic ordering).

    sealed trait Lex[A] {
      val order : Order[A]
    }
    
    object Lex {
      def apply[A](implicit ev: Lex[A]): ev.type = ev
    
      implicit val lexHNil: Lex[HNil] =
        new Lex[HNil] {
          val order = Order.make[HNil]((_,_) => false)
        }
    
      implicit def lexHCons[Head,Tail](implicit
          orderHead: Order[Head],
          lexTail: Lex[Tail]
        ): Lex[HCons[Head, Tail]] =
        new Lex[HCons[Head, Tail]] {
          val orderTail: Order[Tail] = lexTail.order
    
          val order = Order.make[HCons[Head, Tail]] {
            case (HCons(h1,t1), HCons(h2,t2)) =>
              orderHead.lesserThan(h1,h2) || (orderHead.areEqual(h1,h2) && orderTail.lesserThan(t1,t2))
          }
        }
    }
  • The reverse-lexicographic ordering which is the reverse version of the lexicographic ordering (i.e. from right to left)

    HCons(h1,t1) < HCons(h2,t2) if and only if t1 < t2 by reverse-lexicographic ordering or (t1 == t2 and h1 < h2).

    sealed trait RevLex[A] {
      val order : Order[A]
    }
    
    object RevLex {
      def apply[A](implicit ev: RevLex[A]): ev.type = ev
    
      implicit val revLexHNil: RevLex[HNil] =
        new RevLex[HNil] {
          val order = Order.make[HNil]((_,_) => false)
        }
    
      implicit def revLexHCons[Head,Tail](implicit
          orderHead: Order[Head],
          revLexTail: RevLex[Tail]
        ): RevLex[HCons[Head, Tail]] =
        new RevLex[HCons[Head, Tail]] {
          val orderTail: Order[Tail] = revLexTail.order
    
          val order = Order.make[HCons[Head, Tail]] {
            case (HCons(h1,t1), HCons(h2,t2)) =>
              orderTail.lesserThan(t1,t2) || (orderTail.areEqual(t1,t2) && orderHead.lesserThan(h1,h2))
          }
        }
    }

As said above, it is possible to define more orderings:

  • Question 1: The Alternate ordering is defined by:

    HCons(h1,t1) < HCons(h2,t2) if and only if h1 < h2 or (h1 == h2 and t1 > t2 by alternate ordering).

    Just like what was done for Lex and RevLex, implement the Alternate ordering.

    Solution (click to expand)

    sealed trait Alternate[A] {
      val order : Order[A]
    }
    
    object Alternate {
      def apply[A](implicit ev: Alternate[A]): ev.type = ev
    
      implicit val alternateHNil: Alternate[HNil] =
        new Alternate[HNil] {
          val order = Order.make[HNil]((_,_) => false)
        }
    
      implicit def alternateHCons[Head,Tail](implicit
          orderHead: Order[Head],
          alternateTail: Alternate[Tail]
        ): Alternate[HCons[Head, Tail]] =
        new Alternate[HCons[Head, Tail]] {
          val orderTail: Order[Tail] = alternateTail.order
    
          val order = Order.make[HCons[Head, Tail]] {
            case (HCons(h1,t1), HCons(h2,t2)) =>
              orderHead.lesserThan(h1,h2) || (orderHead.areEqual(h1,h2) && orderTail.greaterThan(t1,t2))
          }
        }
    }

There are lots of ways to define a valid ordering on heterogeneous lists! Defining type-classes like Lex, RevLex and Alternate for every ordering we want to implement is clunky and messy. We can do much better than that … with a GADT 😉

sealed trait HListOrder[A]
object HListOrder {
  final case object HNilOrder extends HListOrder[HNil]

  final case class HConsOrder[Head,Tail](
      orderHead: Order[Head],
      hlistOrderTail: HListOrder[Tail]
    ) extends HListOrder[HCons[Head,Tail]]

  // Implicit definitions

  implicit val hnilOrder : HListOrder[HNil] =
    HNilOrder

  implicit def hconsOrder[Head,Tail](implicit
      orderHead: Order[Head],
      hlistOrderTail: HListOrder[Tail]
    ): HListOrder[HCons[Head,Tail]] =
    HConsOrder(orderHead, hlistOrderTail)

  def apply[A](implicit ev: HListOrder[A]): ev.type = ev
}

Note that these implicit definitions are boilerplate. Their only purpose is passing arguments to their corresponding constructor (i.e. final case class or case object): hnilOrder to HListOrder (O arguments) and hconsOrder to HConsOrder (2 arguments).

  • Question 2: Write the function def lex[A](implicit v : HListOrder[A]): Order[A] that compute the lexicographic ordering from a value of type HListOrder[A].

    Solution (click to expand)

    def lex[A](implicit v : HListOrder[A]): Order[A] =
      v match {
        case HListOrder.HNilOrder =>
          Order.make[HNil]((_,_) => false)
    
        case hc : HListOrder.HConsOrder[head,tail] =>
          val orderHead: Order[head] = hc.orderHead
          val orderTail: Order[tail] = lex(hc.hlistOrderTail)
    
          Order.make[HCons[head, tail]] {
            case (HCons(h1,t1), HCons(h2,t2)) =>
              orderHead.lesserThan(h1,h2) || (orderHead.areEqual(h1,h2) && orderTail.lesserThan(t1,t2))
          }
      }

  • Question 3: Write the function def revLex[A](implicit v : HListOrder[A]): Order[A] that compute the reverse-lexicographic ordering from a value of type HListOrder[A].

    Solution (click to expand)

    def revLex[A](implicit v : HListOrder[A]): Order[A] =
      v match {
        case HListOrder.HNilOrder =>
          Order.make[HNil]((_,_) => false)
    
        case hc : HListOrder.HConsOrder[head,tail] =>
          val orderHead: Order[head] = hc.orderHead
          val orderTail: Order[tail] = revLex(hc.hlistOrderTail)
    
          Order.make[HCons[head, tail]] {
            case (HCons(h1,t1), HCons(h2,t2)) =>
              orderTail.lesserThan(t1,t2) || (orderTail.areEqual(t1,t2) && orderHead.lesserThan(h1,h2))
          }
      }

This approach has several benefits. Whereas the initial approach had to find one implicit by ordering, the GADT approach only have to find one! Considering implicit resolution is a costly operation, reducing it means faster compilation times. Reading the code of functions lex and revLex is easier than understanding how implicit resolution works for traits Lex and RevLex because they are just functions, you can use all you can code in building the instance Order[A].

Conclusion

Not so trivial, isn’t it? 😉 Actually a fair amount of the complexity you may have experienced comes to the fact that reasoning about values and types is almost never taught in programming courses. What you consider simple now (web apis, streaming, databases, etc) would probably terrifies your younger self when you were introduced for the first time to “Hello World!”. You probably did not learn all you know in programming in three hours so do not expect reasoning about programs to be magically easier.

This workshop aimed at inspiring you, opening your mind to this all new set of possibilities. If you found the use-case interesting, then take the time to understand the techniques.

Have fun and take care ❤️