Object-oriented programming treats everything as an object with encapsulated state and behaviour. This works well for many domains, but it has limits:
FP offers a declarative style: you describe what the result should be, not how to achieve it step by step. This leads to terser, more composable, and more confidently correct code — especially when concurrency enters the picture.
| OO approach | FP thinking |
|---|---|
| Everything is an object — verbose for simple behaviour | Functions are first-class values — pass them around directly |
| Functional interfaces require boilerplate | Function literals are lightweight and pervasive |
| Step-by-step instruction focus | Declarative, goal-oriented composition |
| Mutable state complicates concurrency | Immutability by default simplifies parallelism |
Modern OO languages have been absorbing FP ideas: Java 8+ added lambdas and streams; C# has LINQ; Kotlin has function types and immutability as a design principle. Scala was the pioneer that proved OOP and FP could coexist smoothly on the JVM.
Why is declarativity valuable for concurrent and distributed systems? What property of pure functions makes them safe to evaluate in parallel?
Scala ("Scalable Language") was designed by Martin Odersky at EPFL starting in 2001, with the first public release in 2004. Scala 3 (2021) is the version we use — specifically 3.3.5. It compiles to JVM bytecode (also JavaScript and native).
| Feature | What it means |
|---|---|
| Strong, expressive type system | Intersection types, union types, type inference, enums, opaque types |
| Purely object-oriented | Every value is an object, every operation is a method call |
| Full FP support | Functions as values, pattern matching, immutability, algebraic data types |
| Syntactic flexibility | Significant indentation, infix operators, DSL-friendly |
SBT (Scala Build Tool) is the standard build system. The REPL (scala or sbt console) evaluates expressions interactively — essential for exploration. IntelliJ IDEA (with the Scala plugin) and VS Code (with Metals) are the common IDEs.
In pure FP, every program entity is a value. Values are immutable — once bound to a name, they never change. This eliminates entire classes of bugs caused by unexpected mutation.
// values can be associated to names — non-modifiable variables
val v = 1
// types are optional (typically inferred)
val w: Int = 1
// right-hand side can be any expression
val z = v + 5
println(z)
val a = 1
println("result is " + a) // Java-style concatenation
println(s"result is $a") // string interpolation
println(s"result is ${a+1}") // with expression evaluation
// primitive types mirror JVM
val i: Int = 10 + 5 // as in Java, interpreted as +(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 method as operator
val n: String = null // null can be passed to "objects"
val u: Unit = () // the Unit type has a single value: ()
Scala 3 style conventions: never put spaces between function name and parameter list; always put spaces around operators; never after '(' or before ')'; always after a comma, never before.
val declares an immutable binding — think of it as naming a value, not declaring a variable. There is no null in pure FP; Scala retains it only for JVM interop.
A function type is written (T1, ..., Tn) => T0. A function literal (also called lambda or anonymous function) is written (x1, ..., xn) => expression.
There are four idiomatic styles for expressing a function value:
| Style | Example | When to use |
|---|---|---|
| Typed literal + typed val | val f1: (Int,Int)=>Int = (x:Int,y:Int)=>x+y | Explicit documentation |
| Typed literal + untyped val | val f2 = (x:Int,y:Int)=>x+y | Inferred return type |
| Untyped literal + typed val | val f3: (Int,Int)=>Int = (x,y)=>x+y | Clean body, known signature |
| Placeholder syntax | val f4: (Int,Int)=>Int = _ + _ | Short, each _ is a parameter |
A function body can contain multiple expressions; the last one is the return value:
val g: Int => Int =
(x: Int) =>
println("hello") // side-effect
x + 1 // return value
println(g(10)) // prints "hello", then 11
A special case: 0-argument functions use ()=>T, 1-argument can be written x=>e or =>T (by-name, discussed later).
A higher-order function (HOF) takes a function as an argument or returns one as a result. This is the FP equivalent of the Strategy pattern — and far more concise.
Higher-order functions are the FP way of making code reusable and configurable. Instead of writing many similar functions, you write one function parameterised by the varying behaviour — expressed as a function argument.
When a function returns a function, we enter the territory of currying (see section 8). The function type arrow is right-associative: A => B => C means A => (B => C).
Pattern matching is the FP alternative to the switch statement, but far more powerful: it can destructure values, bind variables, and apply guards.
What is the difference between a total function and a partial function in the context of pattern matching? What happens when you call a partial function outside its domain?
A case block { case p1 => e1; ... } defines a partial unary function. It's "partial" because it can fail on inputs that don't match any case, raising scala.MatchError. The syntax _ match followed by indented cases is the idiomatic Scala 3 style.
Scala 3 uses significant indentation (like Python) as the default. Curly braces remain available for single-line or Java-interop code. For complicated blocks, you can add end res markers. The course uses significant indentation consistently.
A def defines a method. Unlike a val holding a function, a method supports currying, generics, annotations, and nesting. Methods can be defined inside other methods — something Java does not allow.
Scala optimises tail-recursive calls into a loop (no stack growth). A call is tail-recursive if it is the very last expression evaluated before returning. Use @annotation.tailrec to verify: if the recursion isn't tail, the code won't compile.
Currying transforms a function that takes multiple arguments into a chain of single-argument functions. This enables partial application — fixing some arguments to produce a more specialised function.
Currying is not just a syntactic trick. It lets you configure a function once and reuse it many times. In the slides, configuration/strategy arguments are often grouped by currying to enable this pattern.
The function type arrow => is right-associative, so Double => Double => Double is Double => (Double => Double). A curried function literal x => y => x * y has exactly that type.
A product type represents a value that contains all of its components — a Cartesian product of sets. In Scala, case class defines a product type (also called a record).
Case classes give you: automatic toString, equals, hashCode, copy, and destructuring in pattern matching — all for free.
In FP, data (case class fields) and behaviour (functions operating on them) are kept separate. This contrasts with OOP, where data and methods are encapsulated together. Why might separation be a feature rather than a drawback? Think about what happens when you want to add a new operation.
While a product type is a value that has all components, a sum type is a value that is exactly one of several alternatives — a disjoint union of sets. Together, products and sums form Algebraic Data Types (ADTs).
An enum in Scala 3 defines a new type as the sum of a number of (possibly 0-argument) product types. This gives you the full power of ADTs: enumerate singletons (like Java enums), model hierarchies (a Person is a Student or Teacher), or build recursive structures like linked lists.
Pattern matching is the natural way to consume an ADT — the compiler can even warn you if your match is not exhaustive (a huge safety advantage).
The subtype relation T <: R means "any value of type T can be used where R is expected." It is reflexive and transitive (a preorder).
For sum types, each case is a subtype of the enum — e.g. Student <: Person. Pattern matching recovers the specific type at the receiving site.
For functions, subtyping follows two rules simultaneously (contravariance on arguments, covariance on return):
// (T1,...,Tn) => T0 <: (R1,...,Rn) => R0 iff:
// T0 <: R0 (covariant on return)
// Ri <: Ti (contravariant on each argument)
val f: Student => Person = (p: Person) => Student("m", 2015)
Intuitively: if you need a function that works on any Person, it's safe to pass one that works on a subtype (Student). Conversely, if you need a function returning Person, you can pass one that returns a more specific type.
In FP, modules group related definitions (types + functions) under a namespace. This is how you structure code in the absence of classes as the primary organisational unit.
In FP, why is it idiomatic to define types in an enum and algorithms in a companion object, rather than putting methods inside the type itself? What does this say about the relationship between data and behaviour?
Generics (parametric polymorphism) let you write code that works uniformly across many types. In Scala the syntax uses square brackets [A, B, ...].
Type inference for generics is very effective: you rarely need to specify type arguments explicitly, especially at the call site.
Two canonical generic data structures demonstrate the power of ADTs + generics + higher-order functions.
Optional[A] models a value that may or may not be present — a safer alternative to null.
enum Optional[A]:
case Just(a: A)
case Empty()
object Optional:
def isEmpty[A](opt: Optional[A]): Boolean = opt match
case Empty() => true
case _ => false
def orElse[A, B >: A](opt: Optional[A], orElse: B): B = opt match
case Just(a) => a
case _ => orElse
def map[A, B](opt: Optional[A])(f: A => B): Optional[B] = opt match
case Just(a) => Just(f(a))
case _ => Empty()Sequence[A] is a generic singly-linked list — the fundamental persistent data structure in FP.
enum Sequence[E]:
case Cons(head: E, tail: Sequence[E])
case Nil()
object Sequence:
def sum(l: Sequence[Int]): Int = l match
case Cons(h, t) => h + sum(t)
case _ => 0
def map[A, B](l: Sequence[A])(mapper: A => B): Sequence[B] = l match
case Cons(h, t) => Cons(mapper(h), map(t)(mapper))
case Nil() => Nil()
def filter[A](l: Sequence[A])(pred: A => Boolean): Sequence[A] = l match
case Cons(h, t) if pred(h) => Cons(h, filter(t)(pred))
case Cons(_, t) => filter(t)(pred)
case Nil() => Nil()The combination of product types (case classes), sum types (enums), generics, and higher-order functions is remarkably expressive. It lets you define the structure of data once, and then compose operations over it using map, filter, fold — without ever resorting to mutable state or iteration.
The lambda calculus (Alonzo Church, 1930) is the formal foundation of all functional programming. It is stunningly simple: just three syntactic forms.
L ::= x | (lambda;x.L) | L1 L2
A lambda is either a variable, an abstraction (function) binding a variable, or an application (calling a function with an argument).
| Lambda calculus | Scala equivalent |
|---|---|
x | x (a variable / parameter name) |
lambda;x.L | x => L (function literal) |
L1 L2 | L1(L2) (function application) |
Beta-reduction is the single computational rule:
(lambda;x.LB) LP --> LB{LP/x}
"Calling a function gives the body LB after substituting formal parameter x with actual LP"
Given the Church encoding T := lambda;x.lambda;y.x and F := lambda;x.lambda;y.y, derive the reduction steps for Not F where Not := lambda;x.x F T.
The lambda calculus is Turing-complete: any computable function can be expressed. You can encode booleans, naturals (Church numerals), pairs, lists, and even recursion (via the Y combinator) using only functions.
The fact that every other programming construct (multi-argument functions, conditionals, loops, data structures) can be derived from just functions is why the lambda calculus is considered the mathematical foundation of computation — alongside Turing machines.
A critical property of the lambda calculus is confluence (the Church-Rosser theorem): if an expression can reduce to two different forms, there exists a third form that both can reach.
flowchart TD L["L (original expression)"] --> L1["L1"] L --> L2["L2"] L1 --> L3["L3 (common result)"] L2 --> L3
If a program terminates, its result is unique regardless of evaluation order (don't-care nondeterminism). This implies referential transparency: you can replace an expression with its value without changing the program's meaning — enabling equational reasoning, refactoring, and fearless composition.
Declarativity in FP means you express what result you want, not the step-by-step how. A composition like sum(map(filter(l)(>=20))(_+1)) says nothing about order of evaluation. A parallel or distributed system can evaluate it differently — the result is the same.
While declarativity means we often don't care about evaluation order, sometimes we do — for performance reasons or because of side-effects. Scala supports three strategies.
| Strategy | When argument is evaluated | Scala syntax |
|---|---|---|
| Call-by-value (strict) | Once, before function body | def f(a: A) — default |
| Call-by-name (non-strict) | Each time it is used in the body | def f(a: => A) |
| Call-by-need (lazy) | Once, first time it is used | def f(a: => A) + lazy val v = a |
Given the function def sPairBN[A](a: => A, dummy: => A): (A, A) = (a, a), explain the output of sPairBN({println("e1"); 10}, {println("e2"); 20}) — and contrast it with what call-by-value would produce.
A Stream is essentially a lazy linked list. The tail — and optionally the head — is computed only when needed. This enables modelling infinite sequences, such as the natural numbers or Fibonacci series.
The key trick: the Cons case holds thunks (0-argument functions) instead of strict values, and cons uses by-name parameters with lazy val to cache results.
lazy val corec: Stream[Int] = Stream.cons(1, corec) // infinite stream of 1s
println(Stream.toList(Stream.take(corec)(10))) // [1,1,...,1]
Streams decouple description from evaluation. You describe a potentially infinite sequence (Stream.iterate(0)(_ + 1)) and then decide how much of it to realise. This is the engine behind big data frameworks like Apache Spark — which was itself written in Scala.
Extension methods let you add new methods to existing types — without inheritance or modifying the original type. They are purely syntactic sugar that extracts one argument to become the "receiver."
With extension methods, you can write fluent pipelines:
val seq = Cons(10, Cons(20, Cons(30, Nil())))
println(seq.filter(_ >= 20).map(_ + 1).sum) // 52
Extension methods are not about adding behaviour to objects in the OOP sense. They are a syntactic convenience that allows module-defined operations to be chained — keeping the FP discipline (data and behaviour separate) while giving the ergonomics of method-call syntax.
Referential transparency means an expression can be replaced by its value without changing the program's meaning. The Church-Rosser theorem states that if a lambda term reduces to two different forms, there is always a third form reachable from both. This implies a unique normal form (if one exists), so the result of a terminating program is independent of evaluation order — the fundamental enabler of equational reasoning.
A val f: A => B = ... evaluates its right-hand side once and stores the function object. A def f(a: A): B = ... creates a JVM method which can support generics (def f[A](...)), currying in separate parameter lists, annotations like @tailrec, and nesting inside other defs.
It returns a function of type Double => Double that doubles its argument — i.e., y => 2 * y. Partial application at work.
Because Scala's enum cases are known at compile time. The compiler can verify that all cases are covered in a match expression. If a case is missing, it issues a warning (or an error with the right flag). This eliminates a class of runtime bugs.
Recall: T := lambda;x.lambda;y.x, F := lambda;x.lambda;y.y, Not := lambda;x.x F T, And := lambda;x.lambda;y.x y F.
And (Not F) T
= And ((lambda;x.x F T) F) T
-> And (F F T) T
-> And ((lambda;x.lambda;y.y) F T) T
-> And T T
= (lambda;x.lambda;y.x y F) T T
-> (lambda;y.T y F) T
-> T T F
= (lambda;x.lambda;y.x) T F
-> F
Result: F (falseness).
With call-by-value (default), loop(20) is evaluated before being passed, causing infinite recursion (stack overflow). With call-by-name (=> A), loop(20) is never evaluated because dummy is unused in the body — the result would be (10, 10).
def compose(f: Int => Int, g: Int => Int): Int => Int = x => f(g(x)). Usage: compose(_ - 1, _ * 2)(5) gives 9.
A Stream stores its head and tail as thunks (by-name / () => A), while a Sequence stores them as strict values. This means Stream can represent infinite sequences; its elements are computed on demand and optionally cached via lazy val.
(T1,...,Tn) => T0 <: (R1,...,Rn) => R0 iff R1 <: T1, ..., Rn <: Tn (contravariant on arguments) and T0 <: R0 (covariant on return). Example: if Student <: Person, then Person => Student <: Student => Person. Why? A function expecting a Student can be given a Person (any Person is a Student? No — contravariance says the opposite: the argument type can be more general). Actually the function that accepts Person is a subtype of one that accepts Student: because it's safe to call a Person-accepting function with a Student argument.
The companion object holds the operations (algorithms) that work on the type. This keeps data definitions (the enum with its cases) separate from behaviour (the functions in the object) — a hallmark of the FP organisational style. The object can also contain factory methods and private implementation details.