CS3510 Functional Programming and Applications Complete Revision Notes 2026

Course Overview and Administrative Details

Module Name: CS3510 Functional Programming and Applications.
Revision Guide Year: 2026 Exam, Academic Year 2025 / 2026.
Instructor: Prof. Zhaohui Luo (ZHL), Royal Holloway, University of London.
Core Languages: Haskell (learned in Part 1) and Scala (learned in Part 2).
Core Concepts Covered: * Types and Polymorphism. * Recursion (Natural to mathematicians, often alien to CS students). * Higher-order functions. * List comprehensions. * Algebraic data types. * Lazy evaluation. * Multi-paradigm programming.

Exam Format and Consistent Structural Patterns

Exam Duration: 2 hours.
Structure: Total of 100 marks, consisting of 4 main questions worth 25 marks each. All questions are mandatory (no choice).
Sub-divisions: Each main question is divided into parts (a, b, c, d), with sub-parts worth between 2 and 10 marks.
Permitted Materials: Calculators are explicitly not permitted (standard since 2024).
Consistent Question Mapping: * Question 1: Foundational Haskell concepts including polymorphism, currying, list operations, and basic function definitions. * Question 2: List evaluation exercises (c1–c5 or k1–k5 style), identifying type errors, defining standard functions via list comprehension, and recursion (Fibonacci or factorial). * Question 3: Scala and multi-paradigm programming. Includes closures (var/val interaction), for-comprehensions, factors/prime logic, quicksort in Scala, and comparison of == in Scala versus Java. * Question 4: Type declarations (type alias recursion errors), evaluation strategies (innermost vs. outermost), lazy evaluation (f applied to $\perp$ ), and binary trees (definitions and height functions).

Detailed Topic Analysis from Past Papers (2023–2025)

1. Polymorphism (Parametric & Ad Hoc): * Parametric Polymorphism: A function has a single definition that works uniformly for any type. Uses type variables (e.g., $a$ ). Example: $length :: [a] \rightarrow Int$ . * Ad Hoc Polymorphism (Overloading): The same operator or function name has different implementations for different types, mediated by type classes. Example: $(+)$ works for Int and Float via the $Num$ class.
2. Currying and Partial Application: * Currying: Transforming a function on pairs/tuples into a sequence of single-argument functions. In Haskell, $f :: a \rightarrow b \rightarrow c$ actually means $a \rightarrow (b \rightarrow c)$ . * Partial Application: Applying a curried function to fewer arguments than expected to produce a new function (e.g., $add \, 1$ creates an increment function). * Conventions: The arrow $\rightarrow$ associates to the right; function application associates to the left.
3. List Evaluation Exercises: Usually involves evaluating a sequence of constants (c1–c5). Requires knowledge of $(:)$ (cons), $(++)$ (append), $take$ , $drop$ , $length$ , $reverse$ , and $zip$ .
4. Type Errors and Incorrect Definitions: Given a target type (e.g., $[a] \rightarrow a$ ), identify the actual type of incorrect implementations. Reasons for mismatch include returning a list instead of an element or using operators that restrict polymorphism (like $(+)$ ).
5. List Comprehension Principles: Creating functions like $concat$ , $filter$ , $sorted$ , and $uppers$ using the syntax: $[expr \, | \, x \leftarrow xs, \, guard]$ .
6. Scala Closures and Mutability: Predicting values when a closure captures a mutable variable ( $var$ ). In Scala, closures capture the variable reference. Change in $var$ after the closure is defined will affect the closure's output.
7. Multi-Paradigm Programming: * Definition: A language supporting multiple styles (e.g., Scala supporting FP + OOP). * Advantages: Increased productivity, flexibility, and the ability for one team to work in one language using different styles. * Polyglot vs. Multi-Paradigm: Polyglot uses different languages in one environment; multi-paradigm uses one language with multiple styles.
8. Evaluation Strategies: * Innermost Reduction (Call by Value): Reduce the innermost redex first; arguments are evaluated before being passed to functions. * Outermost Reduction (Call by Name): Reduce the outermost redex first; function definitions are expanded before arguments are evaluated. * Lazy Evaluation: Defined as Outermost Reduction + Sharing (to avoid duplicate computation).
9. Binary Tree Operations: Defining $data \, Tree \, a = Leaf \, a \, | \, Node \, (Tree \, a) \, a \, (Tree \, a)$ and a recursive height function: $height \, (Leaf \, _) = 0$ ; height \, (Node \, l \, _ \, r) = 1 + max(height \, l)(height \, r).
10. Quicksort Implementations: * Haskell: Uses list comprehension. $qsort \, [] = []$ ; $qsort \, (x:xs) = qsort \, smaller \, ++ \, [x] \, ++ \, qsort \, larger$ (where smaller contains elements $\le x$ and larger contains elements > x). * Scala: Uses pattern matching and for-comprehension. Utilizes $(:::)$ for list concatenation.
11. Infinite Lists and Bottom ( $\perp$ ): * Bottom ( $\perp$ ): Represents a non-terminating computation. * Lazy Evaluation Behavior: If a function $f \, x = 10$ (ignores its argument), then $f \, \perp$ terminates and returns $10$ because $\perp$ is never evaluated.

Comprehensive Definitions and Frameworks

Church-Rosser Property: If an expression $e$ can be reduced to both $e_1$ and $e_2$ via different paths, there exists an expression $e'$ that both $e_1$ and $e_2$ can eventually reach. This guarantees that final values are deterministic in pure languages.
Redex (Reducible Expression): A sub-expression that can be simplified. Includes Delta-redexes (expanding definitions) and Beta-redexes (applying lambda abstractions).
Type Synonym (type): An abbreviation for an existing type; cannot be recursive (e.g., $type \, String = [Char]$ ).
Algebraic Data Type (data): Defines a new type with constructors; can be recursive.
Scala == vs. Java ==: In Scala, $==$ performs structural/value equality (identical to Java's $.equals$ ). In Java, $==$ checks reference equality.
Lambda Expression: An anonymous function (without a name). Once a lambda is reached, redexes inside are generally ignored; the lambda is a normal form.

Lecture Signals and Important Quotes (2026)

January 23: Type inference allows the machine to help find types; in pure FP, there are no variables, only constants.
January 30: Haskell is strongly typed. Lists must contain elements of the same type. $Num \, a \implies [a] \rightarrow a$ involves a class constraint.
February 6: Pattern matching is the primary way functions are defined; order in pattern matching is critical. Currying is useful for partial application.
March 20: "Lazy evaluation is very important… quite unique for functional programming." Outermost reduction is the best for termination.
Example Walkthrough: Evaluating $square(3+4)$ . Innermost: $square(7) \rightarrow 7 \times 7 \rightarrow 49$ . Outermost: $(3+4) \times (3+4) \rightarrow 7 \times (3+4) \rightarrow 7 \times 7 \rightarrow 49$ (sharing prevents the second $(3+4)$ from being re-calculated).

Ranked Study Priorities for 2026 Exam

Priority 1: Lazy Evaluation & Strategies. Must know the definition (outermost + sharing), its impact on termination ( $f \, \perp$ ), and the Church-Rosser property.
Priority 2: Polymorphism (Parametric vs. Ad Hoc). Know both definitions and examples (length vs. sum/plus).
Priority 3: List Evaluation Steps. Practice step-by-step resolution of expressions using all standard list functions.
Priority 4: Type Errors. Be able to explain why a definition has a specific type that differs from the target.
Priority 5: Scala Closures. Understand the reference-capture mechanism of $var$ .
Priority 6: Scala for-comprehensions. Specifically for defining $factors$ and $prime$ predicates.
Priority 7: Type Alias Recursion Error. Explain why $type \, A = (String, \, A \rightarrow Char)$ is invalid (synonyms must be fully expandable).
Priority 8: Higher-Order Functions. Definitions and defining $map$ , $filter$ , or $foldr$ .
Priority 9: Binary Trees. Recursive height/depth and structural definitions.
Priority 10: Currying & Conventions. Right-associativity of arrows and left-associativity of application.

Out of Scope / Unlikely Topics

Lambda Calculus Formal Theory: Beta-reduction rules or Church encodings (only the notation is used).
Set Theory: Formal foundations like ZF set theory or Russell's paradox.
Advanced Type Theory: Martin-Lof type theory, dependent types (Agda/Coq), and Algorithm W (Damas-Milner).
Parallel Programming: Parallel execution research topics.
Formal Mu-recursion: General recursive function theory or Turing equivalence.

Code Implementation Reference

Haskell Quicksort: $qsort \, [] = []$ qsort \, (x:xs) = qsort \, [a \, | \, a \leftarrow xs, \, a \le x] \, ++ \, [x] \, ++ \, qsort \, [b \, | \, b \leftarrow xs, \, b > x]
Scala Quicksort: def \, qsort(xs:List[Int]):List[Int] = xs \, match { $case \, Nil \implies Nil$ case \, x::ys \implies qsort(for(i \leftarrow ys \, if \, i \le x) \, yield \, i) \, ::: \, List(x) \, ::: \, qsort(for(j \leftarrow ys \, if \, j > x) \, yield \, j) }
Haskell Fibonacci: $fibs = 0 : 1 : [x+y \, | \, (x,y) \leftarrow zip \, fibs \, (tail \, fibs)]$ $fib \, n = fibs \, !! \, n$
Scala Factors and Prime: $def \, factors(n:Int) = for(x \leftarrow List.range(1,n+1) \, if \, n \% x == 0) \, yield \, x$ $def \, prime(n:Int) = factors(n) == List(1,n)$
Sorted via Zip: $adjPairs \, xs = zip \, xs \, (tail \, xs)$ $sorted \, xs = and \, [x \le y \, | \, (x,y) \leftarrow adjPairs \, xs]$
Java Factorial (Iterative): $public \, static \, int \, fac(int \, n) { int \, r = 1; for(int \, i=1; i \le n; i++) r \times = i; return \, r; }$

Predicted 2026 Exam Topics

Q1: High probability of Ad Hoc Polymorphism (last seen 2024) and List Evaluation.
Q2: Type errors regarding $[a] \rightarrow [a]$ and the definition of $sorted/adjPairs$ .
Q3: High certainty of Multi-paradigm advantages and Scala closure execution (var/val).
Q4: Recursive type synonym errors and Lazy Evaluation walkthroughs including bottom ( $\perp$ ).