Advanced Scala: ADTs, modules and type classes

1. On specification and modelling

The chapter opens by recalling the two notions that justify the whole course, and by connecting them to programming languages.

A software model is defined as "an informative representation of a software system": it represents the shape of the concepts to capture, and a selection of what to neglect. The second half of the sentence is the part to remember: models always neglect something, otherwise they would be the system itself. And models that capture behaviour are actually systems, possibly parts of an actual system: they may be somewhat executable, where "executable" can mean emulation, simulation or animation.

How does one achieve the combined use? The deck contrasts two approaches. The transformation-based (classical) MDE approach goes from model to code by model-to-code transformations, possibly in multiple steps. The language-based (agile) MDE approach, which this chapter follows, uses languages that encompass the whole spectrum from specification to implementation. For that to work, a programming language must offer four features, each justified by an MDE concern:

Scala is presented as a natural choice for this job, while the deck notes that other high-level modern languages could be used as well. The specific goals of the lecture are to introduce or recap Scala mechanisms that the rest of the course will use, to pave the way towards the edge of advanced programming, and to introduce additional verification techniques. The progression of the deck is: dealing with abstract data types (functions, methods, algebraic data types, alias and opaque types, modules as strategies); dealing with contextual programming (contextual abstractions, ad-hoc polymorphism and type classes); the ScalaCheck tool as an application of property-based verification; and pervasive declarativity through monads, up to a fully declarative MVC application.

2. A very brief FP-Scala primer

Scala is a strongly typed, sophisticated and scalable language that mixes OOP and FP, although the course uses it for functional programming; the deck adds that ideally any Scala API can admit a Java facade. Three uses are named: as a powerful declarative language (functions, modules, types, property checking, monadic constructions); for DSL support, since flexible syntax supports the language-oriented engineering of models; and for specifying system behaviour, capturing the constraints and capabilities of software components.

Functions, modules and flexible syntax

A module is just a set of definitions. The first example packs the mechanisms used all over the course: recursion with pattern matching, currying, records, extension methods, and the flexible syntax that makes method calls read like DSL statements.

object Functions extends App:

  // a function (i.e. method), using recursion and case-match
  def factorial(n: Int): Int = n match
    case 0 | 1 => 1
    case _     => n * factorial(n - 1)

  println(factorial(5)) // 120

  // a function (i.e. method), using currying, and passing a function
  def applyManyTimes[A](initial: A, n: Int)(f: A => A): A = n match
    case 0 => initial
    case _ => applyManyTimes(f(initial), n - 1)(f)

  println(applyManyTimes(0, 10)(i => i + 2)) // 20
  println(applyManyTimes(0, 10)(_ + 2))      // equivalent formulation

  // a record data type
  case class Point2D(x: Double, y: Double)

  // using extension method
  extension (p: Point2D) def multiply(d: Double): Point2D = p match
    case Point2D(x, y) => Point2D(d * x, d * y)

  // flexible syntax for method calls
  println(multiply(Point2D(10, 20))(1.5))     // standard, with currying
  println(Point2D(10, 20).multiply(1.5))      // OO style
  println(Point2D(10, 20) multiply 1.5)       // binary operator style
  println:                                     // context-oriented
    Point2D(10, 20).multiply:
      1.5

The deck shows the same program in Java 21+ using switch expressions, record types and static methods: the point is not that Scala is exotic, but that these mechanisms are now mainstream, and Scala lets them compose. The Java version is not reproduced here; the equivalence is the lesson.

Functional data types: Optional and Sequence

The primer then builds two small data types with enum, the functional-mechanisms toolbox the chapter will reuse: modules as sets of definitions, algebraic (sum and product) data types, genericity, functions and methods, pattern matching, recursion, and extension methods.

object Optionals:

  enum Optional[A]:
    case Just(a: A)
    case None() // here parens are needed because of genericity

  object Optional:

    extension [A](opt: Optional[A])
      def isEmpty(): Boolean = opt match
        case None() => true
        case _      => false

      def orElse[B >: A](orElse: B): B = opt match
        case Just(a) => a
        case _       => orElse

      def map[B](f: A => B): Optional[B] = opt match
        case Just(a) => Just(f(a))
        case _       => None()

The notable case is sequences, i.e. lists, as a recursively defined algebraic data type with extension methods that are structural recursions over it.

object Sequences:

  enum Sequence[E]:
    case Cons(head: E, tail: Sequence[E])
    case Nil()

  object Sequence:

    def of[A](n: Int, a: A): Sequence[A] =
      if (n == 0) then Nil[A]() else Cons(a, of(n - 1, a))

    extension (s: Sequence[Int])
      def sum: Int = s match
        case Cons(h, t) => h + t.sum
        case _          => 0

    extension [A](s: Sequence[A])

      def map[B](mapper: A => B): Sequence[B] = s match
        case Cons(h, t) => Cons(mapper(h), t.map(mapper))
        case Nil()      => Nil()

      def filter(pred: A => Boolean): Sequence[A] = s match
        case Cons(h, t) if pred(h) => Cons(h, t.filter(pred))
        case Cons(_, t)            => t.filter(pred)
        case Nil()                 => Nil()

These little data types are not just examples: they are the models that the rest of the chapter and the next one will test, extend and compose. The deck immediately shows them under test in ScalaTest, with one test block per operation.

import org.scalatest.funsuite.AnyFunSuite
import org.scalatest.matchers.should.Matchers.*

import Sequences.*
import Sequence.*

class SequenceTest extends AnyFunSuite:

  test("Sequence correctly sums"):
    Cons(10, Cons(20, Cons(30, Nil()))).sum shouldBe 60
    Nil().sum shouldBe 0

  test("Sequence correctly maps"):
    Cons(10, Cons(20, Nil())).map(_ + 1) shouldBe Cons(11, Cons(21, Nil()))
    Cons(10, Cons(20, Nil())).map(_.toString) shouldBe Cons("10", Cons("20", Nil()))
    Nil[Int]().map(_ + 1) shouldBe Nil()

  test("Sequence correctly filters"):
    Cons(10, Cons(20, Nil())).filter(_ <= 10) shouldBe Cons(10, Nil())
    Cons(10, Cons(20, Nil())).filter(_ <= 9) shouldBe Nil()
    Nil[Int]().filter(_ <= 10) shouldBe Nil()

  test("Sequence correctly creates with of"):
    Sequence.of(3, "a") shouldBe Cons("a", Cons("a", Cons("a", Nil())))
    Sequence.of(0, 10) shouldBe Nil()

3. Abstract data types: specification by opacity

Abstract data types (ADTs) are introduced as a cornerstone of programming and software engineering: define a type by name + operations + constructors, abstracting and hiding concrete implementations, which could be replaced one another. The idea is that a module can define abstract types and make their concretion opaque to users, and then provide constructors and operations (as methods) with known mutual coherence.

The construct that realises opacity in Scala 3 is an alias type with opaqueness: inside object O, write opaque type T = TImpl, with genericity if needed. From the outside, the association of T to TImpl is invisible.

An ADT specification is a mini-language

The deck specifies the ADT of lists in a (semi-)formal language, to be used at design time. Note the four compartments — type, constructors, operations, axioms — and that the axioms are equations relating operations to constructors.

type:
  List[A]

constructors:
  cons : A x List[A] => List[A]
  nil  : List[A]

operations:
  map[B]    : List[A] x (A => B) => List[B]
  concat    : List[A] x List[A] => List[A]

axioms:
  map(nil, f)           = nil
  map(cons(h, t), f)    = cons(f(h), map(t, f))
  concat(nil, l)        = l
  concat(cons(h, t), l) = cons(h, concat(t, l))

SequenceADT: an opaque implementation

The specification above is realised with an opaque type whose implementation is a private enum. The users of the module see only the constructors and the operations.

And here is the decisive property of opacity: because Sequence is defined opaque, a client cannot even write a Cons directly, and cannot pattern-match on the representation. The usage example shows that the only way to build a value is through cons and nil.

SetADT: an ADT backed by algebraic sequences

The second example reuses the algebraic Sequence as the hidden representation of a set ADT, with fromSequence removing duplicates as it copies, and the usual set operations.

object SetADT:
  opaque type Set[A] = Sequence[A]

  def fromSequence[A](seq: Sequence[A]): Set[A] = seq match
    case Cons(h, t) => Cons(h, fromSequence(t.remove(h)))
    case Nil()      => Nil()

  def union[A](s1: Set[A], s2: Set[A]): Set[A] = s2 match
    case Cons(h, t) => Cons(h, union(s1.remove(h), t))
    case Nil()      => s1

  def intersection[A](s1: Set[A], s2: Set[A]): Set[A] = s1 match
    case Cons(h, t) if s2.contains(h) => Cons(h, intersection(t, s2.remove(h)))
    case Cons(_, t) => intersection(t, s2)
    case Nil()      => Nil()

  extension [A](s: Set[A])
    def contains(a: A): Boolean = s match
      case Cons(h, t) if h == a => true
      case Cons(_, t)           => t.contains(a)
      case Nil()                => false
    def remove(a: A): Set[A] = s.filter(_ != a)
    def toSequence(): Sequence[A] = s

@main def trySetADT =
  import SetADT.*
  val s1: Set[Int] = fromSequence(Cons(10, Cons(20, Cons(10, Cons(30, Nil())))))
  val s2: Set[Int] = fromSequence(Cons(10, Cons(11, Nil())))
  // val s3: Set[Int] = Cons(10, Nil())  // because Set is defined opaque
  println(s1.toSequence())              // (10, 20, 30)
  println(s2.toSequence())              // (10, 11)
  println(union(s1, s2).toSequence())   // (10, 20, 30, 11)
  println(intersection(s1, s2).toSequence()) // (10)

The commented line is the whole lesson in miniature: the user of the ADT cannot say Cons(10, Nil()) for a Set, because the association to the representation is invisible. fromSequence(Cons(10, ...)) works only because fromSequence lives inside the module.

ADTs versus algebraic data types

The deck closes the section with an honest comparison, because the course uses both styles.

From this point on, the deck assumes the algebraic data types version for sequences and streams, while the rest of the lecture keeps discussing from ADTs — and it is the ADT route that leads to type classes, which is precisely where the chapter is heading.

4. Module types by traits

The next step separates the concept of a module from its implementation: modules can be given a type, and many different implementations of the same module type may exist. The implications are stated as a list worth memorising:

• we can provide many implementations of a given module, trading off various aspects;
• this allows passing module implementations to functions to make them more abstract;
• an application may decide which implementation to use each time;
• it is very useful in ADTs;
• ADT axioms could become properties to hold in any implementation — the sentence that connects this section to property-based testing.

The constructs are minimal: a trait ModuleType with method signatures, an object ModuleImpl extends ModuleType, and functions that take the module type as a parameter.

MathModule: two implementations, one contract

object MathModules:

  // type of a module
  trait MathModuleType:
    def factorial(n: Int): Int
    def exp(base: Double, power: Int): Double

  // non-tail recursive solutions without input checks
  object BasicMathModule extends MathModuleType:

    override def factorial(n: Int): Int =
      if n == 0 then 1 else n * factorial(n - 1)

    override def exp(base: Double, power: Int): Double =
      if power == 0 then 1 else base * exp(base, power - 1)

  object ProductionMathModule extends MathModuleType:

    override def factorial(n: Int): Int =
      @scala.annotation.tailrec
      def _fact(n: Int, temp: Int): Int =
        if n == 0 then temp else _fact(n - 1, temp * n)
      n match
        case _ if n >= 0 => _fact(n, 1)

    override def exp(base: Double, power: Int): Double =
      @scala.annotation.tailrec
      def _exp(p: Int, temp: Double): Double =
        if p == 0 then temp else _exp(p - 1, temp * base)
      power match
        case _ if base >= 0 => _exp(power, 1)

The two implementations trade off aspects: the basic one is direct but recurses non-tail-recursively and performs no input checks; the production one is tail-recursive and guards its inputs. The client, however, does not care which one it gets: it programs against the module type.

@main def tryMathModule =
  import MathModules.*

  // probability of having x successes over n trials, where each success has prob. p
  // abstracting from specific implementation of the math module
  def binomialProbability(mm: MathModuleType)(n: Int, x: Int, p: Double): Double =
    mm.factorial(n) / mm.factorial(x) / mm.factorial(n - x) *
      mm.exp(p, x) * mm.exp(1 - p, n - x)

  // probability of 6 heads on 10 coin tosses
  println:
    binomialProbability(BasicMathModule)(10, 6, 0.5)
  println:
    binomialProbability(ProductionMathModule)(10, 6, 0.5)

SequenceADT as a module type

The same pattern applied to the sequence ADT yields a module type that includes the abstract type Sequence[A] member, and two implementations: a direct one over a private enum, and a "smart" one backed by the standard library List.

object Sequences:

  trait SequenceADT:
    type Sequence[A]
    def cons[A](a: A, s: Sequence[A]): Sequence[A]
    def nil[A](): Sequence[A]
    def map[A, B](s1: Sequence[A], f: A => B): Sequence[B]
    def concat[A](s1: Sequence[A], s2: Sequence[A]): Sequence[A]

  object BasicSequenceADT extends SequenceADT:
    private enum SequenceImpl[A]:
      case Cons(a: A, t: Sequence[A])
      case Nil()
    import SequenceImpl.*

    opaque type Sequence[A] = SequenceImpl[A]

    override def cons[A](a: A, s: Sequence[A]) = Cons(a, s)
    override def nil[A](): Sequence[A] = Nil()

    override def concat[A](s1: Sequence[A], s2: Sequence[A]) = s1 match
      case Cons(a, s) => Cons(a, concat(s, s2))
      case _          => s2

    override def map[A, B](s1: Sequence[A], f: A => B) = s1 match
      case Cons(a, s) => Cons(f(a), map(s, f))
      case _          => Nil()

  object ScalaListSequenceADT extends SequenceADT:
    opaque type Sequence[A] = List[A]

    override def cons[A](a: A, s: Sequence[A]) = a :: s
    override def nil[A](): Sequence[A] = List()
    override def concat[A](s1: Sequence[A], s2: Sequence[A]) = s1 ++ s2
    override def map[A, B](s1: Sequence[A], f: A => B): Sequence[B] = s1.map(f)

Usage is where the abstraction pays: each implementation can be imported, and a function can be written once against the module type and applied to both.

@main def trySequencesADTModule =
  import Sequences.*

  val basicSequenceADT: SequenceADT = BasicSequenceADT
  val scalaListSequenceADT: SequenceADT = ScalaListSequenceADT

  {
    import basicSequenceADT.*
    val s1: Sequence[Int] = cons(10, cons(20, cons(30, nil())))
    println(concat(s1, s1))   // (10, 20, 30, 10, 20, 30)
    println(map(s1, _ >= 20)) // (false, true, true)
  }
  {
    import scalaListSequenceADT.*
    val s2: Sequence[Int] = cons(10, cons(20, cons(30, nil())))
    println(concat(s2, s2))   // (10, 20, 30, 10, 20, 30)
    println(map(s2, _ >= 20)) // (20, 30)
  }

  def sequenceOps(sADT: SequenceADT): Unit =
    import sADT.*
    val s1: Sequence[Int] = cons(10, cons(20, cons(30, nil())))
    println(concat(s1, s1))       // (10, 20, 30, 10, 20, 30)
    println(map(s1, _ >= 20))     // (false, true, true)

  sequenceOps(BasicSequenceADT)
  sequenceOps(ScalaListSequenceADT)

5. Contextual abstraction: given and using

Contextual abstraction is the idea that certain inputs of a function are actually just "context", so one might want to provide implicit ways of defining and passing them. The deck draws three implications:

• Programming: one might see OOP (the state of an object) as precisely one way of addressing this problem; contextual abstraction makes it easier to support additional arguments and strategies to methods; and it is the base for type classes and ad-hoc polymorphism, seen next.
• Software engineering: it is key to declarativity — you specify abstract behaviour, and key "platform" details are just context.

The constructs are a pair: a using clause marks parameters as contextual, and a given clause defines canonical terms that the compiler can pass implicitly.

A functional strategy: ordering as a plain parameter

The running example is max over a sequence, which needs a strategy for ordering. First version: the ordering is a plain curried parameter.

def max[T](seq: Sequence[T])(ordering: (T, T) => Boolean): T = seq match
  case Cons(h1, Cons(h2, t)) =>
    val m = max(Cons(h2, t))(ordering)
    if ordering(h1, m) then h1 else m
  case Cons(h1, Nil()) => h1

@main def tryContextualParameters() =
  // input and context are passed in the same way
  println:
    max(Cons(10, Cons(30, Cons(20, Nil()))))(_ > _)   // 30
  println:
    max(Cons(10, Cons(30, Cons(20, Nil()))))(_ < _)   // 10

A module strategy: ordering as a module type

Second version: the strategy becomes a module type, so that the ordering logic lives in a named, reusable object.

trait OrderingModule[T]:
  def greater(t1: T, t2: T): Boolean

def max[T](seq: Sequence[T])(ordering: OrderingModule[T]): T = seq match
  case Cons(h1, Cons(h2, t)) =>
    val m = max(Cons(h2, t))(ordering)
    if ordering.greater(h1, m) then h1 else m
  case Cons(h1, Nil()) => h1

object MyStandardIntOrdering extends OrderingModule[Int]:
  def greater(t1: Int, t2: Int): Boolean = t1 > t2

object MyStandardStringOrdering extends OrderingModule[String]:
  def greater(t1: String, t2: String): Boolean = t1 < t2

Denoting contextual arguments: the using clause

Third version: the ordering becomes a contextual parameter. It is still passed explicitly, but the syntax marks it as context, and recursive calls re-pass it with using.

def max[T](seq: Sequence[T])(using ordering: OrderingModule[T]): T = seq match
  case Cons(h1, Cons(h2, t)) =>
    val m = max(Cons(h2, t))(using ordering)
    if ordering.greater(h1, m) then h1 else m
  case Cons(h1, Nil()) => h1

@main def tryUsingContextualParameters =
  println:
    max(Cons(10, Cons(30, Cons(20, Nil()))))(using MyStandardIntOrdering)
  println:
    max(Cons("10", Cons("30", Cons("20", Nil()))))(using MyStandardStringOrdering)

Defining canonical terms: the given clause

Fourth and final version: canonical terms are declared with given, and the call sites stop mentioning the context altogether. Note the two syntaxes: a given can reuse a previous definition, or be defined on-site with a with block.

object GivenContextualParameters:
  import UsingContextualParameters.*

  // defining a canonical term using a previous definition
  given OrderingModule[Int] = MyStandardIntOrdering

  // defining a canonical term on-site: an alternate syntax
  given OrderingModule[String] with
    def greater(t1: String, t2: String): Boolean = t1 < t2

  // those given are here "in scope"
  @main def tryGivenContextualParameters =
    println:
      max(Cons(10, Cons(30, Cons(20, Nil()))))
    println:
      max(Cons("10", Cons("30", Cons("20", Nil()))))

@main def tryImportGiven =
  import UsingContextualParameters.*
  // importing all givens
  import GivenContextualParameters.given
  // importing a specific given
  // import GivenContextualParameters.g
  // importing just * would not work!

  println:
    max(Cons(10, Cons(30, Cons(20, Nil()))))

  val ord = summon[OrderingModule[Int]] // gives MyStandardIntOrdering

Two details are easy to miss and worth the exam: importing just * does not bring givens into scope — you need .given (or name the specific given); and summon[OrderingModule[Int]] recovers the canonical term currently in scope, which is the primitive that type classes will use.

6. Type classes: ad-hoc polymorphism by context bounds

A context bound is a constraint on a type variable for generic methods, stating that an instantiation is admissible if a given (generic) context for it is available. The deck draws out the implications:

• it is actually very similar to a using clause taking a Ctx[T] parameter;
• such a context Ctx[_] can be interpreted as an "a posteriori" extension of type T — namely, a type class;
• it is a programmable way of supporting so-called ad-hoc polymorphism;
• ultimately, it calls for defining concise data types extensible where needed, in an ad-hoc way.

The constructs: trait GenericCtx[T] defines the type class; def meth[T: GenericCtx](arg: Type) declares a method with ad-hoc polymorphism; and summon[GenericCtx[T]] recovers the witness implementation of the extension.

The Ordered type class

The max example, one more time, is now written with a context bound. It can be called on T only if an Ordered[T] is available in scope — and the commented line shows the failure mode: there is no Ordered[Double].

object ContextBound:

  // Ordered as a type class
  trait Ordered[T]:
    def greater(t1: T, t2: T): Boolean

  // max with ad-hoc polymorphism
  // it can be called on T only if an Ordered[T] is available in scope
  def max[T: Ordered](seq: Sequence[T]): T = seq match
    case Cons(h1, Cons(h2, t)) =>
      val m = max(Cons(h2, t)) // can avoid passing context
      if summon[Ordered[T]].greater(h1, m) then h1 else m
    case Cons(h1, Nil()) => h1

  // defining the "Ordered" extension for Int
  given Ordered[Int] with
    def greater(t1: Int, t2: Int): Boolean = t1 > t2

  // defining the "Ordered" extension for String
  given Ordered[String] with
    def greater(t1: String, t2: String): Boolean = t1 > t2

  @main def tryContextBound =
    // the necessary given are already in scope
    println:
      max(Cons(10, Cons(30, Cons(20, Nil()))))
    println:
      max(Cons("a", Cons("c", Cons("d", Nil()))))
    // println(max(Cons(1.0, Cons(3.0, Cons(5.0, Nil()))))) // not working

The Showable type class

The second example is a pretty-printing type class. Note how the algorithm lives in a companion object that requires only the type class, and how an extension method makes show() read as if it were a member of every type that has a given instance.

object Showables:
  // the Showable type class
  trait Showable[T]:
    def show(t: T): String

  // algorithms / operations on showables
  object Showable:

    extension [A: Showable](a: A)
      def show(): String = summon[Showable[A]].show(a)

    def showPair[A: Showable, B: Showable](t: (A, B)): String = t match
      case (a, b) => "(" + a.show() + ", " + b.show() + ")"

    def showSequence[A: Showable](seq: Sequence[A]): String = seq match
      case Sequence.Cons(h, t) => "| " + h.show() + showSequence(t)
      case Sequence.Nil()      => ":"

object ShowableGivenInstances:
  import Showables.*, Showable.*

  // canonical terms for Int, String, Student
  given Showable[Int] with
    def show(i: Int): String = "" + i

  given Showable[String] with
    def show(s: String): String = s

  case class Student(name: String, id: Int)

  given Showable[Student] with
    def show(s: Student): String = s match
      case Student(n, i) => "stud(" + n.show() + ", " + i.show() + ")"

@main def tryShowable =
  import Showables.*, Showable.*
  import ShowableGivenInstances.{*, given}

  // note it seems like we have actually dynamically extended Int, String...
  println(10.show())
  println("hello!".show())
  println(Student("mario", 201).show())

Higher-kinded types: generalising genericity

The section ends with a kind ladder that the monad machinery of chapter 7 will need. A 0-kinded type is a standard type; a 1-kinded type is generic over a 0-kinded type; a 2-kinded type is generic over a 1-kinded type, i.e. over a type constructor like Optional[_] or Sequence[_].

// 0-kinded types: standard types
trait FactorialModuleType:
  def factorial(n: Int): Int

object BasicFactorialModule extends FactorialModuleType:
  def factorial(n: Int): Int = if n == 0 then 1 else n * factorial(n - 1)

val f = BasicFactorialModule.factorial(5)

// 1-kinded types: generic over a 0-kinded type
trait Showable[T]:
  def show(t: T): String

object ShowableInt extends Showable[Int]:
  def show(i: Int): String = "" + i

val s = ShowableInt.show(5)

// 2-kinded types: generic over a 1-kinded type
trait Filterable[T[_]]:
  def filter[A](t: T[A])(f: A => Boolean): T[A]

object FilterableOptional extends Filterable[Optional]:
  def filter[A](t: Optional[A])(f: A => Boolean): Optional[A] = t match
    case Just(a) if f(a) => Just(a)
    case _               => None()

val opt = FilterableOptional.filter(Just(11))(_ > 10)

The deck shows the same ladder once more with extension methods, where each kind level exposes its capability as an extension (5.factorial(), 5.show(), Just(11).filter(...)): the two formulations are orthogonal, and both will appear in the course.

7. Towards verification, and the second half of deck 04

The outline of deck 04 continues with three topics that the study path assigns to chapter 7: for-yield and the monad type class; an application, namely ScalaCheck and property-based testing; and a State-monadic little MVC. They are the payoff of everything this chapter built, so it is worth stating here how the pieces connect before handing them over.

• For-yield and the monad type class: the 2-kinded Monad[M[_]] type class — unit plus flatMap as an extension — generalises exactly the extension-method machinery of this chapter to type constructors, and re-implements map for free.
• ScalaCheck and property-based testing: property-based testing verifies general rules and invariants rather than specific input/output examples; in the glossary of chapter 3 it means generated test cases plus a derived oracle. The deck's plan for the course says it in one line: "code (ADTs, viewed as a model) can be tested against properties". The axioms of section 3 are exactly such properties, and the module types of section 4 make them hold in any implementation.
• A State-monadic MVC: a fully declarative application assembled from monadic components, the ultimate demonstration that the language covers the spectrum from specification to implementation.

8. Lab: verified specifications, ADTs and type classes

References and goals

• Lab repository: https://github.com/mviroli/asmd24-public-04-advanced-programming
• ScalaTest guide: https://www.scalatest.org/user_guide
• ScalaCheck documentation: https://scalacheck.org/documentation.html
• Software Foundations on ADTs: https://softwarefoundations.cis.upenn.edu/vfa-current/ADT.html

The general goals are to become operative with ScalaCheck/ScalaTest, to play with ADTs and ScalaCheck, to play with monads, and to engineer with monads.

Operational steps

1. Step 1, download and check: download the lab repository, import it in IntelliJ as an SBT project, and check that all ScalaCheck tests (SequenceCheck) run correctly. The rest of the code should be implemented inside or using the package scala.lab04.
2. Step 2, play with ScalaCheck: examine the existing ScalaCheck tests for sequences in test/scala/lab04; note that currently only map is checked, while sum and filter are only implemented — complete the properties for those two operations, and try to implement a new operation such as flatMap with its own ScalaCheck tests. Then explore the parameters: how many tests are generated by default, how to change the number of tests, how to modify the random seed, and what other parameters exist. Finally compare ScalaCheck with ScalaTest: can ScalaTest perform parameterised tests, and what are the key differences between the two frameworks?

R&D tasks

Test your knowledge