highSchoolEquation.scala

/***************************************************************
Just a small example of Algebraic Data Type (ADT) use
to show why they are called "algebraic".

This is a good exercice to check that you understand
the basics of ADT correctly.

Note: Run-it with Dotty (Scala 3) version >= 0.22

dotr -indent -new-syntax -strict -Yerased-terms -Yexplicit-nulls
*/

/** Generates Random values.
    Used for tests
  */
trait RandomValue[A]
  def next(): A

/** Means that the types A and B are "equal". Here "equal" means
  * there is a 1-to-1 correspondance between values of A and B.
  *
  * More formally, for any `a:A` and `b:B` :
  * - from(to(b)) == b
  * - to(from(a)) == a
  *
  * More concretely, it means that:
  * - for any value `a:A`, there is one and only one value `b:B` such that `a == to(b)`
  *   - proof such a `b` exists: take `b == from(a)`.
  *   - proof such a `b` is unique: if `from(b1) == a == from(b2)` then `b1 == to(a) == b2`
  * - for any value `b:B`, there is one and only one value `a:A` such that `b == from(a)`
  *   - proof such a `a` exists: take `a == to(b)`.
  *   - proof such a `a` is unique: if `to(a1) == b == to(a2)` then `a1 == from(b) == a2`
  */
@scala.annotation.alpha("OneOneCorrespondance")
trait ===[A,B]
  def from(a:A): B
  def to(b:B): A

  /** A random test to check the above properties (see Propety Based Testing) */
  final def checkLaws(numberOfTests: Long)(using RandomValue[A], RandomValue[B]): Unit =
    for i <- 1L to numberOfTests
    do
      val a:A = RandomValue[A]()
      assert(to(from(a)) == a, s"from(to($a)) == ${to(from(a))} != $a")

      val b:B = RandomValue[B]()
      assert(from(to(b)) == b, s"to(from($b)) == ${from(to(b))} != $b")

/* Some notations to ease reading ;)
 * Actually these notations will make a lot of sense
 * just a few lines below.
 */
@scala.annotation.alpha("sumType")
type +[A,B] = Either[A,B] // You will understand why `Either[A,B]` is called a "sum type"
@scala.annotation.alpha("productType")
type *[A,B] = (A,B)       // You will understand why `(A,B)` is called a "product type"
type square[A] = A * A    // Just to say that A² = A * A
type _2 = Boolean         // Remember that `Boolean` has exactly two values: true and false!

/* Just the classic equation from High School you probably know for a long time ;)
    (a+b)² = a² + 2*a*b + b²
*/
def highSchoolEquation[A,B]: square[A + B] === square[A] + _2*A*B + square[B] =
  new (square[A + B] === square[A] + _2 * A * B + square[B]) {
    def from(lhs: square[A + B]): square[A] + _2 * A * B + square[B] =
      lhs match {
        case (Left(a1) , Left(a2) ) => Left(Left((a1,a2)))
        case (Left(a)  , Right(b) ) => Left(Right((true , a), b))
        case (Right(b) , Left(a)  ) => Left(Right((false, a), b))
        case (Right(b1), Right(b2)) => Right((b1,b2))
      }
    
    def to(rhs: square[A] + _2 * A * B + square[B]): square[A + B] =
      rhs match {
        case Left(Left((a1,a2)))        => (Left(a1) , Left(a2) ) 
        case Left(Right((true , a), b)) => (Left(a)  , Right(b) )
        case Left(Right((false, a), b)) => (Right(b) , Left(a)  )
        case Right((b1,b2))             => (Right(b1), Right(b2))
      }
  }


/*********************
 * Testing Time ! :) *
 *********************/

highSchoolEquation[Int,String].checkLaws(1000000)

/**************************************************************

  !!! EXPLANATIONS !!!

  Remember that we consider that two types A and B are "equal" if there
  is 1-to-1 correspondance between values of A and B. For example, in the JVM,
  a value of type int is equivalent to 4 bytes (because an int
  is made of 32 bits, see https://docs.oracle.com/javase/tutorial/java/nutsandbolts/datatypes.html)

  It implies that we can can always convert back and forth
  between `Int` and `(Byte,Byte,Byte,Byte)`:
*/

object AnIntIs4Bytes extends (Int === (Byte,Byte,Byte,Byte))
  def from(s: Int): (Byte,Byte,Byte,Byte) =
    ( ((s >>> 3*8) & 0xFF).toByte,
      ((s >>> 2*8) & 0xFF).toByte,
      ((s >>> 1*8) & 0xFF).toByte,
      ( s          & 0xFF).toByte
    )

  def to(_4bytes: (Byte,Byte,Byte,Byte)): Int =
    val (b3,b2,b1,b0) = _4bytes
    ((b3.toInt & 0xFF) << 3*8) |
    ((b2.toInt & 0xFF) << 2*8) |
    ((b1.toInt & 0xFF) <<   8) |
     (b0.toInt & 0xFF)

// Let's check that `from(to(a)) == a` and `to(from(b)) == b`
AnIntIs4Bytes.checkLaws(1000000)

/*
  To give some insight about why the "equality" between types:
    square[A + B] === square[A] + _2*A*B + square[B]
  is close to the high school equation:
    (a+b)² = a² + 2*a*b + b²
  let's consider the "size" of a type as the number of its values
  (at least for types that do not have too many values ;) )
*/

trait Size[A]
  val size: Long

object Size
  inline def apply[A](using ev: Size[A]): Long = ev.size

given Size[Nothing]
  val size: Long = 0 // No values

given Size[Unit]
  val size: Long = 1 // One value: ()

given Size[Boolean]
  val size: Long = 2 // true and false

/**  Here is one of the reason why `Either` is called a "sum type". */
given sizeEither[A,B](using Size[A], Size[B]) as Size[A + B]
  val size: Long = Size[A] + Size[B]

/** Here is one of the reason why `(A,B)` is called a "product type". */
given sizePair[A,B](using Size[A], Size[B]) as Size[A * B]
  val size: Long = Size[A] * Size[B]

assert(Size[square[Nothing + Unit]]                           == 1) // = (0 + 1)²
assert(Size[square[Nothing] + _2*Nothing*Unit + square[Unit]] == 1) // = 0² + 2*0*1 + 1²

assert(Size[square[Unit + Boolean]]                           == 9) // = (1 + 2)²
assert(Size[square[Unit] + _2*Unit*Boolean + square[Boolean]] == 9) // = 1² + 2*1*2 + 2²

def testSize[A,B](erased equality: A === B)(using Size[A], Size[B]): Unit =
  assert(Size[A] == Size[B], s"Size[A] == ${Size[A]} != ${Size[B]} == Size[B]")

testSize(highSchoolEquation[Nothing, Nothing])
testSize(highSchoolEquation[Nothing, Boolean])
testSize(highSchoolEquation[Unit   , Nothing])
testSize(highSchoolEquation[Unit   , Unit   ])
testSize(highSchoolEquation[Boolean, Nothing])
testSize(highSchoolEquation[Boolean, Unit   ])
testSize(highSchoolEquation[Boolean, Boolean])

/**************************************************************

  !!! Helpers, NO NEED TO READ PAST HERE !!!


Just some code to automate random generation of values.
You don't need to read it, it is not related to the subject
but needed to run the tests.
*/
object RandomValue
  inline def apply[A]()(using ev: RandomValue[A]): A = ev.next()

  import scala.util.Random
  
  given RandomValue[Int]
    def next(): Int = Random.nextInt()

  given RandomValue[String]
    def next(): String = Random.nextString(5)

  given RandomValue[_2]
    def next(): _2 = Random.nextBoolean()

  given rndAdd[A,B] (using RandomValue[A], RandomValue[B]) as RandomValue[A + B]
    def next(): A + B =
      if RandomValue[_2]()
      then Left(RandomValue[A]())
      else Right(RandomValue[B]())

  given rndMult[A,B] (using RandomValue[A], RandomValue[B]) as RandomValue[A * B]
    def next(): A * B = (RandomValue[A](), RandomValue[B]())

  given RandomValue[(Byte,Byte,Byte,Byte)]
    def next(): (Byte,Byte,Byte,Byte) =
      val array = Random.nextBytes(4)
      (array(0), array(1), array(2), array(3))