Playing with Probability in Scala 3

11 Jul 2020 - 5700 Words

Here is a simple experiment: take a fair dice (or a coin) and roll it until every side of the dice has been observed at least once. Write down the number of rolls and repeat the operation several times. On average, how many rolls does it take to observe every side of the dice at least once? This is precisely the question we are about to answer together.

Solving Maths puzzle is fun. Solving them using the shiniest features of Scala 3 is even amazingly funnier! If you do not have Scala 3 installed yet:

• on Arch Linux, as usual there is an AUR package : aur/scala-dotty. Install it via yay -S aur/scala-dotty or any other AUR helper.
• on other Linux distributions, download https://github.com/lampepfl/dotty/releases/download/0.25.0-RC2/dotty-0.25.0-RC2.tar.gz , extract it and make sure the executables are in your $PATH.
• on other systems, follow the instructions here.

You should now be able to run the Scala 3 REPL via the command:

[shell prompt]$ dotr -new-syntax -Yexplicit-nulls -Yerased-terms -indent -version
Starting dotty REPL...
Dotty compiler version 0.25.0-RC2 -- Copyright 2002-2020, LAMP/EPFL
scala>

An Important Note: Please refrain from starting your favourite IDE or starting a new project. It will only make experimenting harder and painful. All you need is the Scala 3 REPL, any basic text editor and knowing how to copy-paste on your system.

Understanding the Problem

Let us start by modelling a dice. The sides of a dice will be numbered starting from 1. We consider a coin as a 2-sided dice whose sides are 1 and 2. The sides of an usual 6-sided dice are 1, 2, 3, 4, 5 and 6.

final case class Dice(sides: Int) {
  def roll(): Int =
    scala.util.Random.nextInt(sides) + 1
}

val d2   = Dice(2)
val d6   = Dice(6)
val d10  = Dice(10)
val d20  = Dice(20)
val d100 = Dice(100)

d2 models a coin, d6 models a usual 6-sided dice, etc. The method roll , as its name suggest, simulates rolling the dice. On each invocation it gives a random side (its number). The first question to answer is: is such a dice fair ? Remember that a fair dice is one for which every side is equally likely to be observed. For a coin, it means getting 1 is as likely as getting 2. To check empirically that a dice is fair, or at least not loaded, we will roll it many times and count how often we observe its sides:

def (dice: Dice) frequencies(rolls: Long): Map[Int, Double] =
  // Stores how many times we observed each side
  val arr = Array.fill(dice.sides)(0)
  for i <- 1L to rolls do
    arr(dice.roll() - 1) += 1

  // Transforms counters into ratio
  val probability: IndexedSeq[(Int, Double)] =
    for i <- 1 to dice.sides yield
      i -> arr(i-1).toDouble / rolls
  probability.toMap

scala> d2.frequencies(1000000000L)
val res0: Map[Int, Double] = Map(1 -> 0.499985517, 2 -> 0.500014483)

scala> d6.frequencies(1000000000L)
val res1: Map[Int, Double] = HashMap(
  1 -> 0.166669596,
  2 -> 0.166660131,
  3 -> 0.166664591,
  4 -> 0.166654524
  5 -> 0.166665811,
  6 -> 0.166685347)

This extension method can be called like any method of Dice. As you can see, the frequencies are very close to each other. In addition, the more rolls we perform, the closer they are. We can conclude that these dice are fair enough. We are finally ready for our big adventure: finding the so desired average! We call an experiment the action of rolling the dice until every side has been observed at least once and the length of the experiment its number of rolls. The method rollUntilAllSeen simulates an experiment and return its length.

def (dice: Dice) rollUntilAllSeen(): Int =
  var rolls     = 0
  val seen      = Array.fill(dice.sides)(false)
  var remaining = dice.sides

  while remaining > 0 do
    val outcome = dice.roll()
    rolls += 1
    if !seen(outcome-1) then
      seen(outcome-1) = true
      remaining -= 1
  rolls

scala> d6.rollUntilAllSeen()
val res2: Int = 12

scala> d6.rollUntilAllSeen()
val res3: Int = 15

scala> d6.rollUntilAllSeen()
val res4: Int = 8

scala> d6.rollUntilAllSeen()
val res5: Int = 9

Based on the four experiments above, we get the impression that the average should be close to 11, but four experiments are not a lot to get an accurate estimation of the real average. Fortunately, the more experiments we run, the closer we get to it. We need to compute the average over a large number of experiments. We will actually be a bit smarter. Instead of limiting ourselves to computing the average, we will count, for every observed length, the number of its experiments. It will give us how often a length is observed, i.e. its frequency.

final case class Histogram[A](values: Map[A, BigInt]) {

  def average(using Accumulable[A], Ratio[A]): A =
    var acc   : A      = summon[Accumulable[A]].zero
    var total : BigInt = BigInt(0)
    for (a,count) <- values do
      acc += a*count
      total += count
    acc / total

  def frequencies(using Ratio[A]): Map[A, BigDecimal] =
    val total = values.values.sum
    values.map { case (a, count) => a -> BigDecimal(count) / BigDecimal(total) }

  def map[B](f: A => B): Histogram[B] =
    var histoB = scala.collection.mutable.Map.empty[B, BigInt]
    for (a, count) <- values do
      val b = f(a)
      histoB.update(b, histoB.getOrElse(b, BigInt(0)) + count)
    new Histogram[B](histoB.toMap)
}

object Histogram {
  def apply[A](iterations: Long)(value : => A): Histogram[A] =
    var histo = scala.collection.mutable.Map.empty[A, BigInt]
    for i <- 1L to iterations do
      val a = value
      histo.update(a, histo.getOrElse(a, BigInt(0)) + 1)
    new Histogram(histo.toMap)
}

The class Histogram[A] is essentially a key-value store where the value is the number of times the key has been observed, also known as its multiplicity. You may also wonder how Scala can accept adding two values of type A and multiplying/dividing a value of type A by a BigInt in average. It works thanks to the magic of Type Classes in Scala 3. Accumulable and Ratio are two type classes defined by:

trait Accumulable[A] {
  def zero: A
  def (x:A)+(y:A): A
  def (x:A)*(m: BigInt): A
}

trait Ratio[A] {
  def (x:A) / (m: BigInt): A
}

Note that, unlike Scala 2, no weird implicit conversion is required to support infix syntax for +, * and /. These methods are just defined as extension methods.

scala> val h6 = Histogram(100000000L)(d6.rollUntilAllSeen())
val h6: Histogram[Int] = Histogram(HashMap(73 -> 202, 69 -> 385, 88 -> 17,
  10 -> 8298014, 56 -> 4403, 42 -> 56557, 24 -> 1462064, 37 -> 140975, ...))

scala> h6.average
1 |h6.average
  |          ^
  |no implicit argument of type Accumulable[Int] was found for parameter x$1 of method average in class Histogram

If your first reaction is to implement an instance of Accumulable for Int, ask yourself how you could be confident that the computed values are correct when adding two positive numbers can result into a negative one:

scala> val x = 1990000000
val x: Int = 1990000000

scala> x + x
val res0: Int = -314967296

I am well aware that most use cases using Int is perfectly fine, because they never have numbers big enough to reach this limit. After all, 10 digits ought to be enough for anybody, right? In the next sections, you will see that we will reach this limit very often! Writing an instance of Accumulable for Int is a catastrophic idea. Instead we will write instances for BigInt and BigDecimal.

given Accumulable[BigInt] {
  def zero: BigInt = BigInt(0)
  def (x:BigInt)+(y:BigInt): BigInt = x+y
  def (x:BigInt)*(m:BigInt): BigInt = x*m
}

given Accumulable[BigDecimal] with Ratio[BigDecimal] {
  def zero: BigDecimal = BigDecimal(0)
  def (x:BigDecimal)+(y:BigDecimal): BigDecimal = x+y
  def (x:BigDecimal)*(m:BigInt): BigDecimal = x*BigDecimal(m)
  def (x:BigDecimal)/(m:BigInt): BigDecimal = x/BigDecimal(m)
}

Now we can get out much awaited average:

scala> h6.map(BigDecimal(_)).average
val res0: BigDecimal = 14.69830127

scala> Histogram(10000000L)(BigDecimal(d6.rollUntilAllSeen())).average
val res1: BigDecimal = 14.6949955

As you can see, the average is never far from 14.69. Knowing the average is nice but it does not tell us much about how the length is distributed among the experiments. This is precisely the reason why we kept counters! To visualize this data, we can export the histogram as a CSV file.

def (histogram: Histogram[Int])toCSV(fileName: String): Unit =
    import java.io._
    val pw = new PrintWriter(new File(fileName))
    pw.println("value,count")
    for length <- 0 to histogram.values.keySet.max do
      pw.println(s"$length,${histogram.values.getOrElse(length, BigInt(0))}")
    pw.close()

scala> h6.toCSV("d6.csv")

Opening the file d6.csv with LibreOffice and plotting the data as a XY Chart using the value column as X and count as Y gives this chart:

As you can see, after length 15, there is a huge decrease in the number of experiments. And after length 50, the number of experiment is almost neglectable. The situation is similar for other dice. For example, here is the curve for d100:

By running enough experiment, we can get an pretty close estimation of the average. But an experiment is by nature random, every measure we perform is very likely to give a (close but still) different estimation of the average. We need a more reliable way to approximate the average.

Modelling the Problem

To get a more reliable approximation of the average, or the exact value, we can not rely on random experiments. We need to use maths! Remember that an experiment is a sequence of dice rolls such that, as soon as every side of the dice have been observed at least once, the sequence is over. Given a dice, we will call a sequence of sides valid when it follows these rules.

Using a 3-sided dice:

• The sequence 2→2→1→2 is invalid because the side 3 has not been observed.
• The sequence 2→2→1→2→3→3 is invalid because the sequence needs to stop as soon as every side has been observed so the last roll is not required.
• The sequence 2→2→1→2→3 is valid: every side has been observed and it was not possible to stop earlier.

Note that the validity depends on the dice used! The sequence 2→2→1→2→3 is valid for a 3-sided dice but invalid for a 4-sided dice. To compute the average, we will: (1) enumerate all valid sequences (up to a certain length), then (2) sum their length and finally (3) divide by the number of values in the sum.

def enumerate(sides: Int, depth: Int): LazyList[List[Int]] =
  def aux(revSeq: List[Int]): LazyList[List[Int]] =
    if revSeq.length > depth
    then LazyList.empty
    else if revSeq.toSet.size == sides
          then LazyList(revSeq.reverse)
          else LazyList.range(1, sides+1).flatMap { next => aux(next :: revSeq) }

  aux(List.empty)

def average(sides: Int, depth: Int): Double =
  val validSequences = enumerate(sides, depth)
  validSequences.map(_.length.toDouble).sum / validSequences.size

For a 3-sided dice, the list of all valid sequences up to length 5 is:

scala> enumerate(3,5).map(_.mkString("→")).toList
val res26: List[String] = List(
  1→1→1→2→3, 1→1→1→3→2, 1→1→2→1→3, 1→1→2→2→3, 1→1→2→3,   1→1→3→1→2, 1→1→3→2, 1→1→3→3→2,
  1→2→1→1→3, 1→2→1→2→3, 1→2→1→3,   1→2→2→1→3, 1→2→2→2→3, 1→2→2→3,   1→2→3,
  1→3→1→1→2, 1→3→1→2,   1→3→1→3→2, 1→3→2,     1→3→3→1→2, 1→3→3→2,   1→3→3→3→2,
  2→1→1→1→3, 2→1→1→2→3, 2→1→1→3,   2→1→2→1→3, 2→1→2→2→3, 2→1→2→3,   2→1→3,
  2→2→1→1→3, 2→2→1→2→3, 2→2→1→3,   2→2→2→1→3, 2→2→2→3→1, 2→2→3→1,   2→2→3→2→1, 2→2→3→3→1,
  2→3→1,     2→3→2→1,   2→3→2→2→1, 2→3→2→3→1, 2→3→3→1,   2→3→3→2→1, 2→3→3→3→1,
  3→1→1→1→2, 3→1→1→2,   3→1→1→3→2, 3→1→2,     3→1→3→1→2, 3→1→3→2,   3→1→3→3→2,
  3→2→1,     3→2→2→1,   3→2→2→2→1, 3→2→2→3→1, 3→2→3→1,   3→2→3→2→1, 3→2→3→3→1,
  3→3→1→1→2, 3→3→1→2,   3→3→1→3→2, 3→3→2→1,   3→3→2→2→1, 3→3→2→3→1, 3→3→3→1→2, 3→3→3→2→1
  )

That’s awesome! We just have to average all the lengths:

scala> average(3,5)
val res27: Double = 4.545454545454546

scala> average(3,10)
val res32: Double = 9.071713147410359

scala> average(3,14)
val res36: Double = 13.00953778429934

scala> average(3,16)
val res39: Double = 15.003205911089399

Apparently, computing the average for sequences up to length 16 does not converge yet. Unfortunately our implementation is to slow for large sequences. The number of valid sequences grows exponentially over length. We need a much faster algorithm.

def aggregate[A:Accumulable](sides: Int, depth: Int)(f: Int => A): A =
  var current : Array[BigInt] = Array.fill(sides+1)(BigInt(0))
  var next    : Array[BigInt] = Array.fill(sides+1)(BigInt(0))
  var agg     : A             = summon[Accumulable[A]].zero
  var length  : Int           = 0

  current(0) = BigInt(1) // The empty sequence is the unique sequence where 0 sides have been seen

  while length <= depth do
    agg += f(length) * current(sides)

    for seen <- 0 to sides - 1 do
      next(seen)     += current(seen) * seen
      next(seen + 1) += current(seen) * (sides - seen)

    length += 1
    current = next
    next    = Array.fill(sides+1)(BigInt(0))

  agg

This is a generic aggregation function that, given a sides-sided dice, gives to every valid sequence a value that depends only on its length (via f) and aggregate them over all valid sequences up to a certain length called the depth. We can use it to compute the average for sequences up to length 100000).

scala> val depth = 100000
val depth: Int = 100000

scala> val sides = 3
val sides: Int = 3

scala> val sumOfLengths = aggregate(sides,depth)(length => BigInt(length))
val sumOfLengths: BigInt = A 30109 digits positive integer

scala> val numberOfSeqs = aggregate(sides,depth)(length => BigInt(1))
val numberOfSeqs: BigInt =  A 30104 digits positive integer

scala> val avegrageUpTo100000 = (BigDecimal(sumOfLengths)/numberOfSeqs).toDouble
val avegrageUpTo100000: Double = 99999.0

The average does not seem to converge. Have a look at previous estimations of the averages for depths 5, 10, 14 and 16. The average seem very close to depth - 1. It seem to indicate that, on average, you need to roll a 3-sided dice an infinity of times to obverse every side at least once. It means that, regardless the number of rolls you perform, it is almost certain that you will never see at least once side. Let’s confirm that using the methods of the previous section:

scala> val d3 = Dice(3)
val d3: Dice = Dice(3)

scala> val h3 = Histogram(100000000L)(d3.rollUntilAllSeen())
val h3: Histogram[Int] = Histogram(HashMap(...))

scala> h3.map(BigDecimal(_)).average
val res6: BigDecimal = 5.5003517

The experience shows that, on average, 5.5 rolls are enough to see every side of a 3-sided dice. The only possible conclusion is that our modeling is very wrong. The problem is we consider every sequence to be equally likely. But the sequence 1→2→3 is much likelier to happen than 1→2→2→1→2→1→2→1→1→2→1→3. We can plot the h3 histogram to check that the longer a sequence is, the less likely it is to happen:

Our real big mistake is our mathematical modeling does not model the real problem. This is a very important rule in modeling: models much match closely the things they are supposed to model.

Understanding the Experiment

To get a mathematical model that closely match the experience, we need to have a deeper understanding of the problem. When we perform 10000000 experiments, we get as many valid sequences of sides. But taking the hypothesis that theses sequences are all distinct is wrong. An experiment is a random process, you may get the same sequence several times. We need to take into account how often a sequence is likely to happen.

Given a \(n\)-sided fair dice, by definition of fairness, every time we roll the dice, for any side, there is exactly \(\frac{1}{n}\) chance to observe this side. Each roll being independent from other ones, for every sequence of \(m\) rolls, there is \((\frac{1}{n})^m\) chance to observe this sequence.

Do not jump on the conclusion that the probability of a valid sequence of length \(m\) in our problem is \((\frac{1}{n})^m\) yet! If we change the problem slightly by requiring that every side is observed exactly once (ignoring sequences where one side is observed several times). Then for a coin there is only 2 valid sequences 1→2 and 2→1, each equally likely so they both have probability \(\frac{1}{2}\), not \(\frac{1}{4}\). The good way to proceed is finding a probability space that models correctly the problem.

Remember that the dice used has been fixed as a \(n\)-sided fair dice. The first step in defining a probability space is defining the outcomes. Outcomes are the results of statistical experiments. It our problem, outcomes are the valid sequences of dice rolls. Then we need to define the set of events. Events are the things whose likelihood we want to measure! For example: what is the probability that a valid sequence starts with 1, or what is the probability that a valid sequence is a palindrome (i.e. the reverse of the sequence is the sequence itself),etc. It feels natural, in our situation, to consider as event, any set of valid sequences. Last but not least, we need the probability function. Its purpose is to give, for any event, the likelihood of this event. Informally, a probability function must satisfy 3 properties:

1. the likelihood of any event must be positive or null but never negative!
2. the likelihood of distinct events is the sum of the likelihood of every event.
3. the likelihood of the set of all valid sequences must be 1.

This is where things get complicated. We can decide to give to any valid sequence of size \(m\) the the probability (\((\frac{1}{n})^m\)), but we need to prove that this function satisfies all the conditions above to be a probability function. In addition, the set of valid sequences is not that trivial to work with (at least for me!). Fortunately working in this probability space is not mandatory. We can work in more comfortable probability space as long as we are able to transpose results into this one.

Remember that the dice being used is a \(n\)-sided fair dice. Let us start by some definitions:

• Let \(\mathcal{C}_n=\{1,\dots,n\}\) be the set of the dice’s sides.

• The set of countably infinite sequences of sides is written \(\Omega\).

• The set of finite sequences of sides is written \(\mathcal{F}\).

• For any finite sequence of sides \(f \in \mathcal{F}\), its length is written \(|f|\).

• For any sequence \(s \in \mathcal{F} \cup \Omega\) of sides (finite or infinite), let \(\diamond s\) be the set of sides observed in \(s\) and \(\sharp s\) be the number of distinct sides observed in \(s\), i.e. \(\sharp s = |\diamond s|\).

• For any sequence \(s \in \mathcal{F} \cup \Omega\) of sides (finite or infinite), and any \(i \in \{1,\dots,|s]\}\), let \(s_{[i]}\) be the sides observed at the \(i\)-th roll of \(s\), i.e. \(s=(s_{[1]},\dots,s_{[|s|]})\).

• For any \(f \in \mathcal{F}\) and \(f' \in \mathcal{F}\cup\Omega\), where \(f = (s_1,\dots,s_i)\) and \(f' = (s'_1,\dots)\), we write \(f \cdot f' \in \mathcal{F}\cup\Omega\) the concatenation of \(f\) and \(f'\), i.e. the sequence \((s_1,\dots,s_i,s'_1,\dots)\). Furthermore, for any set of prefix \(F \subset \mathcal{F}\), and any set set of (finite or infinite) sequences \(S\subset \mathcal{F}\cup\Omega\), we write \(F\cdot S = \{f\cdot s\mid f\in F,\ s\in S\}\) the set of sequences made of concatenations of \(F\) and \(S\).

For the new probability space, we can take as outcomes \(\Omega\), the set of all infinite (but countable) sequence of sides. Given a finite sequence of sides \(f \in \mathcal{F}\) (possibly empty), the set of all outcomes (infinite sequences) that start with \(f\) is called a prefix event and written \(\mathcal{E}(f)\). The finite sequence \(f \in \mathcal{F}\) is called a prefix. Note that the set of all outcomes, \(\Omega\), is an event because it is the prefix event of the empty sequence \(\epsilon\). The set of all prefix events is written \(\mathcal{E}\). We will take as events the the σ-field \(\sigma(\mathcal{E})\) generated from prefix events, i.e. the smallest σ-field containing prefix events that is closed under complement, countable unions and intersections. It means that any countable union or intersection of events is an event and the complement of any event is an event. Let \(F\subset \mathcal{F}\) be a finite or countable set of prefixes, we write \(\mathcal{E}(F)\) the event \(\bigcup_{f\in F} \mathcal{E}(f)\).

The class of sets \(\mathcal{R} = \mathcal{E} \cup \{\emptyset\} \) is a semiring of sets. It comes from two facts. Let \(f_1, f_2\in \mathcal{F}\) be two prefixes. Either \(\mathcal{E}(f_1)\) and \(\mathcal{E}(f_2)\) are disjoint, or one is contained in the other. It proves that \(\mathcal{R}\) is table by finite intersection. If \(\mathcal{E}(f_2) \subset \mathcal{E}(f_1)\) then there exists \(f_3\in \mathcal{F}\) such that \(f_2 = f_1 \cdot f_3\) and \(\mathcal{E}(f) = \bigcup_{f_4\in \mathcal{F}, |f_4|=|f_3|} \mathcal{E}(f \cdot f_4)\). It proves that \(\mathcal{E}(f_1) \setminus \mathcal{E}(f_2)\) can be written as a finite union of disjoint element of \(\mathcal{R}\).

Instead of defining the probability function \(p\) directly over \(\sigma(\mathcal{E})\), \(p\) is defined over \(\mathcal{R}\) first and then extended to \(\sigma(\mathcal{E})\) using Carathéodory’s extension theorem. \(p\) is defined on \(\mathcal{R}\) by

\(p\) is additive and σ-subadditive because the only way for the union of two disjoint elements of \(\mathcal{R}\) to be in \(\mathcal{R}\) is if one of the two is the empty set. It is also σ-finite because \(p(\Omega) = p(\mathcal{E}(\epsilon)) = (\frac{1}{n})^{0} = 1\). The function \(p\) can then be uniquely extended into a probability function over \(\sigma(\mathcal{E})\).

Note that:

The probability space \((\Omega,\sigma(\mathcal{E}),p)\) has the very pleasing property that the probability of a prefix event \(\mathcal{E}(f)\) is exactly the probability of getting the sequence \(f\) with \(|f|\) dice rolls. There is a problem though: there are outcomes for which not every side has been observed at least once. The infinite sequence \((1,\dots)\) is such an outcome.

Let \(M\) the subset of outcomes such that at least one side has not been observed, i.e. \( M = \{ \omega \in \Omega \mid \sharp \omega < n \} \). We want to know how likely \(M\) is. For any \(i \in \mathbb{N} \), let \(M_i\) the set of outcomes such at least one side has not been observed up to the \(i\)-th roll, i.e. \(M_i = \mathcal{E}(\{f \in \mathcal{F}\mid |f|=i,\ \sharp f < n\})\).

For any \(i\in \mathbb{N}\), \(M_i\) is an event because it is a finite union of events. Not observing at least one side with an infinity of rolls is equivalent to not observing this side for every \(i\)-th roll, so \(M = \bigcap_{i\in\mathbb{N}} M_i\). From the last equation, we can conclude that \(M\) is an event because it is a countable intersection of events. Furthermore, given \(i\) dice rolls, the probability of not observing a given side is \((\frac{n-1}{n})^i\) so \(p(M_i) \le n \times (\frac{n-1}{n})^i\). Note that \(M_{i+1} \subset M_i\), so \(\bigcap_{j=0}^i M_j = M_i\). We can conclude that the probability, given an infinity of dice rolls, of never observing one side (anyone) is \(0\):

Note that it does not mean these outcome are impossible. In theory, if you flip a coin endlessly, it is possible to always get head (resp. tail), but this is incredibly unlikely. Let \(\Omega' = \overline{M}\) be set of outcomes such that every side has been observed at least once. \(\Omega'\) is the complement of \(M\), written \(\overline{M}\). Its probability is then \(p(\Omega') = 1\). So for any event \(E\in\sigma(\mathcal{E})\), \(p(E) = p(E\cap\Omega') + p(E\cap M)\), but \(p(E\cap M) \le p(M) = 0\), so

Informally, it means we can assume that, in every outcome, every side of the dice are observed at least once. More precisely, we take as probability space, the restriction of \((\Omega,\sigma(\mathcal{E}),p)\) to \(\Omega'\), written \((\Omega',\sigma(\mathcal{E})|_{\Omega'},p)\).

How does the problem translates into this probability space? Remember that an outcome \(\omega \in \Omega'\) is an infinite sequence \((s_1,s_2,\dots)\) of sides \(s_i \in \mathcal{C}_n\) such that every every side is observed at some point. For any \(m \in \{0,\dots,n\}\) we define the random variable \(X_m\) as the function, from \(\Omega'\) to \(\mathbb{R}\), that maps any outcome \(\omega \in \Omega' = (s_1,s_2,\dots)\) to the first \(i\) such that \(m\) side has been observed at least once.

Note that \(X_n(\omega)\) is the number of rolls needed to observe every side of the chosen dice at least once. The average we are looking for is actually the expected value of \(X_n\). But for the expected value to defined, \(X_m\) has to be a measurable function from \((\Omega',\sigma(\mathcal{E})|_{\Omega'})\) to \((\mathbb{R},\mathcal{B}(\mathbb{R}))\). Let \(F_{m,l}\) be the set of prefixes \(f=(s_1,\dots,s_l)\) of length \(l\) such that \(l\) is the first roll for which exactly \(m\) sides have been observed at least once, i.e. \(l = \inf_i\{i \mid \sharp (s_1,\dots,s_i) = m \}\). Then

and so \(X_m\) is indeed measurable. The expected value is:

The mistake we did in the last section is now clear. We computed \(\sum_{l\in\mathbb{N}} |F_{m,l}| \times l\) instead of \(\sum_{l\in\mathbb{N}} |F_{m,l}| \times l \times (\frac{1}{n})^l\). We just have to fix the function used in the aggregation to compute the right value:

def forOneValidPrefix(sides: Int)(length: Int): BigDecimal =
  (BigDecimal(1) / sides).pow(length) * length

scala> val depth = 100000
val depth: Int = 100000

scala> val sides = 3
val sides: Int = 3

scala> val expectedValueFor100000 = aggregate(sides,depth)(forOneValidPrefix(sides))
val expectedValueFor100000: BigDecimal = 5.499999999999999999999999999999999

This time the computed value match what we observed with random experiments, a value around \(5.5\). It also match the average we got for a 6-sided fair dice:

scala> val depth = 10000
val depth: Int = 10000

scala> val sides = 6
val sides: Int = 6

scala> val expectedValueFor100000 = aggregate(sides,depth)(forOneValidPrefix(sides))
val expectedValueFor100000: BigDecimal = 14.70000000000000000000000000000001

We can actually go a bit deeper by observing that for any \(m \in \{1,\dots,n\}\), \(\mathbb{E}(X_m) = \mathbb{E}(X_{m-1}) + \mathbb{E}(X_m - X_{m-1})\):

So \(p(\mathcal{E}(F_{i+1,k+d}) | \mathcal{E}(F_{i,k})) = (\frac{i}{n})^{d-1}\times \frac{n-1}{n} \). So \(p(\mathcal{E}(F_{i+1,k+d}) | \mathcal{E}(F_{i,k})) = (\frac{i}{n})^{d-1}\times \frac{n-1}{n} \). So \(\mathbb{E}(X_{i+1} - X_i) = \sum_{d\in\mathbb{N}^*} d \times \frac{n-1}{n}\times (\frac{i}{n})^{d-1} \).

We recognize a Geometric Distribution whose probability of success is \(p' = \frac{n-i}{n}\). Its expected value is known to be \(\frac{1}{p'} = \frac{n}{n-i}\). It can be computed by

But

So

Finally we can give the formula for the expected value and check that it gives the expected values:

def expectedValue(sides: Int): Double =
  (1 to sides).map(sides.toDouble / _).sum

scala> expectedValue(6)
val res0: Double = 14.7

scala> expectedValue(3)
val res1: Double = 5.5

Understanding the Probability

Still given a \(n\)-sided fair dice \(n>0\). Let \(C \subset \mathcal{C}_n\) be a subset of the sides of the dice and \(l \in \mathbb{N}\) a non-negative integer. The event of all outcomes whose prefixes of length \(l\) do not contain any side in \(C\) is written

Note that for any subsets \(C_1\) and \(C_2\) of \(\mathcal{C}_n\) and \(l\in\mathbb{N}\), the property \(M_{n,l,C_1}\cap M_{n,l,C_1} = M_{n,l,C_1\cup C_2}\) holds and \(p(M_{n,l,C}) = (\frac{n - |C|}{n})^l = (1 - \frac{|C|}{n})^l\). Let \(A_{n,l}\) be the event of all outcomes whose prefixes of size \(l\) contain every side of the dice at least once:

We can generalize this result: given a \(n\)-sided fair dice and \(C \subset \mathcal{C}_n\) a subset of the sides of the dice. Let \(A_{n,l,C}\) be the set of outcomes whose prefixes of length \(l\) do contain only sides of \(C\) and every side of \(C\):

We found the probability of observing, in \(l\) dice rolls or less, a subset of all the sides. But \(A_{n,l,C}\) is not in general \(X_n^{-1}(\{l\})\) because outcomes in \(X_n^{-1}(\{l\})\) reach the last observed side at roll \(l\) while outcomes in \(A_{n,l}\) may have observed every side much before the \(l\)-th roll. But we can relate the two. For any side \(c \in \mathcal{C}_n\) and any non-negative integer \(i\in\mathbb{N}\), let \(R_{n,i,c}\) the event of observing the side \(c\) at roll \(i\). Let \(l\in\mathbb{N}^*\):

We need to be careful when translating this formula to avoid computation approximations to lead to very wrong answers:

def probabilityForLength(sides: Int, length: Int): BigDecimal =
  def cnk(k: Int, f: Int): BigInt =
    def dfact(n: Int, k: Int, res: BigInt = BigInt(1L)): BigInt =
      if k <= 0
      then res
      else dfact(n-1, k-1, res*n)

    dfact(f,k) / dfact(k,k-1)

  if sides == 0 || length == 0 then
    if sides == 0 && length == 0 then
      BigDecimal(1)
    else
      BigDecimal(0)
  else
    ((BigDecimal(sides - 1)/sides).pow(length - 1) +
      BigDecimal(
        (1 to (sides-1)).map { (k: Int) =>
          ( cnk(k,sides-1)
            * (if k % 2 == 0 then 1 else -1)
            * BigInt(sides - 1 - k).pow(length-1)
          )
        }.sum
      ) / BigDecimal(sides).pow(length - 1)
    )

We can check that the probability of observing all the sides of a 120-sided dice in less than 120 rolls is indeed 0:

scala> probabilityForLength(120, 13)
val res0: BigDecimal = 4E-34

scala> probabilityForLength(120, 42)
val res1: BigDecimal = 8.751991852311394833964673845157515E-34

scala> probabilityForLength(120, 99)
val res2: BigDecimal = 1.468941911574859178966522092677385E-33

scala> probabilityForLength(120, 119)
val res3: BigDecimal = 1.529470021201154499656736868919480E-33

Note that the very small numbers we get for 42, 99 and 119 rolls instead of 0 are due approximations in computing with so big and small numbers. To get a better idea of how the probability behaves we can, as usual, export it as a CSV file. Let us start by defining the probability for every length using a stream:

scala> val probaD120 =
          LazyList
            .iterate(0)(_ + 1)
            .map(length => length -> probabilityForLength(120, length))
val probaD120: LazyList[(Int, BigDecimal)] = LazyList(<not computed>)

And write this stream up to some length into a CSV file:

def (self: LazyList[(Int, BigDecimal)]) plot(depth: Int, file: String): Unit =
  import java.io._
  val pw = new PrintWriter(new File(file))
  pw.println("length;probability")
  for (length, proba) <- self.take(depth) do
    pw.printf("%d;%f\n", length, proba.toDouble)
  pw.close

scala> probaD120.plot(1500, "/tmp/d120.csv")

There is a lot of things we can do thanks to this probability like asking how many rolls we need to observe all the sides of dice 9 times out of 10. The probability of observing all the sides of the dice in exactly or less than \(l\) rolls is given by

All we need to do is transform the stream probaD120:

def [A,B,C](ll: LazyList[A])foldP(z: B)(f: (B,A) => (B,C)): LazyList[C] =
  LazyList.unfold((ll,z)) { case (l0, z0) =>
      if l0.isEmpty then
        None
      else
        val (z1,c0) = f(z0,l0.head)
        Some((c0, (l0.tail,z1)))
  }

def (self: LazyList[(Int, BigDecimal)]) cumul: LazyList[(Int, BigDecimal)] =
  self.foldP(BigDecimal(0)) { case (s, (l,p)) => (s+p, l -> (s+p)) }

scala> val distribD120 = probaD120.cumul
val distribD120: LazyList[(Int, BigDecimal)] = LazyList(<not computed>)

scala> distribD120.dropWhile(_._2 < 0.9).head._1
val res5: Int = 842

There is 90% chance that we observe all sides of the 120-sided fair dice with 842 rolls. Once again, we can get a better idea of how the distribution behaves by plotting it

scala> distribD120.plot(1500, "/tmp/d120_cumul.csv")

Conclusion

The initial question was simple:

how many rolls are needed, on average, with a \(n\) sided fair dice, to observe all of its sides.

But the answer was not! We have seen how to check, empirically, that the Scala Random.nextInt function correctly simulates a fair dice. From there we run (many) experiments to get an approximation of the answer. We experienced how easy but disastrous it can be to build a model disconnected from reality. We learned that building a valid model requires a deep understanding of the problem and the experiments. We had to put a lot of care into the construction of the model to be sure it is a valid formalization of the problem. The maths were not easy, but they were right. And in the end, maths lead us to a very simple formula. Was all this formal brutality useful? Yes, it was. The simple formula gives the exact answer and is by far the most efficient implementation. Going deeper we found how to answer more questions like the chance we have to observe all sides in \(l\) rolls or less. We even were able to get a precise idea of how the probability behaves by plotting it.

All along this journey, we used many of the new Scala 3 features among which extensions methods and Type Classes. We saw how easy they were to use and the great benefits they offer. Extensions methods let us add methods to objects without any boilerplate, Type Classes let us write generic function, etc.

I hope you enjoyed this journey as much as I loved writing it. Have a look at all the Scala 3 features. Many of them are not covered here but are truly amazing (Polymorphic Functions, Dependent Function Types, Match Types, Intersection and Union Types, etc). The list is pretty large.

Les GADTs Par l'Exemple

27 Oct 2019 - 7900 Words

Soyez les bienvenu·e·s! Cette session a le dessein de vous présenter un outil de programmation très puissant. Alors que la plupart des introductions sur le sujet commencent par une présentation de ses fondements théoriques d’une manière très formelle, nous avons choisi de vous le présenter à travers de courts exemples et des cas d’utilisation concrets.

Cet atelier est composé de trois parties. La dernière présente trois des cas d’utilisation des plus utiles. Ils forment les usages majeurs en pratique. Mais ne vous y aventurez pas sans préparation! Cette partie est la dernière pour une bonne raison: elle s’appuie massivement sur les leçons des parties précédentes. Commencez par Premier Contact, elle vous exposera, via les plus simples exemples, les idées clefs. Son but est d’ouvrir votre esprit à des manières d’utiliser les types et données que vous n’avez vraisemblablement jamais soupçonnées. Arpentez ensuite Cas d’utilisation simples et utiles: relations sur les types, pour un premier défi devant un usage pratique. Après cela seulement vous serez prêt·e pour Cas d’Utilisation Plus Avancés.

Assurez vous de lire LISEZ-MOI, cette section contient de précieuses astuces pour faciliter votre parcours.

Remerciements

Nous tenons à remercier Laure Juglaret pour ses nombreuses relectures, ses précieuses remarques et corrections.

LISEZ-MOI

Durant toute cette présentation, nous considérerons que:

• null n’existe pas!
• La réflexion au runtime n’existe pas! (c.-à-d. isInstanceOf, getClass, etc)

Cette présentation considère que ces fonctionnalités n’existent pas du tout!.

Leur utilisation n’amènera jamais à une réponse correcte aux questions..

Pour faire cet atelier vous devez disposez du nécessaire pour écrire, compiler et exécuter rapidement du code Scala. Le meilleur moyen est d’ouvrir une session interactive (R.E.P.L.). Si vous avez Scala d’installé sur votre système, vous pouvez facilement en démarrer une via la ligne de commande en exécutant le programme 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>

Pour rappel, dans une session interactive (R.E.P.L.), la commande :paste permet de copier du code dans la session et la commande :reset de repartir d’un environnement vierge.

Si vous n’avez pas Scala d’installé, vous pouvez utiliser le site https://scastie.scala-lang.org/ .

Échauffements

Cette section est un bref rappel de quelques définitions et propriétés sur les types et les valeurs.

Valeurs et Types?

Les valeurs sont les données concrètes que vos programmes manipulent comme l’entier 5, le booléen true, la chaîne "Hello World!", la fonction (x: Double) => x / 7.5, la liste List(1,2,3), etc. Il est souvent pratique de classer les valeurs en groupes. Ces groupes sont appelés des types. Par exemple:

• Int est le groupe des valeurs entières, c.-à-d. les valeurs telles que 1, -7, 19, etc.
• Boolean est le groupe contenant exactement les valeurs true et false (ni plus, ni moins!).
• String est le groupe dont les valeurs sont "Hello World!", "", "J' ❤️ les GADTs", etc.
• Double => Double est le groupe dont les valeurs sont les fonctions prenant en argument n’importe quel Double et renvoyant également un double Double.

Pour indiquer que la valeur v appartient au type (c.-à-d. groupe de valeurs) T, la notation est v : T. En Scala, tester si une valeur v appartient au type T est très simple: il suffit de taper v : T dans la session interactive (REPL):

scala> 5 : Int
res7: Int = 5

Si Scala l’accepte, alors v appartient bien au type T. Si Scala râle, ce n’est probablement pas le cas:

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

Combien de types?

Créons maintenant quelques types et quelques unes de leurs valeurs (quand cela est possible!).

class UnType

• Question 1: Combien de types la ligne class UnType définit-elle?

  Solution (cliquer pour dévoiler)

  Comme son nom le suggère, la ligne class UnType définit seulement un type, nommé UnType.

Passons maintenant à:

class UnTypePourChaque[A]

• Question 2: Combien de types la ligne class UnTypePourChaque[A] définit-elle?

  Solution (cliquer pour dévoiler)

  Comme son nom le suggère, chaque type concret A donne lieu à un type distinct UnTypePourChaque[A].

  Par exemple, une liste d’entiers n’est ni une liste de booléens, ni une liste de chaîne de caractères, ni une liste de fonctions, ni … En effet les types List[Int], List[Boolean], List[Int => Int], etc sont tous des types distincts.

  la ligne class UnTypePourChaque[A] définit un type distinct pour chaque type concret A. Il y a une infinité de types concrets A, donc une infinité de de types distincts UnTypePourChaque[A].

• Question 3: Donnez une valeur qui appartient à la fois aux types UnTypePourChaque[Int] et UnTypePourChaque[Boolean].

  Pour rappel, null n’existe pas!

  Solution (cliquer pour dévoiler)

  C’est en fait impossible. Chaque type concret A donne lieu à un type distinct UnTypePourChaque[A] qui n’a aucune valeur en commun avec les autres types de la forme UnTypePourChaque[B] avec B ≠ A.

Combien de valeurs?

En considérant le type suivant:

final abstract class PasDeValeurPourCeType

• Question 1: Donnez une valeur appartenant au type PasDeValeurPourCeType? Combien de valeurs appartiennent au type PasDeValeurPourCeType?

  Astuce (cliquer pour dévoiler)

  • Qu’est ce qu’une classe final? En quoi est-ce qu’elle diffère d’une classe normale (non finale)?
  • Qu’est ce qu’une classe abstract? En quoi est-ce qu’elle diffère d’une classe concrète?
  Solution (cliquer pour dévoiler)

  La classe PasDeValeurPourCeType est déclarée comme abstract. Cela signifie qu’il est interdit de créer des instances directes de cette classe:

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

  La seule manière de créer une instance d’une classe abstraite est de créer une une sous-classe concrète. Mais le mot clef final interdit la création de telles sous-classes:

  scala> class SousClasseConcrete extends PasDeValeurPourCeType
                                          ^
          error: illegal inheritance from final class PasDeValeurPourCeType

  Il n’existe aucun moyen de créer une instance pour PasDeValeurPourCeType.

Prenons un autre exemple:

sealed trait ExactementUneValeur
case object LaSeuleValeur extends ExactementUneValeur

• Question 2: Donnez une valeur appartenant au type ExactementUneValeur?

  Solution (cliquer pour dévoiler)

  Par définition, LaSeuleValeur est une valeur du type ExactementUneValeur.

• Question 3: Combien de valeurs appartiennent à ExactementUneValeur?

  Solution (cliquer pour dévoiler)

  Comme ci-dessus, ExactementUneValeur, étant un trait, est abstrait. Étant sealed, l’étendre en dehors de son fichier source est interdit. Donc LaSeuleValeur est la seule valeur du type ExactementUneValeur.

Premier Contact

Cette partie présente les idées clefs. Il y a en fait seulement deux idées! Vous trouverez ici des exemples épurés illustrant chacune de ces deux idées.

Cas d’Utilisation: Preuve d’une propriété

Définissons un simple sealed trait:

sealed trait ATrait[A]
case object AValue extends ATrait[Char]

• Question 1: Donnez une valeur du type ATrait[Char].

  Solution (cliquer pour dévoiler)

  Par définition, AValue est une valeur du type ATrait[Char].

• Question 2: Donnez une valeur du type ATrait[Double].

  Solution (cliquer pour dévoiler)

  Il n’existe aucun moyen d’obtenir une instance du type ATrait[Double]. Il n’existe en fait aucun moyen d’obtenir une instance de ATrait[B] pour B ≠ Char parce que la seule valeur possible est AValue qui est de type ATrait[Char].

• Question 3: Que pouvez vous conclure sur le type A si vous avez une valeur ev de type ATrait[A] (c.-à-d. ev: ATrait[A])?

  Solution (cliquer pour dévoiler)

  La seule valeur possible est AValue, donc ev == AValue. De plus AValue est de type ATrait[Char] donc A = Char.

• Question 4: Dans la session interactive (REPL), entrez le code suivant:

  def f[A](x: A, ev: ATrait[A]): Char =
    x

• Question 5: Essayez maintenant en utilisant un filtrage par motif (pattern matching) sur ev: ATrait[A]

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

  Le filtrage par motif (pattern-matching) est il exhaustif?

  Solution (cliquer pour dévoiler)

  Le filtrage par motif est exhaustif parce la seule et unique valeur possible pour ev est en fait AValue. De plus AValue est de type ATrait[Char] ce qui signifie que ev : ATrait[Char] parce que ev == AValue. Donc A = Char et x : Char.

• Question 6: Appelez f avec x = 'w' : Char.

  Solution (cliquer pour dévoiler)

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

• Question 7: Appelez f avec x = 5.2 : Double.

  Solution (cliquer pour dévoiler)

  C’est impossible parce que cela demenderait de fournir une valeur ev : ATrait[Double], ce qui n’existe pas!

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

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
  }

Cas d’Utilisation: La seule chose que je sais, est qu’il existe

Que feriez vous si vous vouliez que votre application tienne un journal d’évènements (c.-à-d. un log), mais que vous vouliez être sur qu’elle ne dépende d’aucun détail d’implémentation de la méthode de journalisation (c.-à-d. du logger), de telle manière que vous puissiez changer son implémentation sans risquer de casser votre application?

En considérant le type suivant, UnknownLogger, des méthodes de journalisation:

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

La première méthode (c.-à-d. *logger) que nous créons stocke les messages dans une String:

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

La seconde méthode les stocke dans une List[String]:

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

La troisième méthode de journalisation imprime directement les messages sur la sortie standard:

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

Notez que ces trois méthodes de journalisation ont toutes le même type (c.-à-d. UnknownLogger) mais qu’elles stockent les messages en utilisant différents types X (String, List[String] et Unit).

• Question 1: Soit v une valeur de type UnknownLogger. Clairement v doit être une instance de la classe LogWith[X] pour un certain X. Que pouvez vous dire sur le type X? Pouvez-vous deviner quel type concret est X?

  Pour rappel, il est interdit d’utiliser la réflexion au runtime! (c.-à-d. isInstanceOf, getClass, etc)

  Solution (cliquer pour dévoiler)

  Nous ne savons presque rien sur X. La seule chose que nous avons est qu’il existe au moins une valeur (v.logs) de type X. À part cela, X peut être n’importe quel type.

  Ne pas savoir quel type concret est X est très utile pour garantir que le code qui utilisera v : UnknownLogger ne dépendra pas de la nature de X. Si ce code savait que X était String par exemple, il pourrait exécuter des opérations que nous voulons interdir comme inverser la liste, ne retenir que les n premiers caractères, etc. En cachant la nature deX, nous forçons notre application à ne pas dépendre du type concret derrièreX mais de n’utiliser que la fonnction fournie v.appendMessage. Ainsi changer l’implémentation réelle de la méthode de journalisation ne cassera aucun code.

• Question 2: Écrivez la fonction def log(message: String, v: UnknownLogger): UnknownLogger qui utilise v.appendMessage pour ajouter le message au journal v.logs et retourne un nouvel UnknownLogger contenant le nouveau journal (c.-à-d. le nouveau log).

  Pour rappel, en Scala, le motif (c.-à-d. pattern) case ac : AClass[t] => est possible dans les expressions de type match/case comme alternative au motif case AClass(v) => :

  final case class AClass[A](value : A)
  
  def f[A](v: AClass[A]): A =
    v match {
      case ac : AClass[t] =>
        // La variable `t` is une variable de type
        // Le type `t` est `A`
        val r : t = ac.value
        r
    }

  Son principal avantage est d’introduire la variable de type t. Les variables de type se comportent comme des variables de motif classiques (c.-à-d. pattern variables) à l’exception prés qu’elles représentent des types et non des valeurs. Avoir t sous la main nous permet d’aider le compilateur en donnant explicitement certains types (comme ci-dessus, expliciter que r est de type t).

  Solution (cliquer pour dévoiler)

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

• Question 3: Exécutez log("Hello World", loggerStr) et log("Hello World", loggerList) et log("Hello World", loggerStdout)

  Solution (cliquer pour dévoiler)

  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)

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

Conclusion Intermédiaire

Les GADTs ne sont en fait que ceci: de simples sealed trait avec quelques case object (possiblement aucun) et quelques final case class (également possiblement aucune!). Dans les parties suivantes, nous explorerons quelques un des cas d’utilisation majeurs des GADTs.

Cas d’utilisation simples et utiles: relations sur les types

Une faculté simple mais très utile des GADTs est l’expression de relations sur les types telles que:

• Le type A est-il égal au type B?
• Le type A est-il un sous-type de B?

Notez bien que, par définition, tout type A est sous-type de lui-même (c.-à-d. A <: A), tout comme tout entier x est également inférieur ou égal à lui-même x ≤ x.

Cas d’Utilisation: Témoin d’Égalité entre Types

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

• Question 1: Donnez une valeur de type EqT[Int, Int]

  Solution (cliquer pour dévoiler)

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

• Question 2: Donnez une valeur de type EqT[String, Int]

  Solution (cliquer pour dévoiler)

  La classe Evidence est l’unique sous-classe conctrète du trait EqT et il est impossible d’en créer une autre parce que EqT est sealed. Donc une valeur v : EqT[A,B] ne peut être qu’une instance de Evidence[X] pour un certain type X, qui elle-même est de type EqT[X,X]. Ainsi il n’y a aucun moyen d’obtenir une valeur de type EqT[String, Int]

• Question 3: Soient A et B deux types (inconnus). Si je vous donne une valeur de type EqT[A,B], que pouvez-vous en déduire sur A et B?

  Solution (cliquer pour dévoiler)

  Si je vous donne une valeur v : EqT[A,B], alors vous savez que v est une instance de Evidence[X] pour un certain type X (inconnu). En effet la classe Evidence est la seule et unique sous-classe concrète du sealed trait EqT. En fait, Evidence[X] est un sous-type de EqT[X,X]. Donc v : EqT[X,X]. Les types EqT[A,B] et EqT[X,X] n’ont aucune valeur en commun si A ≠ X ou B ≠ X, donc A = X et B = X. Et donc A = B. CQFD.

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
}

Passer d’un type égal à l’autre

Si A et B sont en fait le même type, alors List[A] est également le même type que List[B], Option[A] est également le même type que Option[B], etc. De manière générale, pour n’importe quel F[_], F[A] est également le même type que F[B].

• Question 4: Écrivez la fonction def coerce[F[_],A,B](eqT: EqT[A,B])(fa: F[A]): F[B].

  Solution (cliquer pour dévoiler)

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

La bibliothèque standard de Scala définit déjà une classe, nommée =:=[A,B] (son nom est bel et bien =:=), représentant l’égalité entre types. Je vous recommande vivement de jeter un œil à sa documentation (cliquez ici). Fort heureusement, pour plus de lisibilité, Scala nous permet d’écrire A =:= B le type =:=[A,B].

Étant donné deux types A et B, avoir une instance (c.-à-d. objet) de A =:= B prouve que A et B sont en réalité le même type, tout comme pour EqT[A,B]. Pour rappel, A =:= B n’est que du sucre syntaxique pour désigner le type =:=[A,B].

Des instances de A =:= B peuvent êtres crées en utilisant la fonction (<:<).refl[X]: X =:= X (cliquer pour voir la documentation). Le “symbole” <:< est en effet un nom d’objet valide.

• Question 5: En utilisant la fonction coerce ci-dessus, écrivez la fonction def toScalaEq[A,B](eqT: EqT[A,B]): A =:= B.

  Astuce (cliquer pour dévoiler)

  def toScalaEq[A,B](eqT: EqT[A,B]): A =:= B = {
    /* Trouver une définition pour:
          - le constructeur de type `F`
          - la valeur `fa : F[A]`
    */
    type F[X] = ???
    val fa : F[A] = ???
  
    /* Telles que cet appel: */
    coerce[F,A,B](eqT)(fa) // soit de type `F[B]`
  }

  Solution (cliquer pour dévoiler)

  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: En utilisant la méthode substituteCo[F[_]](ff: F[A]): F[B] des objets de la classe A =:= B, dont la documentation est ici, écrivez la fonction def fromScalaEq[A,B](scala: A =:= B): EqT[A,B].

  Astuce (cliquer pour dévoiler)

  def fromScalaEq[A,B](scala: A =:= B): EqT[A,B] = {
    /* Trouver une définition pour:
          - le constructeur de type `F`
          - la valeur `fa : F[A]`
    */
    type F[X] = ???
    val fa : F[A] = ???
  
    /* Telles que cet appel: */
    scala.substituteCo[F](fa) // soit de type `F[B]`
  }

  Solution (cliquer pour dévoiler)

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

Cas d’Utilisation: Témoin de Sous-Typage

Dans cette section, nous voulons créer les types SubTypeOf[A,B] dont les valeurs prouvent que le type A est un sous-type de B (c.-à-d. A <: B). Une classe similaire, mais différente, est déjà définie dans la bibliothèque standard de Scala. Il s’agit de la classe <:<[A,B], qui est le plus souvent écrite A <:< B. Sa documentation est ici. Cette section étant dédiée à l’implémentation d’une variante de cette classe, veuillez ne pas utiliser <:<[A,B] pour implémenter SubTypeOf.

• Question 1: En utilisant uniquement des bornes supérieures (c.-à-d. A <: B) ou bornes inférieures (c.-à-d. A >: B) et aucune annotation de variance (c.-à-d. [+A] et [-A]), créez le trait SubTypeOf[A,B] (et tout ce qui est nécessaire) tel que:

  Il existe une valeur de type SubType[A,B] si et seulement si A est un sous-type de B (c.-à-d. A <: B).

  Pour rappel, par définition, un type A est un sous-type de lui-même (c.-à-d. A <: A).

  Pour rappel, n’utilisez pas la classe <:<[A,B].

  Solution (cliquer pour dévoiler)

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

  Remarque pour les personnes à l'aise en Scala (cliquer pour dévoiler)

  En production, il est pratique de définir SubTypeOf de la manière équivalente suivante:

  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
  }

Cas d’Utilisation: Éviter les messages d’erreur de scalac à propos des bornes non respectées

Dans cet exemple, nous voulons modéliser le régime alimentaire de certains animaux. Commençons par définir le type Food (c.-à-d. nourriture) et quelques-uns de ces sous-types:

trait Food
class Vegetable extends Food
class Fruit extends Food

et maintenant la classe représentant les animaux mangeant de la nourriture de type A (c.-à-d. Vegetable, Fruit, etc):

class AnimalEating[A <: Food]

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

Définissons une fonction comme il en existe tant en Programmation Fonctionnelle et passons lui elephant comme argument:

def dummy[F[_],A](fa: F[A]): String = "Ok!"

scala> dummy[List, Int](List(1,2,3))
res0: String = Ok!

scala> dummy[Option, Boolean](Some(true))
res1: String = Ok!

scala> dummy[AnimalEating, Vegetable](elephant)
            ^
       error: 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

• Question 1: Pourquoi scalac se plaint il?

  Solution (cliquer pour dévoiler)

  La fonction dummy requiert que son argument F, qui est un constructeur de type comme le sont List, Option, Future, etc, accepte n’importe quel type en argument afin qu’il soit toujours possible d’écrire F[A] pour n’importe quel type A. Hors AnimalEating impose que son argument soit un sous-type de Food. Donc AnimalEating ne peut être utilisé comme argument F de dummy.

Le problème est que, en définissant class AnimalEating[A <: Food], nous avons imposé à A d’être un sous-type de Food. Donc Scala, tout comme Java, nous interdit de donner à AnimalEating, en tant qu’argument A, autre chose qu’un sous-type de Food (en incluant Food lui-même):

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

Nous sommes face à un dilemme: afin d’utiliser la fonction dummy, que nous tenons beaucoup à utiliser parce c’est une fonction très utile, il nous faut supprimer la contrainte A <: Food de la définition class AnimalEating[A <: Food]. Mais nous tenons également au fait que les animaux ne mangent que de la nourriture (Food) et pas des entiers, ni des booléens et encore moins des chaînes de caractères!

• Question 2: Comment pouvez vous adapter la définition de AnimalEating telle que:

  • Il soit possible d’appeler dummy avec comme argument elephant! Nous voulons:

    scala> dummy[AnimalEating, Vegetable](elephant)
    res0: String = Ok!

  • Si A n’est pas un sous-type de Food (Food lui-même inclus), alors il doit être impossible de créer une instance de AnimalEating[A].

  • La classe AnimalEating doit rester une classe ouverte (c.-à-d. non sealed ou final)! Il doit toujours être possible pour n’importe qui, n’importe quand, de créer librement des sous-classes de AnimalEating. Bien évidemment, ces sous-classes doivent respecter les deux contraintes ci-dessus.

    Astuce (cliquer pour dévoiler)

    En Scala, Nothing est un type ne contenant aucune valeur. Pouvez vous créer une valeur de type (Nothing, Int)? Pourquoi?

    Solution (cliquer pour dévoiler)

    Si, afin de créer une instance de AnimalEating[A], nous forçons chaque méthode créant des valeurs à prendre un paramètre supplémentaire de type SubTypeOf[A, Food], alors il sera uniquement possible de créer une instance de AnimalEating[A] quand A sera un sous-type de Food:

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

    Pour créer une valeur de type AnimalEating[A], nous avons besoin d’appeler le constructeur d’AnimalEating. Pour appeler ce constructeur, il nous faut fournir ev : SubTypeOf[A, Food].

    Il nous est désormais possible d’appeler la fonction dummy sur elephant:

    scala> dummy[AnimalEating, Vegetable](elephant)
    res0: String = Ok!

    En pratique, en utilisant des implicites, le compilateur peut fournir de lui-même le paramètre ev : SubTypeOf[A, Food].

    Notez qu’il est désormais possible d’écrire le type AnimalEating[Int] mais vous ne pourrez jamais créer une valeur de ce type.

Cas d’Utilisation: Fournir les bonnes données au bon diagramme

Ce cas d’utilisation traite des méthodes pour garantir, à la compilation, que seulement les valeurs du bon type peuvent être données à une fonction donnée. L’exemple choisi est celui de la conception d’une bibliothèque de graphiques. Afin de simplifier l’exemple, nous considèrerons que notre bibliothèque n’implémente que deux types de graphique: des camemberts (c.-à-d. pie charts) et des graphiques dit XY (c.-à-d. XY charts). Cela s’écrit en Scala via l’énumération:

sealed trait ChartType
case object PieChart extends ChartType
case object XYChart extends ChartType

Bien évidemment les camemberts (Pie) et graphiques XY s’appuient sur des jeux de données de nature différente. Encore une fois, pour simplifier, nous considèrerons que les deux types de données sont PieData pour les camemberts et XYData pour les graphiques XY:

class PieData
class XYData

Un camembert (PieChart) n’affiche que des données PieData, alors qu’un graphique XY (XYChart) n’affiche que des données XYData. Voici, grandement simplifiée, la fonction d’affichage draw:

def draw[A](chartType: ChartType)(data: A): Unit =
  chartType match {
    case PieChart =>
      val pieData = data.asInstanceOf[PieData]
      // Faire des trucs pour tracer les données pieData
      ()
    case XYChart =>
      val xyData = data.asInstanceOf[XYData]
      // Faire des trucs pour tracer les données xyData
      ()
  }

Cette fonction repose sur l’hypothèse que l’utilisateur·rice n’appellera la fonction draw que sur le bon type de données. Quand chartType vaut PieChart, la fonction présuppose, via data.asInstanceOf[PieData] que data est en fait du type PieData. Et quand chartType vaut XYChart, elle présuppose que data est en fait de type XYData.

Le problème est que ces suppositions reposent sur l’idée que les utilisateurs·rices et/ou développeurs·euses s’assureront toujours que ces hypothèses soient bien respectées. Mais rien n’empêche quelqu’un·e d’appeler draw sur un camembert (PieChart) avec des données de type XYData (ou le contraire), faisant planter le système misérablement en production!

scala> draw(PieChart)(new XYData)
java.lang.ClassCastException: XYData cannot be cast to PieData
  at .draw(<pastie>:11)
  ... 28 elided

En tant que développeurs·euses, nous savons que les erreurs, ça arrive! Nous voulons un moyen d’empêcher ces bogues ennuyeux de survenir en production! Nous voulons imposer, à la compilation, que seulement deux scenarii soit possibles:

• Quand draw est appelée avec chartType == PieChart: l’argument data doit être de type PieData
• Quand draw est appelée avec chartType == XYChart: l’argument data doit être de type XYData.

Pour rappel, ces deux contraintes doivent être vérifiées à la compilation!

• Question 1: Adaptez les définitions de ChartType, PieChart, XYChart et draw telles que:

  • Tout scenario différent des deux ci-dessus fera échouer la compilation sur une erreur de type.

  • ChartType doit toujours être un sealed trait. Mais il est autorisé à prendre des paramètres de type (c.-à-d. generics).

  • PieChart et XYChar doivent toujours être des case object et ils doivent toujours étendre ChartType.

  • Les déclarations de ChartType, PieChart et XYChar ne doivent pas avoir de corps du tout (c.-à-d. il ne doit pas y avoir d’accolades { ... } dans leurs déclarations);

  Astuce (cliquer pour dévoiler)

  Le code ressemble à ceci:

  sealed trait ChartType[/*METTRE LES GENERICS ICI*/]
  case object PieChart extends ChartType[/*Il y a quelque chose à écrire ici*/]
  case object XYChart extends ChartType[/*Il y a quelque chose à écrire ici aussi*/]
  
  def draw[A](chartType: ChartType[/*Ecrire quelque chose ici*/])(data: A): Unit =
   chartType match {
      case PieChart =>
        val pieData : PieData = data
        ()
      case XYChart =>
        val xyData: XYData = data
        ()
      }

  Solution (cliquer pour dévoiler)

  sealed trait ChartType[A]
  case object PieChart extends ChartType[PieData]
  case object XYChart extends ChartType[XYData]
  
  def draw[A](chartType: ChartType[A])(data: A): Unit =
   chartType match {
      case PieChart =>
        val pieData : PieData = data
        ()
      case XYChart =>
        val xyData: XYData = data
        ()
      }

Vous pouvez maintenant dormir sur vos deux oreilles avec l’assurance que votre code en production ne plantera pas à cause d’une entrée non conforme à cet endroit 😉

Cas d’Utilisation Plus Avancés

Maintenant que vous avez vu ce que sont les GADTs et comment les utiliser dans la vie de tous les jours, vous êtes prêt·e pour les cas d’utilisations plus conséquents ci-dessous. Il y en a trois. Chacun illustre une manière différente d’utiliser la puissance des GADTs. Le premier traite de l’expression d’effets, ce qui est très largement utilisé dans chaque monade IO populaire ou effets algébriques. Ne vous inquiétez pas de ne pas savoir ce que sont ces derniers, cette section l’expliquera. Le second s’attache à montrer comment garantir des propriétés dans le système de types. Ce point est illustré à travers l’exemple de l’accommodation des techniques issues de la programmation fonctionnelle aux contraintes issues des bases de données. Le troisième offre une manière plus simple de travailler avec des implicites.

Cas d’Utilisation: Les Effets!

Ce qui est appelé un effet est parfois juste une interface déclarant quelques fonctions dépourvues d’implémentation. Par exemple nous pouvons définir le trait ci-dessous. Notez qu’aucune de ces fonctions n’a d’implémentation.

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

Les implémentations de ces interfaces (traits) sont données ailleurs, et il peut en avoir beaucoup! Cela est utile quand il est désirable de changer facilement d’implémentation:

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

Une manière équivalente de définir ExampleEffectSig est via un sealed trait muni de quelques final case class (peut-être aucune!) et/ou quelques case object (peut-être aucun!):

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]

De nouveau, nous avons des déclarations ne fournissant aucune implémentation! De nouveau, leurs implémentations peuvent être fournies ailleurs et il peut en avoir beaucoup:

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

Prenons un effet plus réaliste ainsi qu’une de ses implémentations possibles:

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: Tout comme ExampleEffect est l’équivalent de ExampleEffectSig via la définition d’un sealed trait muni de quelques final case class et case object, écrivez l’équivalent de EffectSig de la même manière. Appelez ce trait Effect.

  Solution (cliquer pour dévoiler)

  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: Écrivez la fonction def run[A](effect: Effect[A]): A qui reproduit l’implémentation de EffectImpl tout comme runExampleEffect reproduit celle de ExampleEffectImpl.

  Solution (cliquer pour dévoiler)

  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
    }

Le type Effect[A] déclare des effets intéressants (CurrentTimeMillis, PrintLn et Mesure) mais pour être réellement utile, il doit être possible de chaîner ces effets! Pour ce faire, nous voulons pouvoir disposer des deux fonctions suivantes:

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

De nouveau, nous ne nous intéressons pas à leurs implémentations. Tout ce que nous voulons, pour le moment, est déclarer ces deux opérations de la même manière que nous avons déclaré CurrentTimeMillis, PrintLn et Mesure.

• Question 3: Ajoutez deux final case classes, Pure et FlatMap, à Effect[A] déclarant ces deux opérations.

  Solution (cliquer pour dévoiler)

  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: Adaptez la fonction run pour gérer ces deux nouveaux cas.

  Solution (cliquer pour dévoiler)

  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: Ajoutez les deux méthodes suivantes au trait Effect[A] pour obtenir:

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

  Et exécutez le code suivant pour voir s’il fonctionne:

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

  Solution (cliquer pour dévoiler)

  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 ()

  En exécutant run(effect1) on obtient:

  scala> run(effect1)
  The current time is 1569773175010