Cambridge 9618 · International A Level Computer Science · ~18 min read
Notes
Video
Slides
Quiz
Worksheet
Functional Programming — Core Principles
Functional programming (FP) treats computation as the evaluation of mathematical functions. It avoids changing state and mutable data. Cambridge 9618 requires you to understand the four core features:
🔬
Pure Functions
A function that always returns the same output for the same input, and has no side effects — it doesn't modify any external state, read files, print to screen, or change variables outside itself.
🧊
Immutability
Once a value is created, it cannot be changed. Instead of modifying data, you create new values. This prevents unexpected state changes and makes programs easier to reason about.
🎯
First-Class Functions
Functions are treated as values — they can be stored in variables, passed as arguments to other functions, and returned as results. This makes functions extremely flexible building blocks.
⚙️
Higher-Order Functions
Functions that take other functions as parameters, or return a function as their result. Examples: map, filter, fold. They allow powerful abstractions without loops.
Pure Functions
A function is pure if it has two properties:
Same input → same output (deterministic): calling Double(4) always returns 8, no matter when it's called.
No side effects: it doesn't modify global variables, write to files, print output, or change any external state.
// PURE function — only uses its parameters, returns a value FUNCTIONDouble(n : INTEGER) RETURNS INTEGER RETURN n * 2 ENDFUNCTION
// IMPURE function — reads/modifies global variable (side effect)
total ← 0// global variable PROCEDURE AddToTotal(n : INTEGER)
total ← total + n // side effect — modifies external state ENDPROCEDURE
Higher-Order Functions — Map, Filter and Fold
These three functions process lists (sequences) without explicit loops. In FP, they replace the FOR/WHILE loops of procedural programming.
Map — transform each element
Applies a function to every element in a list and returns a new list of the same length.
Input list
1
2
3
4
5
map(Double)
× 2 for each
Output list
2
4
6
8
10
// Equivalent procedural approach (impure — uses index variable and mutation) FUNCTIONMapDouble(nums : ARRAY[1:5] OF INTEGER) RETURNS ARRAY[1:5] OF INTEGER DECLARE result : ARRAY[1:5] OF INTEGER DECLARE i : INTEGER FOR i ← 1TO5
result[i] ← nums[i] * 2 NEXT i RETURN result ENDFUNCTION
Filter — keep matching elements
Applies a predicate function to each element; only elements where the predicate returns TRUE are included in the output list.
Input list
1
2
3
4
5
filter(IsEven)
keep if x MOD 2 = 0
Output list
2
4
Fold (Reduce) — collapse a list to a single value
Combines all elements in a list using an accumulator function, starting with an initial value. Also called 'reduce' in some languages.
In functional programming, you can chain functions together so the output of one becomes the input of the next. This builds complex operations from simple, pure building blocks.
// Compose two functions: first double, then add 1 FUNCTIONDouble(n : INTEGER) RETURNS INTEGER RETURN n * 2 ENDFUNCTION
FUNCTIONAddOne(n : INTEGER) RETURNS INTEGER RETURN n + 1 ENDFUNCTION
// Composed: AddOne(Double(x))
OUTPUT AddOne(Double(4)) // Double(4)=8, then AddOne(8)=9
Tail Recursion
In functional programming, recursion replaces loops (since there are no mutable loop counters). Tail recursion is a special form where the recursive call is the last operation in the function — there is nothing to do after the recursive call returns.
// Standard recursion (NOT tail-recursive) — winding + unwinding FUNCTIONFactorial(n : INTEGER) RETURNS INTEGER IF n = 0THEN RETURN1 ELSE RETURN n * Factorial(n - 1) // must multiply AFTER recursive call ENDIF ENDFUNCTION
// Tail-recursive version (accumulator pattern) FUNCTIONFactTail(n : INTEGER, acc : INTEGER) RETURNS INTEGER IF n = 0THEN RETURN acc ELSE RETURN FactTail(n - 1, n * acc) // recursive call is the LAST thing ENDIF ENDFUNCTION // Called as: FactTail(4, 1) → FactTail(3,4) → FactTail(2,12) → FactTail(1,24) → 24
The advantage of tail recursion is that the compiler/interpreter can optimise it into an iterative loop internally (no new stack frames needed), avoiding stack overflow for large inputs.
Declarative Programming
In declarative programming, you describe what you want the result to be, not how to achieve it step-by-step. The language/runtime works out the execution strategy.
Procedural (HOW)
Declarative (WHAT)
Write step-by-step instructions; tell the computer every step
Describe the desired output; the system works out how to get there
Use loops, variables, mutation
Express relationships, constraints, or patterns
Example: Pascal, Python, Java
Example: SQL, Prolog, HTML, CSS
SQL — Structured Query Language
SQL is the most common declarative language. You state the data you want and the conditions; the database engine decides how to retrieve it efficiently.
SQL — Declarative query
SELECT studentName, grade FROM Students WHERE grade >= 70 ORDER BY studentName ASC;
-- We declare WHAT we want — rows from Students where grade ≥ 70, -- sorted by name. The SQL engine decides HOW to retrieve them.
Prolog — Logic Programming
Prolog is a declarative logic programming language. You define facts (true statements about the world) and rules (logical relationships), then query the system.
Prolog — Facts, Rules & Queries
/* Facts */ parent(tom, bob). % tom is a parent of bob parent(bob, ann). % bob is a parent of ann
/* Rule — X is a grandparent of Z if X is parent of Y and Y is parent of Z */ grandparent(X, Z) :- parent(X, Y), parent(Y, Z).
/* Query */
?- grandparent(tom, Who). % Who = ann
In Prolog, uppercase words are variables (X, Z, Who) and lowercase are atoms/facts (tom, ann). The Prolog engine uses backtracking to find all solutions automatically.
Comparison — All Four Paradigms
Feature
Procedural
OOP
Functional
Declarative
Focus
How to do it
Objects & relationships
Function evaluation
What to achieve
State
Mutable variables
Object attributes
Immutable values
No explicit state
Loops
FOR/WHILE
FOR/WHILE in methods
Recursion / HOFs
Implicit (engine)
Side effects
Common
Methods can have them
Avoided (pure funcs)
None
Examples
Python, Pascal, C
Java, C++, Python
Haskell, Erlang
SQL, Prolog, HTML
Cambridge 9618 exam tip: The key distinction examiners test is pure functions (no side effects, same output for same input), first-class functions (can be passed as arguments), and higher-order functions (take/return functions). For declarative, be able to contrast it with procedural: declarative states WHAT, procedural states HOW. SQL and Prolog are the two most commonly cited examples of declarative languages.
⚠️ Common Mistakes
Thinking recursion = functional programming — procedural programs also use recursion; it's just how FP implements iteration
Confusing immutability with constants — in FP you create new values rather than updating existing ones (the original data structure is unchanged)
Saying declarative programs "don't have any code" — they do have code, but the code describes goals, not step-by-step procedures
Confusing filter with map — map transforms every element (same list length); filter removes elements (shorter or equal length list)
Forgetting that fold/reduce needs an initial value (the starting accumulator)
Q1Define a 'pure function'. Give one example of a pure function and one example of an impure function, explaining why each is or is not pure.[4]
✅ Mark scheme
A pure function always returns the same output for the same input and has no side effects [1]; pure example: a function that returns n*2 given n — always the same output, doesn't change any external variable [1]; impure example: a function that reads from a file, generates a random number, or modifies a global variable — same input could give different outputs or it changes external state [1]; explanation of why the impure one is not pure [1].
Q2Describe what the higher-order function 'map' does. Show the result of applying map(Double) to the list [3, 5, 7, 9] where Double multiplies a number by 2.[3]
✅ Mark scheme
Map applies a given function to every element in a list and returns a new list of the same size [1]; the function Double is applied to each element: 3→6, 5→10, 7→14, 9→18 [1]; result: [6, 10, 14, 18] [1].
Q3Explain the difference between 'map' and 'filter' as higher-order functions, with an example of each.[4]
✅ Mark scheme
Map transforms every element and returns a new list of the same length [1]; example: map(Double, [1,2,3]) → [2,4,6] — same number of elements [1]; filter tests each element with a predicate function and only keeps elements where the predicate is TRUE [1]; example: filter(IsEven, [1,2,3,4,5]) → [2,4] — fewer elements in result [1].
Q4Describe the fold (reduce) higher-order function and trace fold(Add, 0, [10, 20, 30]) step-by-step.[4]
✅ Mark scheme
Fold combines all elements of a list using an accumulator function, starting with an initial value [1]; trace: acc=0, element=10 → Add(0,10)=10 [1]; acc=10, element=20 → Add(10,20)=30; acc=30, element=30 → Add(30,30)=60 [1]; final result: 60 [1].
Q5State two characteristics that distinguish functional programming from procedural programming.[2]
✅ Mark scheme
Any two: (1) FP avoids side effects / uses pure functions; procedural code commonly modifies global state [1]; (2) FP uses immutable data — values cannot be changed after creation; procedural uses mutable variables [1]; (3) FP uses recursion instead of explicit loops; procedural uses FOR/WHILE statements [1]; (4) FP treats functions as first-class values that can be passed as arguments; procedural does not [1].
Q6Explain what is meant by 'declarative programming' and give one example. How does it differ from procedural programming?[3]
✅ Mark scheme
Declarative programming describes WHAT result is wanted rather than HOW to achieve it step-by-step [1]; example: SQL query — SELECT name FROM Students WHERE grade > 70 — states what data is needed, not how the database should search [1]; procedural programming requires the programmer to specify every step in sequence (how to loop through records, compare values, etc.); declarative leaves the execution strategy to the language/engine [1].
Q7A programmer is writing a payroll application that processes employees' personal data and bank details. Identify three ethical issues that arise, and for each issue describe one action the programmer should take to address it responsibly.[6]
✅ Mark scheme
Issue 1: data privacy — encrypt stored bank details and use secure transmission (HTTPS/TLS) — 1+1 mark; Issue 2: data minimisation — only collect data necessary for payroll processing, not additional personal details — 1+1 mark; Issue 3: access control — restrict database access to authorised payroll staff only using role-based permissions — 1+1 mark. (Any three valid ethical issues with appropriate actions, 1 mark each pair.)
Q8Explain what is meant by intellectual property and copyright in the context of software. State two ways a programmer could ensure they comply with copyright law when using third-party libraries or code in their project.[4]
✅ Mark scheme
Intellectual property: legal rights protecting creations of the mind including software code — 1 mark; copyright: automatic right giving creator exclusive control over copying, distribution and modification — 1 mark; compliance method 1: check the open-source licence (e.g. MIT, GPL) and ensure use complies with its terms — 1 mark; compliance method 2: attribute the author/library in documentation as required by the licence — 1 mark.
Topic Quiz
Question 1 of 10
You scored
out of 10
Card 1 of 8
Click to reveal definition
🎉
All cards reviewed!
Term
Definition
🎯
Mini Test — 2.5.3 Functional & Declarative
10 questions · 10 marks · 10 minutes
⏱ 10:00
Section A — Multiple Choice [5 marks]
Q1Which of the following is a characteristic of a pure function?
Q2What does the 'map' function do in functional programming?
Q3What is the result of filter(IsPositive, [-3, -1, 0, 2, 5]) where IsPositive returns TRUE for values greater than 0?
Q4SQL is an example of which programming paradigm?
Q5A function is 'first-class' if:
Section B — Short Answer [5 marks]
Q6Explain what 'immutability' means in functional programming and why it is useful.
Mark schemeImmutability means that once a value is created, it cannot be changed [1]; instead of modifying an existing value, a new value is created [1]; this is useful because it prevents unexpected side effects from one part of a program changing data used by another part, making programs easier to understand and debug [1].
Q7What is a higher-order function? Give one example.
Mark schemeA higher-order function is a function that takes another function as a parameter, or returns a function as its result [1]; example: map takes a function (e.g. Double) and a list as inputs, applies Double to each element, and returns the new list — it is a higher-order function because it takes a function as an argument [1].
Q8What is tail recursion and why is it preferred over standard recursion in functional programming?
Mark schemeTail recursion is where the recursive call is the very last operation in the function — no computation is done after the recursive call returns [1]; it is preferred because compilers/interpreters can optimise it into a loop (tail-call optimisation), meaning no additional stack frames are needed for each call [1]; this prevents stack overflow errors for large inputs [1].
Q9Trace fold(Multiply, 1, [2, 3, 4]) step-by-step and state the final result.
Q10Give two differences between declarative programming and procedural programming.
Mark schemeAny two contrasting pairs: Declarative describes WHAT result is wanted; procedural specifies HOW to achieve it step by step [1]; declarative leaves execution strategy to the language engine; procedural gives explicit sequence of instructions [1]; declarative has no mutable state/loops; procedural uses variables and iteration [1].