Cambridge 9618 · International A Level Computer Science · ~20 min read
Notes
Video
Slides
Quiz
Worksheet
What is Functional Programming?
Functional programming (FP) is a programming paradigm that treats computation as the evaluation of mathematical functions. Programs are built by composing functions — no variables are changed, no loops are used, and functions have no side effects.
Cambridge 9618 uses a Haskell-like syntax for functional programming examples. The key idea: instead of telling the computer HOW to do something step-by-step (imperative), you describe WHAT the result should be (declarative).
Imperative (Python)
Functional (Haskell)
total = 0 for x in [1,2,3,4,5]: total += x print(total)
sum [1,2,3,4,5] -- result: 15 (no loop, no mutation)
Core Concepts
🧮
Pure Functions
A function is PURE if: (1) it always returns the same output for the same input, and (2) it has NO side effects — it doesn't modify any external state, print to screen, read files, or change any variables. Like a mathematical function: f(x) = x + 1 always gives x+1, nothing else.
🔒
Immutability
Data cannot be changed once created. Instead of modifying a list in place, a NEW list is created with the changes. Variables are like mathematical constants — once bound to a value, they don't change. This eliminates a whole class of bugs caused by unexpected state changes.
🎯
First-Class Functions
Functions are treated like any other value — they can be passed as ARGUMENTS to other functions, returned as RESULTS from functions, and stored in data structures (lists, variables). Functions are "first-class citizens" of the language.
🏗️
Higher-Order Functions
Functions that TAKE another function as an argument, or RETURN a function as their result. Examples: map (apply a function to every element), filter (keep elements matching a predicate), fold/reduce (combine elements into one value). These replace loops in functional programming.
Lambda Functions (Anonymous Functions)
A lambda is a function without a name — defined inline. In Haskell: \x -> x + 1 is an anonymous function that adds 1 to x. The backslash represents λ (lambda).
Lambda expressions — Haskell syntax
-- Named function addOne::Int->Int addOne x = x +1
-- Equivalent lambda (anonymous) \x -> x +1
-- Lambda with multiple parameters \x y -> x + y
-- Used inline with map: map (\x -> x *2) [1,2,3] -- result: [2, 4, 6]
Higher-Order Functions: map, filter, fold
map :: (a → b) → [a] → [b]
Applies a function to EVERY element of a list, returning a new list of the same length.
Functions can be chained together — the output of one becomes the input of the next. In Haskell, the dot operator . composes functions. (f . g) x = f (g x) — g is applied first, then f to its result.
-- Equivalent pipeline (left to right, easier to read): doubleThenAdd x = x |>double|>addTen
Recursion in Functional Programming
Functional programming has no loops — recursion is used instead. A recursive function calls itself with a smaller version of the problem until it hits a base case.
Recursive functions — Haskell
-- Factorial factorial::Int->Int factorial0=1-- base case factorial n = n *factorial (n -1) -- recursive case
-- Sum of a list using pattern matching sumList:: [Int] ->Int sumList [] =0-- base case: empty list sumList (x:xs) = x +sumList xs -- head + sum of tail
Lists: Head and Tail
In Haskell, lists are defined recursively. The head is the first element, the tail is the rest of the list. The cons operator : adds an element to the front of a list.
-- Pattern matching on list: myFunc [] = ... -- match empty list myFunc (x:xs) = ... -- match head x, tail xs
Type System
Haskell uses a strong static type system. Every function has a type signature showing its input and output types. The arrow -> separates parameter types from the return type.
-- Read as: "takes an Int, returns an Int"
addOne :: Int -> Int
-- Takes two Ints, returns an Int
add :: Int -> Int -> Int
-- Takes a function (Int→Int) and a list of Ints, returns a list of Ints
myMap :: (Int -> Int) -> [Int] -> [Int]
-- Type variable 'a' = polymorphic (works for any type)
identity :: a -> a
Summary table — FP concepts
Concept
Definition
Example
Pure function
Same input → same output, no side effects
f(x) = x + 1
Immutability
Data cannot be modified — new values created
Lists are never changed in place
Lambda
Anonymous function defined inline
\x -> x * 2
Higher-order function
Takes/returns functions as values
map, filter, foldl
map
Apply function to every list element
map (*2) [1,2,3] = [2,4,6]
filter
Keep elements satisfying predicate
filter even [1,2,3,4] = [2,4]
fold
Combine list into single value
foldl (+) 0 [1,2,3] = 6
Composition (.)
Chain functions: output of one is input of next
(f . g) x = f(g(x))
Recursion
Function calls itself — replaces loops
factorial n = n * factorial(n-1)
Cambridge 9618 exam tip: For "trace" questions, show each step of how a function evaluates — especially recursion (show each recursive call and its return value). For map/filter/fold: state the function, the list, and the result at each step. For type signatures: read :: as "has type" and -> as "returns". For composition: remember (f . g) x = f(g(x)) — g is applied FIRST. When defining recursive functions, always identify the base case (usually empty list [] or n=0) and the recursive case.
⚠️ Common Mistakes
Confusing map and filter — MAP applies a function to every element (same length list). FILTER keeps elements that satisfy a predicate (shorter or equal length list). Map changes values; filter removes elements.
foldl vs foldr — foldl processes left-to-right (accumulator on left). foldr processes right-to-left. For addition/multiplication both give the same result. For non-commutative operations (subtraction, cons) they give different results. Cambridge usually asks about foldl.
Confusing function composition order — (f . g) x = f(g(x)). g is applied FIRST, then f. If the dot is read left-to-right as "f then g", this is wrong. Think of it mathematically: f composed with g means apply g first, then f to the result.
Pure functions cannot have side effects — a function that prints to screen, reads from a file, modifies a global variable, or generates random numbers is NOT pure. Cambridge may ask you to identify whether a function is pure — check for side effects AND check it returns the same output for the same input.
Recursion needs a base case — every recursive function must have a base case that stops the recursion. Missing the base case causes infinite recursion (stack overflow). For lists, the base case is usually the empty list []. For integers, it's usually 0 or 1.
✅ Notes completed!
▶
Video coming soon
Click slide or press arrow keys to navigate
Worksheet — 4.6.1 Functional Programming
8 questions · Cambridge 9618 standard
Q1State what is meant by a "pure function" in functional programming. Give one example of a pure function and one example of an impure function, explaining your reasoning.[4]
✅ Mark scheme
Pure function [2]: always returns the same output for the same input — consistent results regardless of when or how many times it is called [1]; has NO side effects — does not modify any external state, does not read from or write to files, does not print to screen, does not modify global variables [1]; Example pure function [1]: f(x) = x * x (square function), or addOne x = x + 1 — for the same input, always the same output, no external interaction; Example impure function [1]: a function that prints to screen (side effect), reads user input (different result each time), generates a random number (different result each time), or modifies a global counter. The reason must be stated — what side effect / inconsistency makes it impure.
Q2Evaluate the following Haskell expressions. Show your working. (a) map (*3) [2, 4, 6] (b) filter (>5) [3, 5, 7, 9, 2] (c) foldl (+) 0 [1, 2, 3, 4][6]
✅ Mark scheme
(a) map (*3) [2,4,6] [2 marks]: applies (*3) to each element: 2*3=6, 4*3=12, 6*3=18; result: [6, 12, 18] [1 for working, 1 for correct result]; (b) filter (>5) [3,5,7,9,2] [2 marks]: keeps only elements where element > 5: 3>5 False, 5>5 False, 7>5 True, 9>5 True, 2>5 False; result: [7, 9] [1 for correct predicate application, 1 for correct result]; (c) foldl (+) 0 [1,2,3,4] [2 marks]: starts with accumulator 0; step by step: (0+1)=1, (1+2)=3, (3+3)=6, (6+4)=10; result: 10 [1 for showing accumulator steps, 1 for correct final result].
Q3Write a recursive Haskell function called myLength that returns the length (number of elements) of a list. Show the base case and recursive case. Trace its evaluation on the input [1, 2, 3].[4]
✅ Mark scheme
Function definition [2]: myLength :: [a] -> Int myLength [] = 0 -- base case: empty list has length 0 [1] myLength (_:xs) = 1 + myLength xs -- recursive: 1 + length of tail [1] (Accept x:xs instead of _:xs — the underscore shows head element is ignored) Trace on [1,2,3] [2]: myLength [1,2,3] = 1 + myLength [2,3] [1] = 1 + (1 + myLength [3]) = 1 + (1 + (1 + myLength [])) = 1 + (1 + (1 + 0)) = 3 [1 for correct full trace showing base case reached]
Q4Explain what a higher-order function is. Identify which of the following are higher-order functions and explain why: (a) map (b) factorial (c) filter (d) head[4]
✅ Mark scheme
Higher-order function [1]: a function that takes another function as an argument, and/or returns a function as its result; functions are first-class values, so they can be passed around like any other data; (a) map: HIGHER-ORDER — takes a function as its first argument (e.g. map (+1) [1,2,3]) and applies it to every list element [1]; (b) factorial: NOT higher-order — takes an integer, returns an integer; no functions are passed or returned [accept]; (c) filter: HIGHER-ORDER — takes a predicate function (a→Bool) as its first argument and uses it to test each element [1]; (d) head: NOT higher-order — takes a list, returns the first element; no functions involved [accept]. Award 1 for definition + 1 each for correctly identifying map as HO + filter as HO (1 mark each, max 3 for identifications + 1 for definition = 4).
Q5Two functions are defined: double x = x * 2 and addFive x = x + 5. Write the composition (addFive . double) and evaluate it for x = 3. Then write the composition (double . addFive) and evaluate it for x = 3. Explain why the results differ.[4]
✅ Mark scheme
(addFive . double) x = addFive (double x) [1]: double is applied FIRST: double 3 = 6; then addFive: 6 + 5 = 11; result = 11 [1]; (double . addFive) x = double (addFive x) [1]: addFive is applied FIRST: addFive 3 = 8; then double: 8 * 2 = 16; result = 16 [1]; Results differ because function composition is not commutative — the ORDER in which functions are applied matters: (f . g) applies g first, then f; when the operations are different (multiplication vs addition), changing the order changes the result; 2*(x+5) ≠ (2*x)+5 for x=3 (16 ≠ 11). Award 4 marks: 1 for correct first composition + evaluation, 1 for correct second composition + evaluation, 1 for explanation of composition order, 1 for correct math showing why results differ.
Q6Compare functional programming and imperative programming in terms of: (a) use of variables, (b) loops vs recursion, (c) side effects.[6]
✅ Mark scheme
(a) Variables [2]: Imperative: variables are mutable — they can be assigned and reassigned; a variable's value can change at any point in the program (e.g. x = 5; x = x + 1 is valid) [1]; Functional: variables are IMMUTABLE — once bound to a value, they cannot change; a new value requires creating a new binding, not modifying the existing one; data is never changed in place [1]; (b) Loops vs Recursion [2]: Imperative: uses loops (for, while, do-while) to repeat operations — the loop variable changes with each iteration [1]; Functional: has NO mutable loop variables so cannot use traditional loops; uses RECURSION instead — a function calls itself with a smaller input until a base case is reached; each recursive call creates a new binding rather than modifying existing state [1]; (c) Side effects [2]: Imperative: functions (procedures) regularly cause side effects — printing output, modifying global variables, reading files, updating databases; this is normal and expected in imperative code [1]; Functional: pure functions must have NO side effects; a function only computes a return value; no external state is modified; the same input always produces the same output; side effects (I/O etc.) are handled separately and explicitly [1]. 2 marks per point. Max 6.
Q7A functional program contains the following higher-order functions applied to a list [1, 2, 3, 4, 5, 6]: (a) filter (x > 3) → result A, (b) map (x * 2) applied to result A → result B, (c) fold (+) 0 applied to result B → result C. State the values of A, B, and C, showing your working at each stage.[4]
✅ Mark scheme
A = filter (x > 3) [1, 2, 3, 4, 5, 6] = [4, 5, 6] [1]; B = map (x * 2) [4, 5, 6] = [8, 10, 12] [1]; C = fold (+) 0 [8, 10, 12] = 0+8+10+12 = 30 [1]; Award 1 mark for correct final answer of C = 30 even if intermediate steps not fully shown [1 max if no working].
Q8Explain what referential transparency means in functional programming. State two benefits it provides for testing and reasoning about code, and contrast this with a function that reads from a global variable.[5]
✅ Mark scheme
Referential transparency: an expression can be replaced by its value without changing the program's behaviour — calling a function with the same arguments always returns the same result [1]; Benefit 1: easier testing — a referentially transparent function can be tested in isolation with no need to set up global state or mock side effects [1]; Benefit 2: easier reasoning / optimisation — the compiler or programmer can substitute function calls with cached results (memoisation) safely, knowing the value never changes [1]; A function reading a global variable is NOT referentially transparent because its return value depends on the current state of the variable, which may have been changed by another part of the program, making the result unpredictable [1]; this means behaviour cannot be predicted from arguments alone [1].
Q3For composition (f . g) x, which function is applied first?
Q4What does foldl (*) 1 [2, 3, 4] evaluate to?
Q5In Haskell, \x -> x + 5 is:
Section B — Short Answer [5 marks]
Q6Explain what is meant by "immutability" in functional programming. Why is it a desirable property?
Mark schemeImmutability: once a variable or data structure is bound to a value, it cannot be changed or modified [1]; instead of modifying data in place (like changing array elements), functional programming creates NEW data with the required changes; original data remains unchanged [1]; why desirable: eliminates bugs caused by unexpected state changes — one part of the program cannot accidentally modify data that another part is using [1]; makes code easier to reason about and test — data is predictable and consistent throughout execution; also enables safe concurrent programming since there are no shared mutable states to cause race conditions [1]. Max 3 marks — award any 3.
Q7Trace the evaluation of this recursive function for the input [4, 2, 8]: myMax [x] = x; myMax (x:xs) = if x > myMax xs then x else myMax xs
Mark schememyMax [4,2,8]: = if 4 > myMax [2,8] then 4 else myMax [2,8] [1] myMax [2,8]: = if 2 > myMax [8] then 2 else myMax [8] myMax [8] = 8 (base case: single element) [1] = if 2 > 8 then 2 else 8 → False → 8 Back to outer: if 4 > 8 then 4 else 8 → False → 8 [1] myMax [4,2,8] = 8 [1 for correct final answer] Award marks for: identifying base case evaluation (1), correct recursive unfolding (1), correct conditional evaluation (1), correct final result 8 (1). Max 4.
Q8What is the result of: map (\x -> x * x) (filter even [1..6])? Show your working step by step.
Mark schemeWorking step by step [3]: Step 1: [1..6] = [1, 2, 3, 4, 5, 6] [1] Step 2: filter even [1,2,3,4,5,6]: keep only even numbers: 2, 4, 6 → [2, 4, 6] [1] Step 3: map (\x -> x*x) [2,4,6]: apply square function to each: 2*2=4, 4*4=16, 6*6=36 → [4, 16, 36] [1] Final result: [4, 16, 36]
Q9State the Haskell type signature for a function called myFilter that takes a predicate function (Int → Bool) and a list of Ints, and returns a list of Ints.
Mark schememyFilter :: (Int -> Bool) -> [Int] -> [Int] [2] Award 2 marks for correct full type signature. Partial credit (1 mark): for having the right structure but minor error (e.g. omitting parentheses around predicate). Key elements: function in parentheses taking Int returning Bool [1]; [Int] input list and [Int] output list [1]; correct use of :: and -> [implicitly required for structure]. Accept also polymorphic version: myFilter :: (a -> Bool) -> [a] -> [a] [2 marks — correct and more general].
Q10State TWO reasons why functional programming languages do not use loops (for/while) and explain what is used instead.
Mark schemeReason 1: loops require MUTABLE variables (a loop counter that changes with each iteration) [1]; functional programming requires IMMUTABILITY — data cannot be modified once created; a changing loop counter contradicts immutability [1]; Reason 2: loops are inherently about HOW to iterate (step by step, change state) — an imperative style; functional programming is DECLARATIVE — describes WHAT the result should be, not the step-by-step process [1]; Instead: RECURSION is used — a function calls itself with a smaller version of the problem until reaching a base case; each recursive call creates new bindings rather than modifying existing state; higher-order functions (map, filter, fold) also replace common loop patterns [1]. Award 1 per reason + 1 per explanation, max 4 marks total.