Functional programming basics in Scala 3

1. Why functional programming?

Pure OO approaches have limits. "Everything is an object" can be verbose and does not always fit; a function written as a class with one method (a functional interface) is verbose, and verbosity creates inertia; and OO code is not declarative, since it describes step-by-step behaviour rather than the goal. FP offers:

• a smooth abstraction for computing information;
• techniques to abstract away the "internal execution", the imperative aspects;
• techniques to support concurrency orthogonally (the topic of the PCD course);
• higher confidence in the correctness of code, by construction.

The possible disadvantage for software engineering: functional code is terser and requires higher competence. Mainstream OO languages have absorbed FP ideas in translated form: "no side effects" became "prefer immutability", "everything is a function" became "use lambdas and factories", "higher-order functions" became "use the Strategy pattern", and "abstract evaluation order" became "use lazy APIs", as with Java streams.

import java.util.*;
import java.util.stream.*;
import static java.util.stream.Collectors.*;

public class ShowcaseJava8 {
  public static void main(String[] args) {
    // using a 'lambda function' to express a functional strategy
    final Comparator<Integer> comparator = (a, b) -> a - b;
    final Set<Integer> set = new TreeSet<>(comparator);
    set.addAll(Arrays.asList(10, 20, 30, 40, 5, 6, 7, 60, 70));
    System.out.println(set);

    // declaratively working with streams: note str is an 'infinite' sequence!
    final Random random = new Random();
    final Stream<Integer> str = Stream.generate(() -> random.nextInt(6))
                                      .map(i -> i + 1);
    System.out.println(str.limit(20).collect(toList()));

    // simulating large-scale data processing with parallel streams
    final List<Double> l = IntStream.range(0, 10000000)
        .mapToObj(x -> Math.random())
        .collect(toList());
    // sequential
    long time = System.currentTimeMillis();
    System.out.println(l.stream().reduce((a, b) -> Math.max(a, b)));
    time = System.currentTimeMillis() - time;
    System.out.println("Time: " + time);
    // parallel
    long time2 = System.currentTimeMillis();
    System.out.println(l.stream().parallel().reduce((a, b) -> Math.max(a, b)));
    time2 = System.currentTimeMillis() - time2;
    System.out.println("Time2: " + time2);
    System.out.println("Gain: " + (((double) time) / time2));
  }
}

[5, 6, 7, 10, 20, 30, 40, 60, 70]
[6, 5, 2, 6, 6, 1, 3, 4, 1, 4, 3, 4, 5, 1, 1, 3, 6, 6, 6, 2]
Optional[0.9999993348556825]
Time: 826
Optional[0.9999993348556825]
Time2: 46
Gain: 17.956521739130434

2. What is Scala, and how do you work with it?

Scala ("Scalable Language") is a strongly typed language that compiles to Java bytecode (and to JavaScript and native code). Martin Odersky started it at EPFL in 2001 to be both object-oriented and functional; version 3 came in 2021, and the course uses 3.3.5. Java 8+, C# and Kotlin inherited their functional side from it.

The course builds with SBT and experiments in the REPL, started with sbt console (or scala); IntelliJ IDEA is the reference IDE.

3. What is a functional program made of?

• computation is a set of functions, possibly split into modules;
• functions have a pure "many inputs, one output" behaviour;
• there are no side effects (console I/O is tolerated as a hack, to log);
• values are primitive values, functions, records and sums (unions);
• there are no imperative constructs: recursion is the only iteration mechanism.

The first fragment of the language is T ::= Int | Double | Boolean | String | … and e ::= v | v1 op v2 | …. A val names a value and can never be reassigned.

// values can be associated to names, namely non-modifiable variables
val v = 1
// type indication is optional (typically inferred)
val w: Int = 1
// the right-hand side is a whole expression
val z = v + 5
// the usual way to print on the console (a non-FP hack)
println(z)                    // 6

val a = 1
println("result is " + a)     // result is 1   (Java-style concatenation)
println(s"result is $a")      // result is 1   (string interpolation)
println(s"result is ${a+1}")  // result is 2   (interpolating an expression)

// primitive types as expected on the JVM
val i: Int = 10 + 5                       // as in Java, to be read +(10,5)
val l: Long = 100_000_000_000L
val d: Double = 5.4 * 1.3
val f: Float = 3.0f
val b: Boolean = true && false
val s: String = "hello" concat " to all"  // String methods as operators
val n: String = null                      // null can be passed to "objects", sorry
println(s"$i, $l, $d, $f, $b, $s, $n")    // 15, 100000000000, 7.0200000000000005, 3.0, false, hello to all, null

val u: Unit = ()                // Unit has a single value, written ()
val u2: Unit = println("a")     // prints a: Unit is the type of "no interesting result"

There is no real distinction between primitive and other types: every value is an object, and 10 + 5 is the method call 10.+(5). Types of values are usually left to inference. Unit has the single value () and types expressions whose result does not matter, such as println(…); null exists only for JVM interoperability.

4. How do you write, pass and return functions?

Functions are values: the language grows by T ::= (T1,…,Tn) => T0 (function types) and e ::= (x1,…,xn) => e1 … en | ef(e1,…,en) (function literals and calls).

// a function variable: type (Int, Int) => Int, value an anonymous function (function literal)
val f: (Int, Int) => Int = (x: Int, y: Int) => x + y
val res = f(5, 10)    // standard call syntax, "value passing"
println(res)          // 15

// various syntaxes for function literals
val f1: (Int, Int) => Int = (x: Int, y: Int) => x + y  // typed literal, typed val
val f2 = (x: Int, y: Int) => x + y                     // typed literal, untyped val
val f3: (Int, Int) => Int = (x, y) => x + y            // untyped literal, typed val
val f4: (Int, Int) => Int = _ + _                      // placeholders, typed val
val f5: (Int, Int) => Int = f4                         // a function variable used as a value
// val f6 = _ + _                                      // does not type-check

println(s"${f1(10, 5)}, ${f4(10, 5)}")  // 15, 15

val g: Int => Int =
  (x: Int) =>           // a function literal with an imperative body
    println("hello")    // a statement (with a side effect)
    x + 1               // the last expression is the result

println(g(10))          // prints hello, then 11

A function type (T1,…,Tn) => T0 describes functions from n inputs to one output (special cases T1 => T0 and () => T0). A function value or function literal (a lambda, in Java) (x1,…,xn) => e is an actual function. In each declaration above, the part before = is the val with its type, the part after is the function. There are four styles:

Styles 3 and 4 need an expected type: val f6 = _ + _ fails with "Could not infer type for parameter _$1 of anonymous function". With several expressions in the body, as in g, the last one is the result.

Higher-order functions

// first order: no argument or result is a function
val f = (x: Int, y: Int) => x + y
// higher order: an input (or the output) is itself a function
val h: (Int, Int, (Int, Int) => Int) => Int = (a, b, f) => f(a, b)

println(h(10, 5, _ * _))            // 50
println(h(10, 5, (a, b) => a + b))  // 15
println(h(10, 5, f))                // 15

val i: (Int, Int => Int, Int => Int) => Int =
  (n, f1, f2) => f1(f2(n))

println(i(10, _ + 1, _ * 2))        // 21

val l: (Int => Int) => (Int => Int) =
  f => (i => f(f(i)))               // without parens: f => i => f(f(i))

println(l(_ + 1)(10))               // 12

A higher-order function takes or returns a function. It is the quintessential FP pattern for making code reusable and configurable: the FP version of Strategy (or rather, Strategy is the OO version of it). i applies f2 then f1; l returns a function, which leads to currying (section 7). => is right-associative: a => b => c means a => (b => c).

5. How does pattern matching work?

Matching adds e ::= { case p1 => e1; … } | e match { case … }: a switch expression that can also define a function.

// matching against patterns: a switch expression
val v = 5
val res = v match
  case n if n > 0 => "pos"
  case 0 => "zero"
  case _ => "neg"     // default case: makes the function total
println(res)          // pos

// a case-based function (partial, here)
// val f = (i: Int) => i match   // alternative header
val f: Int => String = _ match
  case n if n > 0 => "pos"
  case 0 => "zero"

println(f(1))         // pos
println(f(0))         // zero

val g: Int => String = { case n if n > 0 => "pos" }  // one-liner with {}
println(g(1))         // pos

// what f(-1) does: no case matches
try f(-1) catch case e: MatchError => println(e)  // scala.MatchError: -1 (of class java.lang.Integer)

• A case block defines a partial unary function, which fails on unmatched inputs with scala.MatchError; we normally neither throw nor catch it. match applies it to the value on its left, and case _ makes it total.
• Patterns, for now: values, variables, variables with an if guard. A variable in a pattern is always a fresh one.
• Cases are tried top to bottom; only the first match is evaluated.
• _ match with indented cases is the idiomatic Scala 3 case-based function; braces serve for one-liners.

val zero = 0
def isZero(n: Int): Boolean = n match
  case `zero` => true    // backquotes: compare with the existing value
  case _ => false
def alwaysTrue(n: Int): Boolean = n match
  case zero => true      // a NEW variable named zero: matches anything
println((isZero(0), isZero(5), alwaysTrue(5)))  // (true,false,true)

object Indentation:

  // idiomatic Scala 3 significant indentation
  val res = 5 match
    case n if n > 0 => "pos"
    case 0 => "zero"

  // indentation with an end marker (useful in complicated cases)
  val res2 = 5 match
    case n if n > 0 => "pos"
    case 0 => "zero"
  end res2

  // Scala 2 (and Java) style: avoid it unless necessary
  val res3 = 5 match {
    case n if n > 0 => "pos"
    case 0 => "zero"
  }

  // single line: curly braces and a semicolon
  val res4 = 5 match { case n if n > 0 => "pos"; case 0 => "zero" }

  // a single argument can be passed indented, after a colon
  println:
    5 + 10              // prints 15

end Indentation         // an end marker for the object

6. What do methods add: nesting and tail recursion

A method is declared as def f(x1: T1,…,xn: Tn): T0 = e, a UML-like syntax.

// a defined function (method), with UML-like syntax
def square(d: Double): Double = d * d
println(square(3.0))     // 9.0

// mostly equivalent code with a val
val square2: Double => Double = d => d * d
println(square2(3.0))    // 9.0

// recursion and pattern matching
def factorial(n: Int): Int = n match
  case 0 | 1 => 1                 // 0 or 1 gets mapped to 1
  case _ => n * factorial(n - 1)  // otherwise

println(factorial(6))    // 720

// a nested function: note the indentation
def abs(n: Int): Int =
  def sign(m: Int): Int = m match
    case i if i > 0 => 1
    case 0 => 0
    case _ => -1
  n * sign(n)

println(s"${abs(-2)}, ${abs(2)}, ${abs(0)}")  // 2, 2, 0

// tail recursion, checked, in a nested function
def factorial2(n: Int): Int =
  @annotation.tailrec             // only checks that the optimisation is possible
  def _fact(n: Int, acc: Int): Int = n match
    case 0 | 1 => acc
    case _ => _fact(n - 1, n * acc)
  _fact(n, 1)

println(factorial2(6))   // 720

A method is much like a val holding a function (compare square and square2), but it also allows currying, generics, annotations and nesting, and becomes a bytecode method of a class or object. Input types are mandatory, the return type optional but usually given. Methods can nest, which Java does not allow: sign exists only inside abs. case 0 | 1 matches either value.

When is recursion efficient?

Recursion is compiled into a loop only if it is tail recursion: every recursive call is the last expression evaluated before returning. factorial still has a multiplication to do after the call returns; _fact carries the partial product in an accumulator:

factorial(3)                    _fact(3, 1)
= 3 * factorial(2)              = _fact(2, 3)
= 3 * (2 * factorial(1))        = _fact(1, 6)
= 3 * (2 * 1)                   = 6
= 6

The left column grows with the pending multiplications kept on the stack; the right one runs in constant space. @annotation.tailrec changes nothing in the code: it only makes compilation fail when the call is not tail ("Cannot rewrite recursive call: it is not in tail position", on factorial).

7. What is currying?

A method can have several parameter lists: def f(x1: T1,…)(…)(…): T0 = e.

// a standard function, no currying
def mult(x: Double, y: Double): Double = x * y

// a curried function: curriedMult actually has type Double => (Double => Double)
def curriedMult(x: Double)(y: Double): Double = x * y

// slightly different syntax at the call site
println(mult(10, 2))          // 20.0
println(curriedMult(10)(2))   // 20.0

// curriedMult can be partially applied
val twice: Double => Double = curriedMult(2)
println(twice(10))            // 20.0

// => is right-associative, so this type is Double => (Double => Double)
val curriedMultAsFunction: Double => Double => Double = x => y => x * y
println(curriedMultAsFunction(10)(2))  // 20.0

Currying performs a multi-argument application as successive applications of a function and its results: a function returning a function returning a function… It gives partial application: curriedMult(2) fixes the first argument and returns a Double => Double. (The results print 20.0 because they are Doubles.) Currying also groups arguments, for readability (a strategy argument in its own list) or for type inference, which proceeds one list at a time; foldLeft in lesson 3 relies on it.

8. How do you model data with product and sum types?

An algebraic data type is built by composition from atomic types, in two ways: a product type (Cartesian product, a record) contains a part of type T1 and one of type T2; a sum type (disjoint union) is either a T1 or a T2, never both.

Product types: case classes

// a new product type, aka a record type
case class Point2D(x: Double, y: Double)
val p: Point2D = Point2D(10, 20)
println(p)       // Point2D(10.0,20.0): a string representation for free

// matching to manipulate a point declaratively
def rotate(p: Point2D): Point2D = p match
  case Point2D(x, y) => Point2D(y, -x)

// matching over couples
def sum(p1: Point2D, p2: Point2D): Point2D = (p1, p2) match
  case (Point2D(x1, y1), Point2D(x2, y2)) => Point2D(x1 + x2, y1 + y2)

// partial matching
def getX(p: Point2D): Double = p match
  case Point2D(x, _) => x

// a "fluent setter" that creates a new record
def chgX(p: Point2D, x: Double): Point2D = p match
  case Point2D(_, y) => Point2D(x, y)

println(rotate(Point2D(10, 20)))              // Point2D(20.0,-10.0)
println(sum(Point2D(10, 20), Point2D(3, 4)))  // Point2D(13.0,24.0)
println(getX(Point2D(10, 20)))                // 10.0
println(chgX(Point2D(10, 20), 11))            // Point2D(11.0,20.0)

A case class is a record that can be matched using values, variables or underscores for its fields, and gets a readable toString and structural equality. The tuple (p1, p2) is the case class Tuple2(p1, p2), which is how sum matches two points at once. (The deck's comments give 10 and Point2D(11,20) for the last two lines; the fields are Doubles, so the real output is 10.0 and Point2D(11.0,20.0).)

Records plus functions give almost everything an object gives, but FP keeps data and functions separate, and that is a feature.

Sum types: enums

// a new sum type, defined by enumerating its cases
enum Person:
  case Student(name: String, year: Int)
  case Teacher(name: String, course: String)

// a value of type Person is either a Student OR a Teacher
val p: Person = Person.Student("mario", 2015)

// an algorithm over Person
def name(p: Person): String = p match
  case Person.Student(n, _) => n
  case Person.Teacher(n, _) => n

println(name(p))        // mario

enum WeekDay:           // a Java-like enumeration
  case Monday, Tuesday, Wednesday, Thursday, Friday

def preferredDay(d: WeekDay): Boolean =
  d == WeekDay.Friday   // could have used matching instead

println(preferredDay(WeekDay.Monday))  // false

enum IntList:           // a recursive type: a linked list of Int
  case Cons(head: Int, tail: IntList)
  case Nil

def sum(l: IntList): Int = l match
  case IntList.Cons(h, t) => h + sum(t)
  case _ => 0

println(sum(IntList.Cons(10, IntList.Cons(20, IntList.Nil))))  // 30

An enum is the sum of some product types; a zero-argument case is a singleton. Hence three kinds: an enumeration of singletons like a Java enum (WeekDay), a sum of records like a class hierarchy (Person), a recursive sum like a linked list (IntList). Cases are qualified by the enum name unless imported. Enums cannot express every ADT, but suffice for now. The compiler checks that a match covers every case, with a warning:

enum Person:
  case Student(name: String, year: Int)
  case Teacher(name: String, course: String)

def name(p: Person): String = p match   // warning: match may not be exhaustive.
                                        // It would fail on pattern case: Person.Teacher(_, _)
  case Person.Student(n, _) => n

Subtyping, or inclusive polymorphism

T <: R (reflexive and transitive, a preorder) means a T can be passed where an R is expected. A sum type is a supertype of its cases (Student <: Person), and matching recovers the case at the receiving site. For functions, (T1,…,Tn) => T0 <: (R1,…,Rn) => R0 iff the result is covariant (T0 <: R0) and each argument contravariant (Ri <: Ti); no matching is needed.

enum Person:
  case Student(name: String, year: Int)
  case Teacher(name: String, course: String)
import Person.*

val s: Person = Student("mario", 2015)   // Student <: Person: no conversion needed

// (Person => Student) <: (Student => Person)
val f: Student => Person = (p: Person) => Student("m", 2015)
println(f(Student("mario", 2015)))       // Student(m,2015)

Callers of f pass a Student and use the result as a Person. A function accepting any Person handles the Student (argument may be wider), and the Student it returns is a Person (result may be narrower). The reverse is unsafe, since a caller of a Person => Student may pass a Teacher, and is rejected:

val g: Person => Student = (s: Student) => s
                           ^^^^^^^^^^^^^^^^^
Found:    Person.Student => Person.Student
Required: Person => Person.Student

T ::= Int | Double | Boolean | String            primitives
    | (T1,…,Tn) => T0                              functions
    | C | E                                        case classes, enums

D ::= val x: T = v                                 value
    | def f(x1: T1,…,xn: Tn): T0 = e               function
    | case class C(x1: T1,…,xn: Tn)                product type
    | enum E: … case C(…)                          algebraic data type

e ::= v | v1 op v2 | ef(e1,…,en) | (x1,…,xn) => e1 … en     functional
    | { case p1 => e1; … } | e match { case … }             matching
    | C(e1,…,en)                                             record

9. How do you organise and test functional code?

A module groups definitions under a namespace, some public, some private; public ones are accessed as module.defname. The operations on a type go into a module with the type's name. In Scala a module is an object, and import ModuleName.* removes the prefix.

// an ADT: type + module
enum Person:
  case Student(name: String, year: Int)
  case Teacher(name: String, course: String)

object Person:
  def name(p: Person): String = p match
    case Student(n, _) => n
    case Teacher(n, _) => n

println(Person.name(Person.Student("mario", 2015)))  // mario

import Person.*

println(name(Student("mario", 2015)))                // mario

// a method outside the Person module
def isStudent(p: Person): Boolean = p match
  case Student(_, _) => true
  case _ => false

println(isStudent(Student("mario", 2015)))           // true

The object named like the enum is its companion: inside it the cases need no qualification, and the import brings in both operations and cases. Since the enum's structure is public, outside code such as isStudent can still match on it; lesson 3 hides it.

JUnit works in Scala if you want to keep TDD (proper Scala test frameworks come later). In FP a test typically contains only assertions, and case-class equality makes them natural; the three tests below pass.

import org.junit.*
import org.junit.Assert.*

class RecordTest:

  case class Item(desc: String, code: Int)
  val record = Item("a", 10)

  @Test def testMatches() =
    assertTrue(record match { case Item(x, 10) => true; case _ => false })
    assertTrue:        // significant indentation style
      record match
        case Item("a", 10) => true
        case _ => false

  @Test def testEquality() =
    assertEquals(record, Item("a", 10))
    assertNotEquals(record, Item("a", 11))

  @Test def testChangeCode() =
    def changeCode(item: Item)(f: Int => Int): Item = item match
      case Item(desc, code) => Item(desc, f(code))
    assertEquals(Item("a", 11), changeCode(Item("a", 10))(_ + 1))

scalaVersion := "3.3.5"

lazy val root = (project in file("."))
  .settings(
    name := "pps-code-scala",
    libraryDependencies += "com.github.sbt" % "junit-interface" % "0.13.2" % Test
  )

10. Lab 02: exercises and solutions

The lab (fork unibo-pps/pps-lab02) practises this lesson; each solution below was compiled and run, and the comments show the real output.

object HelloScala extends App:
  println("Hello, Scala")   // Hello, Scala

def mult(x: Int, y: Int): Int = x * y
def multCurried(x: Int)(y: Int): Int = x * y
val multiplyBy3 = multCurried(3)        // partial application: Int => Int
println((mult(3, 4), multCurried(3)(4), multiplyBy3(5)))  // (12,12,15)

def divide(x: Double, y: Double): Double = x / y
def divideCurried(x: Double)(y: Double): Double = x / y
val half: Double => Double = divideCurried(_)(2)  // fixes the SECOND argument
println((divide(1, 4), half(9), divide(1, 0), divide(0, 0)))  // (0.25,4.5,Infinity,NaN)

// (i) a val holding a function literal
val positive: Int => String = _ match
  case x if x >= 0 => "positive"
  case _ => "negative"

// (ii) method syntax
def positiveM(x: Int): String = x match
  case x if x >= 0 => "positive"
  case _ => "negative"

println((positive(0), positive(-3), positiveM(7)))  // (positive,negative,positive)

// type first: (String => Boolean) => (String => Boolean)
val neg: (String => Boolean) => (String => Boolean) = p => s => !p(s)
def negM(p: String => Boolean): String => Boolean = s => !p(s)
// generic version (a def can have type parameters)
def negG[A](p: A => Boolean): A => Boolean = a => !p(a)

val empty: String => Boolean = _ == ""   // a predicate on strings
val notEmpty = neg(empty)                // notEmpty: String => Boolean
println(notEmpty("foo"))                 // true
println(notEmpty(""))                    // false
println(notEmpty("foo") && !notEmpty(""))                   // true
println(negM(empty)("foo") && negG[Int](_ > 0)(-1))         // true

// x <= y = z, in four variants
val p1: Int => Int => Int => Boolean = x => y => z => x <= y && y == z  // curried val
val p2: (Int, Int, Int) => Boolean = (x, y, z) => x <= y && y == z      // non-curried val
def p3(x: Int)(y: Int)(z: Int): Boolean = x <= y && y == z               // curried def
def p4(x: Int, y: Int, z: Int): Boolean = x <= y && y == z               // non-curried def

println((p1(1)(2)(2), p2(1, 2, 3), p3(3)(2)(2), p4(2, 2, 2)))  // (true,false,false,true)

// function composition: (f o g)(x) = f(g(x))
def compose(f: Int => Int, g: Int => Int): Int => Int = x => f(g(x))
println(compose(_ - 1, _ * 2)(5))   // 9
// the generic version works for any types that line up
def composeG[A, B, C](f: B => C, g: A => B): A => C = x => f(g(x))
println(composeG((s: String) => s.length, (i: Int) => "x" * i)(4))  // 4

def power(base: Double, exponent: Int): Double = exponent match
  case 0 => 1
  case n => base * power(base, n - 1)

def powerTail(base: Double, exponent: Int): Double =
  @annotation.tailrec
  def loop(n: Int, acc: Double): Double = n match
    case 0 => acc
    case _ => loop(n - 1, acc * base)
  loop(exponent, 1)

println((power(2, 3), power(5, 2), powerTail(2, 10)))  // (8.0,25.0,1024.0)

def reverseNumber(n: Int): Int =
  @annotation.tailrec
  def loop(rest: Int, acc: Int): Int = rest match
    case 0 => acc
    case _ => loop(rest / 10, acc * 10 + rest % 10)
  loop(n, 0)

println(reverseNumber(12345))   // 54321

enum Expr:
  case Literal(value: Int)
  case Add(left: Expr, right: Expr)
  case Multiply(left: Expr, right: Expr)

object Expr:
  def evaluate(expr: Expr): Int = expr match
    case Literal(v) => v
    case Add(l, r) => evaluate(l) + evaluate(r)
    case Multiply(l, r) => evaluate(l) * evaluate(r)

  def show(expr: Expr): String = expr match
    case Literal(v) => v.toString
    case Add(l, r) => "(" + show(l) + " + " + show(r) + ")"
    case Multiply(l, r) => "(" + show(l) + " * " + show(r) + ")"

@main def tryExpr =
  import Expr.*
  val e = Multiply(Add(Literal(1), Literal(2)), Literal(4))
  println(show(e))       // ((1 + 2) * 4)
  println(evaluate(e))   // 12

import org.junit.*
import org.junit.Assert.*
import Expr.*

class ExprTest:
  val e = Add(Literal(2), Multiply(Literal(3), Literal(4)))

  @Test def testEvaluate() =
    assertEquals(7, evaluate(Add(Literal(3), Literal(4))))
    assertEquals(14, evaluate(e))

  @Test def testShow() =
    assertEquals("5", show(Literal(5)))
    assertEquals("(2 + (3 * 4))", show(e))

object Optionals:
  enum Optional:
    case Just(value: Int)
    case Empty()

  object Optional:
    def mapInt(optional: Optional)(f: Int => Int): Optional = optional match
      case Just(v) => Just(f(v))
      case _ => Empty()

    def filter(optional: Optional)(p: Int => Boolean): Optional = optional match
      case Just(v) if p(v) => optional
      case _ => Empty()

@main def tryOptionals =
  import Optionals.*, Optional.*
  println(mapInt(Just(5))(_ + 1))    // Just(6)
  println(mapInt(Empty())(_ + 1))    // Empty()
  println(filter(Just(5))(_ > 2))    // Just(5)
  println(filter(Just(5))(_ > 8))    // Empty()
  println(filter(Empty())(_ > 2))    // Empty()

Check your understanding