Monads, property-based testing and a monadic MVC

1. For-yield and the monad type class

This chapter is the second half of deck 04: chapter 6 built the machinery — opaque types, module types, given/using, type classes, and the kind ladder — and now that machinery is turned onto the most famous type class of all. The deck opens with a warning about how monads are talked about:

"It is the one-for-all recipe" · "it is the single design pattern for FP" · "it is a way of programming semicolon in for comprehension" · "it is variable binding mechanism" · "it can bring logic features into FP" · "it is a tool for packing imperative aspects as pure FP".

All of those sentences are true in some sense, and none of them is the definition. The history the deck reports is worth knowing because it explains why monads appear in so many places: in category theory a monad is an endofunctor with two natural transformations (I ← T and T ∘ T ← T) together with certain laws; Eugenio Moggi (UNIGE) described their use in programming in 1991; Haskell 3.1 introduced monads to handle I/O with lazy evaluation; and since then monads have proved fruitful for sequences, optionals, streams, stateful evaluation, futures, I/O and parsers. Scala collections are monadic and this is used in for comprehensions; libraries like scalaz and cats provide full monad support; and this course will make Sequence and Optional monads by type classes — which is precisely the plan of this chapter.

A computational package for values

The working definition is deliberately unpretentious: a monad is a computational "package" (or context) for elements of a type A, giving two operators:

• unit — creates the package around a value of type A;
• bind (also called flatMap) — takes a package of A and a function from A to a package of B, takes the values out of the input monad, applies the function to them, and ultimately returns one package of B.

A monad is therefore a functional-oriented and programmable composition mechanism for such packages. The general meaning of flatMap is what makes it feel like imperative programming: "for x <- m; ..." becomes m.flatMap(x => ...); in a sense, by flatMap we implement our meaning of ";" in for comprehensions involving the monad's type — we program what to extract from the monad and how to pass it to the next stages.

For comprehensions: the syntax that reads like a program

The deck previews the syntax on the standard library types first, before any custom monad exists. With Option, the comprehension propagates failure: any None input makes the whole sum None. With List, the comprehension computes the cartesian product.

def getRandom(): Option[Double] =
  if Math.random() < 0.9 then Some(Math.random) else None

// preview on for comprehension with scala Option[E]
val sum: Option[Double] =
  for
    x <- getRandom()
    y <- getRandom()
    z <- getRandom()
  yield x + y + z
println(sum) // Some(x + y + z) or None, probabilistically

// preview on for comprehension with scala List[E]
val list: List[String] =
  for
    x <- List(10, 20, 30)
    y <- List("A", "B", "C")
  yield x + y
println(list) // List(10A, 10B, 10C, 20A, 20B, 20C, 30A, 30B, 30C)

// equivalent to
val list2: List[String] =
  List(10, 20, 30).flatMap(x =>
    List("A", "B", "C").map(y =>
      x + y))
println(list2) // List(10A, 10B, 10C, 20A, 20B, 20C, 30A, 30B, 30C)

The desugaring is the point: each <- becomes a flatMap (all but the last one) and the final yield becomes a map. Whatever your data type's flatMap does — fail, iterate, run, thread state — is exactly what the ";" of the comprehension means for that type.

Monads as a 2-kinded type class

Section 6 of chapter 6 ended with the kind ladder: Monad[M[_]] is a 2-kinded type class, generic over a type constructor. The deck states the definition with the laws attached as comments, because the laws are part of the definition of a monad, not an afterthought. Note also the two implementation strategies: either implement extension methods flatMap/map for your data type and use them in for comprehensions, or use the type-class approach to get additional operations for free.

// F[_] is called a "type constructor", or 1-kinded type
// Monad is generic in a type constructor named F
trait Monad[F[_]]:
  // two constructs for monads, namely, its true "definition"
  def unit[A](a: => A): F[A]
  def flatMap[A, B](ma: F[A])(f: A => F[B]): F[B]

  // monadic laws:
  //   Left identity:  flatMap(unit(a), f) === f(a)
  //   Right identity: flatMap(m, unit(_)) === m
  //   Associativity:  flatMap(flatMap(m, f), g) ===
  //                   flatMap(m, x => flatMap(f(x), g))

  // map as a key derived op
  def map[A, B](ma: F[A])(f: A => B): F[B] =
    flatMap(ma)(a => unit(f(a)))

The companion object then hosts general-purpose operations that work for every monad once the type class is available — the payoff of the type-class route. map2 applies a binary function to two packages; seq runs two packages in sequence and keeps only the second result (the monadic "then"); seqN folds a whole stream of packages in sequence, ending when the stream ends.

object Monads:

  trait Monad[M[_]]:
    def unit[A](a: A): M[A]
    extension [A](m: M[A])
      def flatMap[B](f: A => M[B]): M[B]
      def map[B](f: A => B): M[B] = m.flatMap(a => unit(f(a)))

  object Monad:

    // additional general-purpose operations on monads

    def map2[M[_]: Monad, A, B, C](m: M[A], m2: => M[B])(f: (A, B) => C): M[C] =
      m.flatMap(a => m2.map(b => f(a, b)))

    def seq[M[_]: Monad, A, B](m: M[A], m2: => M[B]): M[B] =
      map2(m, m2)((a, b) => b)

    def seqN[M[_]: Monad, A](stream: Stream[M[A]]): M[A] =
      stream match
        case Cons(h, t) => (h(), t()) match
          case (m, Empty()) => m
          case (m, s)       => seq(m, seqN(s))

    // ... many others exist

2. The three monadic laws

Three equations must hold for every monad instance. They are the specification that property-based testing will later check (MONAD-VERIFIER), and they are what makes the derived operations behave as intended.

3. Monads at work: Optional, Sequence, IO

Three instances of the type class now show how the same contract yields completely different ";". In each case a given Monad[...] instance is defined with with blocks — the on-site given syntax of chapter 6, section 5 — and the client code never mentions the instance again.

The Optional monad: boxing a value that may be absent

Here unit is just Just, and flatMap opens the box: if the value is there, the continuation receives it; if the box is Empty, the empty box is passed on.

import Monads.*, Monad.*

object Optionals:

  // data structure for optionals
  enum Optional[A]:
    case Just(a: A)
    case Empty()

  // minimal set of algorithms
  object Optional:
    extension [A](m: Optional[A])
      def filter(p: A => Boolean): Optional[A] = m match
        case Just(a) if p(a) => m
        case _               => Empty()

  // extending Optional as a Monad!
  given Monad[Optional] with
    import Optional.{Just, Empty}

    // unit: just boxing the value
    def unit[A](a: A): Optional[A] = Just(a)

    // flatMap: opens the box if possible, gives the new box
    extension [A](m: Optional[A])
      def flatMap[B](f: A => Optional[B]): Optional[B] = m match
        case Just(a) => f(a)
        case Empty() => Empty()

The use is a three-way sum over random values: the comprehension reads like a normal program, but the failure of any optionalRandom() silently propagates. The flatMap formulation is exactly equivalent, and the generic map2 from the companion object is available with no extra code.

@main def tryOptionals =
  import Optionals.{*, given} // importing also given terms
  import Optional.*           // importing Optional algorithms

  def optionalRandom(): Optional[Double] =
    Just(java.lang.Math.random()).filter(_ < 0.9)

  // for comprehension: <- just unboxes the Optional if possible
  val m: Optional[Double] = for
    x <- optionalRandom()
    y <- optionalRandom()
    z <- optionalRandom()
  yield x + y + z
  println(m)

  // equivalent formulation by flatMap / map
  val m2: Optional[Double] =
    optionalRandom().flatMap(x =>
      optionalRandom().flatMap(y =>
        optionalRandom().map(z =>
          x + y + z)))
  println(m2)

  // use of some monadic operator
  println:
    map2(Just("rand: "), optionalRandom())(_ + _) // Some("rand: 0.223..")

The Sequence monad: iterating over many values

For lists, unit creates a singleton and flatMap maps the continuation over every element, appending all the resulting boxes: the comprehension becomes a cartesian-product generator.

object Sequences:

  enum Sequence[A]:
    case Cons(h: A, t: Sequence[A])
    case Nil()

  object Sequence:
    extension [A](s1: Sequence[A])
      def append(s2: Sequence[A]): Sequence[A] = s1 match
        case Cons(h, t) => Cons(h, t.append(s2))
        case Nil()      => s2

  given Monad[Sequence] with
    import Sequence.*
    def unit[A](a: A) = Cons(a, Nil())

    extension [A](m: Sequence[A])
      def flatMap[B](f: A => Sequence[B]): Sequence[B] = m match
        case Cons(h, t) => f(h).append(t.flatMap(f))
        case Nil()      => Nil()

@main def trySequences =
  import Sequences.{*, given}, Sequence.*

  // for comprehension: <- just iterates all elements,
  // using each to create a new box
  val s: Sequence[(Int, String)] = for
    x <- Cons(10, Cons(20, Nil()))
    y <- Cons("a", Cons("b", Nil()))
    z <- Cons(true, Cons(false, Nil()))
  yield if z then (x, y) else (0, y)

  println(s)
  // Cons((10, a), Cons((0, a), Cons((10, b), Cons((0, b),
  // Cons((20, a), Cons((0, a), Cons((20, b), Cons((0, b), Nil()))))))))

The IO monad: hiding side effects in a pure value

The decisive case: I/O in Scala is imperative, but a monad can package it. IO[A] is a case class wrapping a thunk exec: () => A: building an IO performs no side effect — the effect happens only when the thunk is executed. unit is a thunk that just returns the value; flatMap executes the first thunk and feeds the result to the continuation, producing the next IO. The whole interaction is a value.

object IOs:

  // data structure for a computation with input/output
  case class IO[A](exec: () => A)

  // minimal set of operations
  object IO:
    def read(): IO[String] = IO(() => scala.io.StdIn.readLine)
    def write[A](a: A): IO[A] = IO(() => { println(a); a })
    def compute[A](a: => A): IO[A] = IO(() => a)
    def nop(): IO[Unit] = compute(())

  // extending IO as a Monad!
  given Monad[IO] with

    // unit: an IO that just returns the boxed value
    def unit[A](a: A): IO[A] = IO(() => a)

    // flatMap: opens the box, executes, creates a new box with result
    extension [A](m: IO[A])
      def flatMap[B](f: A => IO[B]): IO[B] = m match
        case IO(e) => f(e())

The classic demonstration is the DrawNumber game: a recursive interactive loop written entirely inside for comprehensions. Notice how the recursion lives inside the monad — drawNumberGame returns an IO[Result], and the recursive call is one of the bound stages — and how the whole game is one pure value that is executed by the final expression.

@main def tryDrawGameApp =
  import IOs.{*, given}, IO.*
  import scala.util.Random.{nextInt => random} // alias import ...

  enum Result:
    case Won, Lost

  def drawNumberGame(attempts: Int, draw: Int): IO[Result] =
    if attempts == 0
    then compute(Result.Lost)
    else
      for
        _   <- write("give your number: ")
        d   <- read()
        i   <- compute(d.toInt)
        res <-
          if i == draw
          then
            for
              _ <- write("won")
              r <- compute(Result.Won)
            yield r
          else
            for
              _ <- write(if i > draw then "too high!" else "too low!")
              r <- drawNumberGame(attempts - 1, draw)
            yield r
      yield res

  // starts one run of the game
  drawNumberGame(10, random(100))

4. Property-based testing with ScalaCheck

The chapter's plan statement — "code (ADTs, viewed as a model) can be tested against properties" — now gets its tool. Property-based testing is a software testing methodology that verifies general rules/invariants rather than specific input/output examples: inputs and outputs are handled as implicit (auto-generated), making explicit their relationship instead. In the glossary of chapter 3 this is generated test cases + a derived (from the rules/invariants) oracle. The pros are that properties are more concise, more declarative, and better at catching edge cases; the recommended practice is to combine unit tests (happy paths) with property-based testing (unknown unknowns).

ScalaCheck is a popular industry-ready framework, and it is itself an application of this chapter's machinery: it is configurable thanks to monads and contextual programming.

• Gen[T] — a monad used to create ad-hoc generators of T elements;
• Arbitrary[T] — a monad representing default generators;
• by default, generators are used to produce 100 elements — to be configured;
• the tool can also be used to property-check Java code (the lab's JAVA-SCALA-CHECK task).

Checking the ADT of sequences

The running example is the Sequence ADT of chapter 6 — the axioms of the specification are written, almost verbatim, as properties. Note the overrideParameters hook that raises the default 100 to 500 successful tests, and the two forAll forms: the one looking for Arbitrary generators, and the one taking explicit Gen generators.

import org.scalacheck.*
import org.scalacheck.Prop.forAll
import org.scalacheck.Arbitrary.arbitrary
import Sequences.*, Sequence.*

object SequenceCheck extends Properties("Sequence"):
  override def overrideParameters(p: Test.Parameters): Test.Parameters =
    p.withMinSuccessfulTests(500) // 100 as default

  // here (or somewhere else) design ad-hoc Generators, if needed
  def smallInt(): Gen[Int] = Gen.choose(0, 100)

  // Prop API:
  // - forAll: (x1,..,xn) => Boolean, looks for Arbitrary generators
  // - forAll(g1,..,gn): (x1,..,xn) => Boolean, uses Gens generators

  property("of is a correct factory") =
    forAll(smallInt(), arbitrary[String]): (i, s) =>
       of(i, s) == of(i, s).filter(e => e == s)
    &&
    forAll(smallInt(), arbitrary[String]): (i, s) =>
       of(i, s).filter(e => e != s) == Nil()
    &&
    forAll(smallInt(), arbitrary[String]): (i, s) =>
       Cons(s, of(i, s)) == of(i + 1, s)
    &&
    forAll(arbitrary[String]): s =>
       of(0, s) == Nil()

Each forAll line is a general rule about of: the factory builds only copies of its element; filtering for anything else leaves the empty sequence; consing one more element is the same as asking for one more copy; and zero copies is the empty sequence. No example list appears anywhere — the specification itself is the test.

5. Generators as monads

The framework's configurable core is monadic: Gen[T] itself supports for comprehensions, so generators can be built recursively, exactly like the data types of chapter 6. The recursive generator below produces sequences of A by choosing an element, choosing a probability of continuing (80%), and either consing it onto a recursively generated tail or stopping. It is written with the very same for/yield syntax of section 1.

import org.scalacheck.Arbitrary.arbitrary
import org.scalacheck.Prop.forAll
import org.scalacheck.{Arbitrary, Gen, Properties}
import u04.datastructures.*
import Sequences.*
import Sequence.*

object SequenceCheck extends Properties("Sequence"):

  // define a recursive generator of lists, monadically
  def sequenceGen[A: Arbitrary](): Gen[Sequence[A]] = for
    a <- arbitrary[A]
    b <- Gen.prob(0.8)
    s <- if b then sequenceGen().map(s2 => Cons(a, s2)) else Gen.const(Nil())
  yield s

  // define custom arbitrary lists and mappers
  given intSeqArbitrary: Arbitrary[Sequence[Int]] = Arbitrary(sequenceGen[Int]())
  given mapperArbitrary: Arbitrary[Int => Int] =
    Arbitrary(Gen.oneOf[Int => Int](_ + 1, _ * 2, x => x * x))

  // check axioms, universally
  property("mapAxioms") =
    forAll: (seq: Sequence[Int], f: Int => Int) =>
      (seq, f) match
        case (Nil(), f)      => map(Nil())(f) == Nil()
        case (Cons(h, t), f) => map(Cons(h, t))(f) == Cons(f(h), map(t)(f))

  // how to check a generator works as expected
  @main def showSequences() =
    Range(0, 20).foreach(i => println(summon[Arbitrary[Sequence[Int]]].arbitrary.sample))

Three mechanisms of the previous chapter are working together here: the given instances register Arbitrary for the custom type and for functions (via Gen.oneOf); summon recovers the instance in showSequences; and mapAxioms checks the map axioms universally — over arbitrary sequences and arbitrary mapper functions. The commented println shows the debugging trick: inspect what the generators are actually producing while a property fails.

6. The State monad

The last monad of the lecture is the one that will run the MVC: a state is, or has, a function evolving S and producing a result A — State[S, A] is a case class around run: S => (S, A). It packages state evolution as a value: nothing is mutated anywhere; running a state on an initial s returns the final state paired with the result.

object States:

  // data structure for state (evolution)
  // a state is / has a function evolving S and producing a result A
  case class State[S, A](run: S => (S, A))

  // minimal set of algorithms
  object State:
    // a facility to run the state on an initial 's'
    extension [S, A](m: State[S, A])
      def apply(s: S): (S, A) = m match
        case State(run) => run(s)

  // define a given that works on all S, shall use "type lambdas"
  given stateMonad[S]: Monad[[A] =>> State[S, A]] with
    // unit: a state with no evolution, just the result
    def unit[A](a: A): State[S, A] = State(s => (s, a))

    // flatMap: runs the state, uses result to create a new state
    extension [A](m: State[S, A])
      override def flatMap[B](f: A => State[S, B]): State[S, B] =
        State(s => m.apply(s) match
          case (s2, a) => f(a).apply(s2)
        )

Two details deserve attention. First, the given is generic in S: Monad expects a 1-kinded type, while State[S, _] has S already fixed — the type lambda [A] =>> State[S, A] performs the partial application for the compiler. Second, unit is "a state with no evolution": it returns the state unchanged. flatMap threads the state: it runs m on s, obtains (s2, a), and runs f(a) on s2 — the state of the first stage becomes the input of the second.

CounterState: an ADT of stateful operations

The monad is then used to give a module type to a stateful counter, following the ADT discipline of chapter 6: the abstract Counter type is opaque (Int), and every operation is a State[Counter, _] — each one "giving (new counter, result)".

trait CounterState:
  type Counter
  def initialCounter(): Counter
  def inc(): State[Counter, Unit]
  def dec(): State[Counter, Unit]
  def reset(): State[Counter, Unit]
  def get(): State[Counter, Int]
  def nop(): State[Counter, Unit]

object CounterStateImpl extends CounterState:
  opaque type Counter = Int

  def initialCounter(): Counter = 0

  // giving (new_counter, result)
  def inc(): State[Counter, Unit] = State(i => (i + 1, ()));
  def dec(): State[Counter, Unit] = State(i => (i - 1, ()));
  def reset(): State[Counter, Unit] = State(i => (0, ()));
  def get(): State[Counter, Int] = State(i => (i, i));
  def nop(): State[Counter, Unit] = State(i => (i, ()));

The usage shows the state monad as a little programming language: seq sequences two operations; recursion (increment) builds a loop; and the session computation reads as a program — increment, reset, increment five times, read, reset — whose result is the value read (5) and whose final state is 0. Running it on the initial counter yields (5, 0): result and state are returned together, as the type promises.

@main def tryCounterState =
  import Monads.*, Monad.*, States.{*, given}, State.*
  val counterState: CounterState = CounterStateImpl
  import counterState.*

  println:
    inc().run(initialCounter()) // ((), 1)

  println:
    seq(inc(), inc()).run(initialCounter()) // ((), 2)

  def increment(n: Int): State[Counter, Unit] =
    if n == 0
    then nop()
    else
      for
        _ <- increment(n - 1)
        _ <- inc()
      yield ()

  val session: State[Counter, Int] =
    for
      _ <- inc()
      _ <- reset()
      _ <- increment(5)
      v <- get()
      _ <- reset()
    yield v

  println:
    session.run(initialCounter()) // (5, 0)

7. A monadic MVC

The lecture closes with the promised payoff: a fully declarative MVC application, assembled entirely from monadic components. The model is the CounterState of section 6; the view is a second state machine over a Swing window, accessed through a thin Java functional facade — an illustration of the deck's claim that "ideally, any Scala API can admit a Java facade", and of Scala's Java interoperability used for real I/O.

import javax.swing.*;
import java.awt.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;

class SwingFunctionalFacade {

  public static interface Frame {
    Frame setSize(int width, int height);
    Frame addButton(String text, String name);
    Frame addLabel(String text, String name);
    Frame showToLabel(String text, String name);
    Frame show();
    Supplier<String> events();
  }

  public static Frame createFrame() {
    return new FrameImpl();
  }
  /* private static class FrameImpl implements Frame { ... } */
}

The view is specified as a module type, WindowState, whose state is the (opaque) Window — the Swing frame — and whose operations are State[Window, _] values. Note the last operation: eventStream packages an infinite stream of button events as the result of a state computation.

import Monads.*, Monad.*, States.*, State.*
import u04.datastructures.Streams.*

trait WindowState:
  type Window
  def initialWindow: Window
  def setSize(width: Int, height: Int): State[Window, Unit]
  def addButton(text: String, name: String): State[Window, Unit]
  def addLabel(text: String, name: String): State[Window, Unit]
  def toLabel(text: String, name: String): State[Window, Unit]
  def show(): State[Window, Unit]
  def exec(cmd: => Unit): State[Window, Unit]
  def eventStream(): State[Window, Stream[String]]

object WindowStateImpl extends WindowState:
  import SwingFunctionalFacade.*

  type Window = Frame

  def initialWindow: Window = createFrame

  def setSize(width: Int, height: Int): State[Window, Unit] =
    State(w => ((w.setSize(width, height)), {}))
  def addButton(text: String, name: String): State[Window, Unit] =
    State(w => ((w.addButton(text, name)), {}))
  def addLabel(text: String, name: String): State[Window, Unit] =
    State(w => ((w.addLabel(text, name)), {}))
  def toLabel(text: String, name: String): State[Window, Unit] =
    State(w => ((w.showToLabel(text, name)), {}))
  def show(): State[Window, Unit] =
    State(w => (w.show, {}))
  def exec(cmd: => Unit): State[Window, Unit] =
    State(w => (w, cmd))
  def eventStream(): State[Window, Stream[String]] =
    State(w => (w, Stream.generate(() => w.events().get)))

mv: running model and view in lockstep

The whole architecture rests on one combinator, mv: it takes a model-state computation and a function from its result to a view-state computation, and builds a combined state over the pair (SM, SV). The model state and the view state evolve independently inside one pure value.

With mv, the application is written as two for comprehensions. windowCreation builds the window from an initial label text and hands back the event stream. The controller binds the model's initial read into the window creation, then feeds every event of the stream through seqN: each button press becomes an mv that runs the model operation, reads the new counter, and writes it into the label — or quits. Finally, the entire application is one value run on the pair of initial states.

@main def runMVC =
  import Monads.*, Monad.*, States.*, State.*, CounterStateImpl.*, WindowStateImpl.*
  import u04.datastructures.Streams.*

  def mv[SM, SV, AM, AV](m1: State[SM, AM], f: AM => State[SV, AV]): State[(SM, SV), AV] =
    State:
      case (sm, sv) =>
        val (sm2, am) = m1.run(sm)
        val (sv2, av) = f(am).run(sv)
        ((sm2, sv2), av)

  def windowCreation(str: String): State[Window, Stream[String]] = for
    _      <- setSize(300, 300)
    _      <- addButton(text = "inc", name = "IncButton")
    _      <- addButton(text = "dec", name = "DecButton")
    _      <- addButton(text = "reset", name = "ResetButton")
    _      <- addButton(text = "quit", name = "QuitButton")
    _      <- addLabel(text = str, name = "Label1")
    _      <- show()
    events <- eventStream()
  yield events

  val controller = for
    events <- mv(seq(reset(), get()), i => windowCreation(i.toString()))
    _      <- seqN(events.map(_ match
      case "IncButton"   => mv(seq(inc(), get()), i => toLabel(i.toString, "Label1"))
      case "DecButton"   => mv(seq(dec(), get()), i => toLabel(i.toString, "Label1"))
      case "ResetButton" => mv(seq(reset(), get()), i => toLabel(i.toString, "Label1"))
      case "QuitButton"  => mv(nop(), _ => exec(sys.exit()))))
  yield ()

  controller.run((initialCounter(), initialWindow))

8. Lab: verifying monads, checking properties, engineering an MVC

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. The lab deck is shared with chapter 6: the operational steps (importing the SBT project, completing sum and filter properties, adding flatMap, exploring ScalaCheck parameters, comparing with ScalaTest) are treated there. This section covers the part of the lab that needs this chapter's material.

R&D tasks

Test your knowledge