PPS-03: Advanced Functional Programming

1. Opaque Type Aliases & ADTs

One of the cornerstones of software engineering is the Abstract Data Type (ADT): define a type solely by its name, its constructors, and its operations — while hiding the concrete implementation. In Scala 3 the opaque type construct makes this possible with zero runtime overhead.

An opaque type inside an object gives you a self-contained ADT module: the object defines the type, the constructors, and the operations. Clients see only the public API. This is an alternative to algebraic data types (enum / case class) that promotes information hiding from the start.

2. ADTs by Example: Euro, Sequence, Set

Euro ADT

Here is a classic “primitive obsession” cure: an opaque type for Euro amounts.

Sequence ADT

The same pattern works for recursive data structures. A linked-list Sequence is defined as an opaque alias to a private enum inside the module.

object SequenceADT:
  private enum SequenceImpl[E]:
    case Cons(head: E, tail: Sequence[E])
    case Nil()

  import SequenceImpl.*

  opaque type Sequence[A] = SequenceImpl[A]

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

  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()
    def filter(p: A => Boolean): Sequence[A] = seq match
      case Cons(h, t) if p(h) => Cons(h, t.filter(p))
      case Cons(_, t)         => t.filter(p)
      case Nil()              => Nil()

@main def trySequenceADT =
  import SequenceADT.*
  val seq = cons(10, cons(20, cons(30, nil())))
  println(seq.map(_ + 1))

Set ADT (backed by algebraic Sequences)

Because Set is just an opaque alias for Sequence, we can build set operations on top of the sequence operations — all while hiding that fact from users.

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

3. Module Types by Traits

Just as we gave data types an abstract interface via opaque types, we can give modules an abstract interface via traits. A trait declaring method signatures becomes a module type; any object implementing it is a module that conforms to that type.

This approach respects the Open/Closed Principle (extend behaviour by providing new implementations) and the Dependency Inversion Principle (depend on abstractions, not concretions) without any OOP inheritance machinery.

4. Logger & Math Module Types

LoggerModuleType

Two implementations of a simple logger trait demonstrate how module types enable pluggable behaviour:

object LoggerModules:
  trait LoggerModuleType:
    def log(s: String): Unit

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

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

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

MathModuleType with Multiple Implementations

A more realistic example: a math module providing factorial and exponentiation, with two distinct implementations (simple recursive vs. tail-recursive with input validation).

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

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

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)

A binomial probability function uses whichever module is passed, proving the abstraction:

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)

// Prob. of 6 heads on 10 coin tosses, same result from both modules:
binomialProbability(BasicMathModule)(10, 6, 0.5)
binomialProbability(ProductionMathModule)(10, 6, 0.5)

5. Contextual Abstraction: given/using

Contextual abstraction is the idea that certain function inputs are really just “context” — configuration, strategies, dependencies that the caller should not have to pass explicitly every time. Scala 3’s given/using mechanism provides first-class support for this pattern.

Here is the simplest case: a max function over a sequence that needs a “default” value when the sequence is empty:

object ContextualParameters:
  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

@main def tryContextualParameters() =
  import ContextualParameters.*
  println(max(Cons(10, Cons(30, Cons(20, Nil()))))(using -1))  // explicit
  println(max(Nil())(using -1))

  import ContextualParameters.given
  println(max(Cons(10, Cons(30, Cons(20, Nil())))))             // implicit via given
  println(max(Nil()))                                           // implicit via given

6. Contextual Strategies & Modules

Contextual Strategies

The same mechanism can inject a comparison strategy into max:

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

  given ((Int, Int) => Boolean) = _ > _

Contextual Modules (Dependency Injection, FP-style)

The full power emerges when we combine module types with given/using: a module is “injected” into a function as a contextual parameter.

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

  object MyIntOrderingModule extends IntOrderingModuleType:
    def greater(t1: Int, t2: Int): Boolean = t1 > t2

  given iom: IntOrderingModuleType = MyIntOrderingModule

@main def tryContextualModules =
  import ContextualModules.*
  import ContextualModules.given                      // import all givens
  println(max(Cons(10, Cons(30, Cons(20, Nil())))))
  val ord = summon[IntOrderingModuleType]             // recovers the given

Applying this to the MathModuleType from earlier: we can declare a given MathModuleType = ProductionMathModule and then call binomialProbability without explicitly passing the module.

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)

given MathModuleType = ProductionMathModule

// Usage: no module argument needed!
binomialProbability(10, 6, 0.5)

7. Type Classes & Context Bounds

When a module type is generic — parameterised by a type T — and used as a contextual parameter, it becomes a type class. A context bound [T: TypeClass] says: “this function works for any T for which a TypeClass[T] witness is available in scope.”

This is ad-hoc polymorphism: different types can have completely different implementations of the same interface, chosen not by inheritance but by which given instance is in scope.

8. The Ordered & Showable Type Classes

Ordered type class

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

// Context-bound style
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

// Given instances
given Ordered[Int] with
  def greater(t1: Int, t2: Int): Boolean = t1 > t2

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())))))           // Int: works
  println(max(Cons("a", Cons("c", Cons("d", Nil())))))       // String: works
  // println(max(Cons(1.0, Cons(3.0, Cons(5.0, Nil())))))    // Double: no given!

Showable type class

The Showable type class provides a show method for any type we choose to support. It mimics what .toString does, but in a principled, extensible way.

trait Showable[T]:
  def show(t: T): String

// Extension method for all Showable types
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 Cons(h, t) => "| " + h + showSequence(t)
  case Nil()      => ":"

// Given instances
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 =
  println(10.show())                    // "10"
  println("hello!".show())             // "hello!"
  println(Student("mario", 201).show()) // "stud(mario, 201)"

9. Higher-Kinded Types

Scala’s type system supports higher-kinded types — types that abstract over type constructors (i.e., types that themselves take type parameters). This is essential for generalising over container-like types.

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

// 1-kinded
trait Showable[T]:
  def show(t: T): String

// 2-kinded
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()

Higher-kinded types are what make the Monad type class possible: a monad works for any type constructor F[_] that satisfies the monadic laws.

10. For-Comprehension & the Monad Type Class

A monad is a design pattern that packages up a computation with some effect (optionality, multiple results, I/O, state) and provides two operations:

• unit[A](a: => A): F[A] — wraps a value into the monadic context
• flatMap[A, B](ma: F[A])(f: A => F[B]): F[B] — sequences computations

In Scala, flatMap enables for-comprehension syntax:

// For-comprehension desugars into flatMap/map
val sum: Option[Double] =
  for
    x <- getRandom()
    y <- getRandom()
    z <- getRandom()
  yield x + y + z

// Equivalent desugared form:
val sum2 = getRandom().flatMap(x =>
           getRandom().flatMap(y =>
           getRandom().map(z => x + y + z)))

The general Monad type class captures this pattern generically:

With the type class in place, we can derive generic operations like map2 (combine two monadic values) and seqN (sequence a stream of monadic values):

object Monad:
  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))

For-Comprehension Desugaring Visualizer

11. Monadic Laws

Three laws define what it means to be a monad. Every Monad[F] implementation must satisfy these for the abstraction to be well-behaved:

12. The Optional & Sequence Monads

Optional as a Monad

The Optional monad models computations that may fail to produce a value. unit wraps a value in Just; flatMap unwraps only if the optional is Just, otherwise propagates Empty:

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

given Monad[Optional] with
  import Optional.{Just, Empty}

  def unit[A](a: A): Optional[A] = Just(a)

  extension [A](m: Optional[A])
    def flatMap[B](f: A => Optional[B]): Optional[B] = m match
      case Just(a) => f(a)
      case Empty() => Empty()

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

val m: Optional[Double] = for
  x <- optionalRandom()
  y <- optionalRandom()
  z <- optionalRandom()
yield x + y + z

Sequence as a Monad

The Sequence monad models non-deterministic / multi-valued computations. flatMap applies the function to every element and concatenates the results, producing the cartesian product:

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

given Monad[Sequence] with
  import Sequence.*

  def unit[A](a: A): Sequence[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()

// Usage: all combinations
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)
// Result: 8 elements — every combination of (10|20) × (a|b) × (true|false)

13. The IO Monad

In a purely functional language, I/O operations (reading input, printing to console) are side effects that violate referential transparency. The IO monad encapsulates these effects as first-class values: an IO[A] is a description of a computation that, when executed, performs I/O and produces an A.

case class IO[A](exec: () => A)

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)

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] =
      m match
        case IO(e) => f(e())

Now we can write an interactive program purely functionally, composing I/O actions with for-comprehension:

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

DrawNumber Game

A complete functional game with stateful logic, all inside the IO monad:

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

// Start the game
drawNumberGame(10, scala.util.Random.nextInt(100))

14. The State Monad

The State monad models computations that carry evolving state through a sequence of steps, all in a purely functional way. A State[S, A] is a function from an initial state S to a pair (S, A) of the new state and the result.

case class State[S, A](run: S => (S, A))

// Type lambda required for the given instance
given stateMonad[S]: Monad[[A] =>> State[S, A]] with
  def unit[A](a: A): State[S, A] = State(s => (s, a))

  extension [A](m: State[S, A])
    override def flatMap[B](f: A => State[S, B]): State[S, B] =
      State(s => m.run(s) match
        case (s2, a) => f(a).run(s2))

15. A State-Monadic Little “MVC”

The capstone example combines everything: opaque types for the window and counter states, module types for the WindowState and CounterState abstractions, and the State monad to wire a complete GUI application — all in pure FP.

WindowState type (abstract)

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

CounterState type (abstract)

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
  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 MVC wiring

The mv combinator runs a model-state computation and a view-state computation independently over a pair of states (SM, SV):

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)

The main controller creates the window, sets up buttons, then processes events infinitely:

@main def runMVC =
  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))

The lesson shows that pure FP is not an academic exercise: it can build real, interactive applications. Libraries like Cats provide these abstractions in a battle-tested form, used in production systems world-wide.

Check Your Understanding