Advanced FP: ADTs, modules, type classes, monads

1. What does this lesson add to pure FP?

The question of the lesson is whether a whole application can be built with pure FP. The answer comes from mechanisms that make FP more applicable while keeping it declarative. Many of them overlap with ideas from OOP, and Scala brought them into mainstream programming. They come in this order:

2. How do opaque types build abstract data types?

An abstract data type (ADT) is defined by its name, its constructors and its operations, while its concrete implementation stays hidden. It is the FP alternative to encapsulation in OOP. In Scala 3 a module (an object) can define a type as well as methods, and opaque type T = TImpl makes the alias transparent inside the module and opaque outside it. Outside, T is a new type unrelated to TImpl; at run time the two are the same representation, so there is no wrapping cost.

object EuroADT:
  opaque type Euro = Int // an alias, into this module, opaque outside

  def fromEuroCents(euros: Int, cents: Int): Euro =
    require(euros >= 0 && cents >= 0)
    cents + euros * 100

  def fromDouble(d: Double): Euro =
    require(d >= 0 && d <= 1_000_000)
    (d * 100).toInt // extension method in libs

  extension (e: Euro)
    def asString(): String = "$%d.%2d".format(e / 100, e % 100)
    def sum(e2: Euro): Euro = e + e2

@main def tryEurosADT =
  import EuroADT.*
  val e1: Euro = fromEuroCents(100, 50)
  val e2: Euro = fromDouble(100.0 / 3)
  println(e1.asString())            // $100.50
  println(e2.asString())            // $33.33
  println((e1 sum e2).asString())   // $133.83
  // val e3: Euro = 100               // error: Found (100 : Int), Required EuroADT.Euro
  // val e3: Euro = fromEuroCents(-10, 0) // IllegalArgumentException: requirement failed

Inside EuroADT a Euro is an Int, so cents + euros * 100 is a valid Euro and sum can use integer addition. Outside, the client sees a new type: it can build values with the constructors and manipulate them with the operations, but it has no way to see how the type is implemented. Assigning 100 to a Euro does not compile, so every value passes through require and the invariant holds by construction.

This is the cure for primitive obsession: using primitives instead of purpose-built types (strings for concepts, booleans for two-valued types, ints for n-valued types), which the deck classifies as a DIP violation. The designer's job is to hide every implementation detail of the new type.

Sequences and sets as ADTs

Any data type (sequences, streams, optionals) can be defined this way. Here the real data type is a private enum and Sequence is an opaque alias to it, so clients can neither pattern-match on Cons/Nil nor build a sequence except through cons and nil. Operations can be extension methods (map) or plain methods (concat), and a single import brings everything in.

object SequenceADT:
  // implementation of data structure: fully hidden
  private enum SequenceImpl[E]:
    case Cons(head: E, tail: Sequence[E])
    case Nil()
  import SequenceImpl.*

  // the type Sequence is an opaque alias to SequenceImpl
  opaque type Sequence[A] = SequenceImpl[A]

  // constructors
  def cons[E](head: E, tail: Sequence[E]): Sequence[E] = Cons(head, tail)
  def nil[E](): Sequence[E] = Nil[E]()

  // operation as extension methods
  extension [A](seq: Sequence[A])
    def map[B](mapper: A => B): Sequence[B] = seq match
      case Cons(h, t) => Cons(mapper(h), t.map(mapper))
      case Nil()      => Nil()

  // operations as standard methods
  def concat[A](seq1: Sequence[A], seq2: Sequence[A]): Sequence[A] = seq1 match
    case Cons(h, t) => Cons(h, concat(t, seq2))
    case Nil()      => seq2

@main def trySequenceADT =
  import SequenceADT.* // note single, import
  val seq = cons(10, cons(20, cons(30, nil())))
  println(concat(seq, seq.map(_ + 1)))
  // Cons(10,Cons(20,Cons(30,Cons(11,Cons(21,Cons(31,Nil()))))))

A new type can also reuse an existing one transparently. Set below is an opaque alias of the algebraic Sequence of lesson 3 (the exposed enum with map and filter as extension methods), so inside the module it can match on Cons/Nil and call filter, while outside a Set is not a Sequence.

import u03.extensionmethods.Sequences.*   // the algebraic Sequence of lesson 3
import Sequence.*

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

  def fromSequence[A](s: Sequence[A]): Set[A] = s 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())                   // Cons(10,Cons(20,Cons(30,Nil())))
  println(s2.toSequence())                   // Cons(10,Cons(11,Nil()))
  println(union(s1, s2).toSequence())        // Cons(10,Cons(11,Cons(20,Cons(30,Nil()))))
  println(intersection(s1, s2).toSequence()) // Cons(10,Nil())

fromSequence removes duplicates by keeping the head and recurring on the tail with every copy of the head removed. union walks s2: it emits 10, then 11, and when s2 is exhausted it appends what is left of s1, that is (20, 30). The result is therefore (10, 11, 20, 30). The slide's comment says (10, 20, 30, 11), which is not what the code prints.

ADTs or algebraic data types?

The price of hiding is that the set of operations is hard to extend outside the module. In the rest of the lesson sequences and streams are the algebraic versions of lesson 3, while the discussion keeps starting from ADTs.

3. How do module types separate interface from implementation?

A module can itself be given a type, separating the concept from its implementations: trait ModuleType { <signatures> }, object ModuleImpl extends ModuleType { … }, and functions that take a ModuleType argument. Many implementations can then trade off different aspects, a function can be made more abstract by taking the module as a parameter, and the application decides each time which implementation to pass. This is how OCP (add an implementation without touching the clients) and DIP (depend on the module type, not on an implementation) are obtained in pure FP.

object LoggerModules:
  // type for modules exposing definition of a log method (no implementation)
  trait LoggerModuleType:
    def log(s: String): Unit

  object BasicLoggerModule extends LoggerModuleType:
    def log(s: String): Unit = println(s)

  object EmptyLoggerModule extends LoggerModuleType:
    def log(s: String): Unit = {}

  // method call requiring indication of a LoggerModuleType
  def loggedCall[A, B](name: String, f: A => B, a: A)(LoggerModule: LoggerModuleType): B =
    LoggerModule.log(s"calling function $name with input $a")
    f(a)

@main def tryLoggers =
  import LoggerModules.*
  println(loggedCall("sin", Math.sin(_), 0.5)(BasicLoggerModule))
  println(loggedCall("sin", Math.sin(_), 0.5)(EmptyLoggerModule))

calling function sin with input 0.5
0.479425538604203
0.479425538604203

Two implementations of a math module

The same idea applies to algorithms. BasicMathModule is non-tail-recursive and does not check its inputs; ProductionMathModule is tail-recursive and rejects bad inputs with a guarded match, which throws MatchError when the guard fails.

object MathModules:
  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:
    def factorial(n: Int): Int =
      if n == 0 then 1 else n * factorial(n - 1) // note if-then-else
    def exp(base: Double, power: Int): Double =
      if power == 0 then 1 else base * exp(base, power - 1)

  // tail recursive solutions with input checks
  object ProductionMathModule extends MathModuleType:
    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)
    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)

@main def tryMathModule =
  import MathModules.*
  // probability of x successes over n trials, each with probability p
  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)       // 0.205078125
  println:
    binomialProbability(ProductionMathModule)(10, 6, 0.5)  // 0.205078125

A module type with a type member

A module type can also declare an abstract type member. The trait says that a type Set[A] exists, with its constructors and operations, and each implementation decides what it is. A client depends only on the trait and imports the type and the operations from a value of that trait:

trait SetADT:
  type Set[A]
  def fromSequence[A](s: Sequence[A]): Set[A]
  def union[A](s1: Set[A], s2: Set[A]): Set[A]
  def intersection[A](s1: Set[A], s2: Set[A]): Set[A]
  extension [A](s: Set[A])
    def contains(a: A): Boolean
    def remove(a: A): Set[A]
    def toSequence(): Sequence[A]

object BasicSetADT extends SetADT:
  opaque type Set[A] = Sequence[A]
  // ... fromSequence, union, intersection, contains, remove, toSequence as in SetADT above

@main def trySetADTModule =
  import Sets.*
  val setADT: SetADT = BasicSetADT
  import setADT.*          // the type Set and the operations of this implementation
  val s1: Set[Int] = fromSequence(Cons(10, Cons(20, Cons(10, Cons(30, Nil())))))
  // val s3: Set[Int] = Cons(10, Nil()) // still rejected: Set is abstract here
  println(s1.toSequence()) // Cons(10,Cons(20,Cons(30,Nil())))

4. How do given and using pass context implicitly?

Contextual abstraction is the idea that some inputs of a function are just context. You want to mark them as such, in the definition and at the call, and to have ways of defining and passing them implicitly. It captures extra arguments and strategies easily, and it is the basis of type classes. The constructs:

• def meth(arg: Type)(using ctx: CtxType) = … declares a contextual parameter. using applies to a whole curried parameter list, typically the last one.
• meth(actualArg)(using actualCtx) passes the context explicitly.
• given givenName: CtxType = actualCtx defines a canonical term for that type (the name can be omitted).
• meth(actualArg) then receives the context implicitly.

object ContextualParameters:
  /* A standard max over a sequence, with an additional "configuration"
   * or "contextual" parameter, specified by using clause. Note the using
   * clause is not necessary in the recursive call. */
  def max(seq: Sequence[Int])(using orElse: Int): Int = seq match
    case Cons(h1, Cons(h2, t)) => max(Cons(if h1 > h2 then h1 else h2, t))
    case Cons(h1, Nil())       => h1
    case _                     => orElse

  given standardDefault: Int = -1 // if using an Int is needed, suggest to take this!

@main def tryContextualParameters() =
  import ContextualParameters.*
  println:
    max(Cons(10, Cons(30, Cons(20, Nil()))))(using -1)   // 30
  println:
    max(Nil())(using -1)                                 // -1
  import ContextualParameters.given // or ContextualParameters.standardDefault
  println:
    max(Cons(10, Cons(30, Cons(20, Nil()))))             // 30, no using clause needed

Worked example: resolving max(Nil())

The call supplies only the first parameter list. Because the second is a using list, the compiler does not report a missing argument: it searches the scope for a given of type Int. Before import ContextualParameters.given there is none, and compilation fails with a message that is worth knowing: No given instance of type Int was found for parameter orElse of method max … given instance standardDefault in object ContextualParameters was not considered because it was not imported with import given. A wildcard import X.* does not bring givens in. After the import, standardDefault is the only candidate, and the call becomes max(Nil())(using standardDefault). Inside the body, the recursive call needs no using: the parameter orElse is itself a given there, so it is found first and passed along. A using parameter is a hole, a given is a value the compiler may put in it, and resolution is a search by type.

Plain contextual values like this Int are uncommon. The typical contexts are strategies and modules:

object ContextualStrategies:
  def max(seq: Sequence[Int])(using ordering: (Int, Int) => Boolean): Int = seq match
    case Cons(h1, Cons(h2, t)) => max(Cons(if ordering(h1, h2) then h1 else h2, t))
    case Cons(h1, Nil()) => h1

  @main def tryContextualStrategies() =
    println:
      max(Cons(10, Cons(30, Cons(20, Nil()))))(using _ > _)   // 30
    println:
      max(Cons(10, Cons(30, Cons(20, Nil()))))(using _ < _)   // 10
    // the given defined here needs not be imported;
    // its name would not be helpful, so it is omitted
    given ((Int, Int) => Boolean) = _ > _
    println:
      max(Cons(10, Cons(30, Cons(20, Nil()))))                // 30

object ContextualModules:
  trait IntOrderingModuleType:
    def greater(t1: Int, t2: Int): Boolean

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

  // defining a module implementing the contract
  object MyIntOrderingModule extends IntOrderingModuleType:
    def greater(t1: Int, t2: Int): Boolean = t1 > t2

  // defining a canonical term taking an existing module
  given iom: IntOrderingModuleType = MyIntOrderingModule

@main def tryContextualModules =
  import ContextualModules.*
  import ContextualModules.given   // or a specific one: import ContextualModules.iom
  println:
    max(Cons(10, Cons(30, Cons(20, Nil()))))   // 30
  val ord = summon[IntOrderingModuleType]      // gives ContextualModules.iom

summon[T] returns the given of type T in scope. With a module type as context, a given becomes an injected dependency, resolved at compile time without reflection or a container:

@main def tryContextualMathModule =
  import MathModules.*
  def binomialProbability(n: Int, x: Int, p: Double)(using mm: MathModuleType): Double =
    mm.factorial(n) / mm.factorial(x) / mm.factorial(n-x) *
    mm.exp(p, x) * mm.exp(1-p, n-x)

  // injecting the dependency by a given!!
  given MathModuleType = ProductionMathModule

  println:
    binomialProbability(10, 6, 0.5)   // 0.205078125

5. What is a type class?

A module type can be generic. Used as a context, a generic module type TC[T] acts as a context bound: a constraint on the type variable saying that an instantiation is admissible only if a TC[T] is available in scope. TC can then be read as an a posteriori extension of T, a type class, and the given in scope is its witness. This is a programmable form of ad-hoc polymorphism: each type gets its own implementation, chosen by which given is in scope rather than by inheritance. It encourages concise data types that are extended later, where and if needed. The constructs are trait TC[T] { … }, def meth[T: TC](arg: T) = … (sugar for a using TC[T] clause) and summon[TC[T]] to recover the witness.

// Ordered as a generic module type, namely, a so called "type class"
trait Ordered[T]:
  def greater(t1: T, t2: T): Boolean

// using-oriented style of definition
def maxWithUsing[T](seq: Sequence[T])(using ordered: Ordered[T]): T = max(seq)

// equivalent definition with context bound, recalling "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)) => max(Cons(if summon[Ordered[T]].greater(h1, h2) then h1 else h2, t))
  case Cons(h1, Nil()) => h1

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

// doing the same for String, in a different style
object MyOrderedString extends Ordered[String]:
  def greater(t1: String, t2: String): Boolean = t1 > t2
given Ordered[String] = MyOrderedString

@main def tryContextBound =
  println:
    max(Cons(10, Cons(30, Cons(20, Nil()))))       // 30
  println:
    max(Cons("a", Cons("c", Cons("d", Nil()))))    // d
  // println(max(Cons(1.0, Cons(3.0, Cons(5.0, Nil())))))
  // error: No given instance of type Ordered[Double] was found
  //        for a context parameter of method max

Showable: adding a method to existing types

Combining a type class with an extension method whose type parameter has a context bound makes it look as if Int and String had been given a new method. The type class and its algorithms live in one object; the instances live in another, imported with {*, given}.

import u03.extensionmethods.Sequences.*, Sequence.*

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

  object Showable:            // algorithms/operations on showables
    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 + 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}
  // it seems like we have actually dynamically extended Int, String...
  println(10.show())                                   // 10
  println("hello!".show())                             // hello!
  println(Student("mario", 201).show())                // stud(mario, 201)
  println(showPair((Student("mario", 201), 3)))        // (stud(mario, 201), 3)
  println(showSequence(Cons(1, Cons(2, Nil()))))       // |1|2:

The Student instance calls n.show() and i.show(), which resolve to the String and Int instances: instances compose. showSequence concatenates h directly, so it uses toString and never needs its context bound; h.show() was presumably meant.

object TypeClasses:
  trait Combine[T]:
    def combine(t1: T)(t2: T): T
    extension (t1: T) def <>(t2: T): T = combine(t1)(t2)

  object SumInt extends Combine[Int]:
    def combine(t1: Int)(t2: Int): Int = t1 + t2
  object ProdInt extends Combine[Int]:
    def combine(t1: Int)(t2: Int): Int = t1 * t2
  object ConcatStrings extends Combine[String]:
    def combine(t1: String)(t2: String): String = t1 + t2

  def combine3[T](using cmb: Combine[T])(t1: T, t2: T, t3: T): T = t1 <> t2 <> t3
  def combine4[T: Combine](t1: T, t2: T, t3: T): T = t1 <> t2 <> t3

  @main def ex1 =
    println(combine3(using SumInt)(1, 10, 100))    // 111
    println(combine3(using ProdInt)(1, 10, 100))   // 1000
    given Combine[Int] = ProdInt
    println(1 <> 2)                                // 2
    println(combine3(1, 10, 100))                  // 1000

6. What are higher-kinded types, and where does Cats fit?

Genericity can itself be generalised. Types have kinds: a 0-kinded type is an ordinary type (Int, Euro); a 1-kinded type is generic over a 0-kinded one (Showable[T], Sequence[A]), and is also called a type constructor; a 2-kinded type is generic over a 1-kinded one, written T[_].

// 0-kinded types, that is, 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)          // 120

// 1-kinded types, that is, 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)                        // "5"

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

import u03.extensionmethods.Optionals.*, Optional.*   // Just(a) | None()
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)   // Just(11)

Filterable is written once for every container: an instance fixes T to Optional, Sequence, and so on. The Monad type class of the next section has the same shape, Monad[M[_]]. The course code also has a variant of these three modules with extension methods, so that one writes 5.factorial(), 5.show() and Just(11).filter(_ > 10).

The Cats library organises FP abstractions as a hierarchy of such type classes. The deck shows the full Cats infographic; the part that matters here is below.

//> using dep org.typelevel::cats-core:2.12.0
import cats.{Monad, Monoid, Show}
import cats.syntax.all.*

case class Student(name: String, id: Int)
given Show[Student] = Show.show(s => s"stud(${s.name}, ${s.id})")

@main def tryCats =
  println(Monoid[Int].combineAll(List(10, 20, 30)))              // 60
  println(Student("mario", 201).show)                            // stud(mario, 201)
  println(Monad[Option].pure(10))                                // Some(10)
  println((Option(1), Option(2)).mapN(_ + _))                    // Some(3)
  println(Monad[List].flatMap(List(10, 20))(x => List(x, x + 1)))  // List(10, 11, 20, 21)

7. What is a monad?

A for-comprehension in Scala is syntax for flatMap and map calls, and it works on any type that has them. The standard Option and List show it:

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

val sum: Option[Double] =
  for
    x <- getRandom()
    y <- getRandom()
    z <- getRandom()
  yield x+y+z
println(sum) // Some(x+y+z) or None, probabilistically; one run: Some(2.0485792428914555)

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 rule that the monad discussion needs: every generator but the last becomes a flatMap, the last becomes a map, and yield gives the body of that map. (The full desugaring, with guards and withFilter, value definitions and for without yield, is in Lesson 7, section 10.) For list2, the outer flatMap calls its function once per element: x = 10 gives List("10A","10B","10C"), and so on, and flatMap concatenates the three lists. With map in place of the outer flatMap the result would be a list of three lists. For Option the same rule means: if a getRandom() is None, flatMap returns None without running the rest.

unit and flatMap

A monad is a computational "package" for elements of a type A, with two operators:

• unit, which creates the package around a value of type A;
• bind, also called flatMap, which takes a package of A and a function from A to a package of B, takes the values out of the input package, applies the function to them and returns a single package of B.

It is a functional, programmable way of composing packages. for x <- m; … becomes m.flatMap(x => …), so by writing flatMap we program our own meaning of ";" in comprehensions over m's type: what to extract from the monad and how to pass it to the next stages. map is derived: flatMap followed by unit.

// 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 that must hold:
  // 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 operation
  def map[A, B](ma: F[A])(f: A => B): F[B] =
    flatMap(ma)(a => unit(f(a)))

The laws are what make unit a neutral element and flatMap a composition, so that monadic code can be reasoned about equationally. For a concrete monad they can be checked case by case; for the Optional monad of section 8, with f = x => if x > 0 then Just(x*10) else Empty() and g = y => Just("v"+y), all three hold for Just(3), Just(-3) and Empty().

The Monad type class used in the course

There are two ways to support for-comprehensions for a data type: just implement flatMap/map as extension methods, or use the type class approach and get further operations for free. The course's Monad declares flatMap as an extension, so that m.flatMap(…) and for work directly, and adds general-purpose operations in its companion:

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

map2 combines two monadic values, seq runs two in order and keeps the second result, seqN runs a whole lazy Stream of them in order (it is not defined on an empty stream). All three work for any M with a Monad[M] in scope.

8. What do Optional, Sequence and IO look like as monads?

Making a data type a monad means giving a Monad instance: unit says how to box a value, flatMap says what "and then" means for that type.

Optional: stop at the first empty result

import Monads.*, Monad.*

object Optionals:
  enum Optional[A]:
    case Just(a: A)
    case Empty()

  object Optional:   // minimal set of algorithms
    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 to be 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()

@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)                  // one run: Just(1.7172390656077152)

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

  // use of some monadic operator
  println:
    map2(Just("rand: "), optionalRandom())(_ + _) // Just(rand: 0.587...) or Empty()

Sequence: every combination

For Sequence, <- iterates over all the elements, and each one produces a new sequence; flatMap appends them. Nested generators give all combinations, with the outer generator varying slowest.

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

IO: side effects behind a pure interface

Reading and printing are side effects, and they break referential transparency. Plain Scala I/O (scala.io.StdIn.readLine, println) is imperative. The IO monad packs such operations into values of type IO[A], a wrapper around a thunk () => A, and composes them in a for-comprehension:

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

  object IO:   // minimal set of operations
    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 to be 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, and 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())

val simpleInteractiveComputation: IO[Int] =
  for
    s <- read()
    _ <- write("Thanks for providing: " + s)
    i <- compute(s.toInt)
    j <- compute(i * 2)
    _ <- write("Result is: " + j)
  yield j

// desugared version
val simpleInteractiveComputationByFlatMaps: IO[Int] =
  read()                              .flatMap(s =>
  write("Thanks for providing: " + s) .flatMap(_ =>
  compute(s.toInt)                    .flatMap(i =>
  compute(i * 2)                      .flatMap(j =>
  write("Result is: " + j)            .map(_ =>
    j)))))

Note what this flatMap does: f(e()) runs m's effect as soon as the composition is built. Defining the two vals above therefore reads and prints twice (with input 5 then 7: Thanks for providing: 5, Result is: 10, Thanks for providing: 7, Result is: 14), and nobody ever calls exec. The effects are packaged behind a pure-looking interface, but the value is not a deferred description.

given Monad[IO] with
  def unit[A](a: A): IO[A] = IO(() => a)
  extension [A](m: IO[A])
    def flatMap[B](f: A => IO[B]): IO[B] = IO(() => f(m.exec()).exec())

val program: IO[Int] = for
  _ <- write("step 1")
  i <- compute(20 + 1)
  _ <- write("step 2: " + i)
yield i * 2
println("-- nothing has run yet --")
println(program.exec())   // step 1 / step 2: 21 / 42
println(program.exec())   // step 1 / step 2: 21 / 42 again

The DrawNumber game

A whole interactive game in the IO monad. The loop is recursion inside the monad, and res <- if … then (for …) else (for …) binds the result of whichever nested computation is chosen.

@main def tryDrawGameApp =
  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, scala.util.Random.nextInt(100))

The last line only builds the IO[Result], and with this eager flatMap building is playing. With the draw fixed at 37 and inputs 50, 25, 37, the game prints give your number:, too high!, give your number:, too low!, give your number:, won before the value exists; its exec() then returns Won.

9. How does the State monad make a whole application pure?

A State[S, A] is a function from a state S to a pair (new state, result A). flatMap runs the first transition on the current state and feeds the new state to the next one. A program that reads like a sequence of commands on a mutable object is really a composition of pure functions.

import Monads.*, Monad.*

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

  object State:   // minimal set of algorithms
    // 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 instance 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, use 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)
        )

Monad expects a 1-kinded type constructor, while State has two parameters. The type lambda [A] =>> State[S, A] fixes S and leaves A free, and given stateMonad[S] provides one instance for every S.

A counter as a State ADT

The counter is an ADT (a module type with an abstract type member) whose operations are state transitions:

import States.*

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

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

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

  def increment(n: Int): State[Counter, Unit] =   // a loop as monadic recursion
    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())  // (0,5)

session is a value: nothing happens until run is applied to an initial counter, and running it twice gives (0,5) twice, because nothing has been mutated in between. The pair is (state, result), as run: S => (S, A) says; the slide comments print the components the other way round (((), 1), (5, 0)).

A State-monadic little "MVC"

The deck closes with a GUI counter whose Scala code has no mutable variables. The view is a Java SwingFunctionalFacade with a fluent Frame interface (setSize, addButton, addLabel, showToLabel, show, and events(), a Supplier<String> that blocks until a button is pressed and returns its name). A second State ADT wraps it:

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

The controller works on the pair of states (Counter, Window). mv runs a model transition, then a view transition built from the model's result:

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

  def mv[SM, SV, AM, AV](m1: State[SM,AM], f: AM => State[SV, AV]): State[(SM, SV), AV] =
    State: (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))

Read the controller from the top. seq(reset(), get()) resets the counter and reads it in one model step; its result (0) becomes the label of the new window, and the view step returns the infinite lazy stream of button events. Each event is mapped to a State[(Counter, Window), Unit] that updates the model and then the label, and seqN chains them in order: that chain is the event loop. It never ends until QuitButton runs sys.exit(). The mutable Swing machinery exists, but it is hidden behind the facade; the application logic is a single State value run once on (initialCounter(), initialWindow). This is the lesson's answer to its opening question.

10. Lab 04

The lab (repository unibo-pps/pps-lab04) practises the three parts of the lesson, each task with its tests: ADTs (a complex-number ADT, a school model, a stack ADT), type classes (Summable, a 1-kinded type class with zero and sum; Traversable, a higher-kinded one) and monads (a Try monad, like Optional but carrying an exception).

import u03.extensionmethods.Sequences.*, Sequence.*
import u03.extensionmethods.Optionals.*, Optional.*
import u04.monads.Monads.*, Monad.*

trait Summable[A]:
  def zero: A
  def sum(a1: A, a2: A): A

given Summable[Int] with
  def zero: Int = 0
  def sum(a1: Int, a2: Int): Int = a1 + a2
given Summable[String] with
  def zero: String = ""
  def sum(a1: String, a2: String): String = a1 + a2

def sumAll[A: Summable](seq: Sequence[A]): A =
  val s = summon[Summable[A]]
  seq match
    case Cons(h, t) => s.sum(h, sumAll(t))
    case Nil()      => s.zero

trait Traversable[T[_]]:
  def logAll[A](t: T[A])(log: A => Unit): Unit

given Traversable[Sequence] with
  def logAll[A](t: Sequence[A])(log: A => Unit): Unit = t match
    case Cons(h, tl) => log(h); logAll(tl)(log)
    case Nil()       => ()
given Traversable[Optional] with
  def logAll[A](t: Optional[A])(log: A => Unit): Unit = t match
    case Just(a) => log(a)
    case _       => ()

def printAll[T[_]: Traversable, A](t: T[A]): Unit =
  summon[Traversable[T]].logAll(t)(a => println("> " + a))

enum MyTry[A]:
  case Success(value: A)
  case Failure(exception: Throwable)
object MyTry:
  def apply[A](a: => A): MyTry[A] =
    try Success(a) catch case e: Throwable => Failure(e)

given Monad[MyTry] with
  import MyTry.*
  def unit[A](a: A): MyTry[A] = Success(a)
  extension [A](m: MyTry[A])
    def flatMap[B](f: A => MyTry[B]): MyTry[B] = m match
      case Success(a) => f(a)
      case Failure(e) => Failure(e)

@main def tryLab04 =
  println(sumAll(Cons(10, Cons(20, Cons(30, Nil())))))   // 60
  println(sumAll(Cons("a", Cons("b", Cons("c", Nil()))))) // abc
  printAll(Cons(1, Cons(2, Nil())))                       // > 1  > 2
  printAll(Just("hi"))                                    // > hi
  def parse(s: String): MyTry[Int] = MyTry(s.toInt)
  println(for a <- parse("10"); b <- parse("32") yield a + b)  // Success(42)
  println(for a <- parse("10"); b <- parse("x2") yield a + b)
  // Failure(java.lang.NumberFormatException: For input string: "x2")

Check your understanding