CAIE 9618 · Paper 4 · Topic 4.6.1

Functional
Programming

Pure Functions · First-Class Functions · Higher-Order Functions · Map / Filter / Fold · Lambda · Immutability

CSZone Cambridge International AS & A Level Computer Science 9618

The Paradigm

What is Functional Programming?

Functional programming (FP) is a programming paradigm that treats computation as the evaluation of mathematical functions. It avoids changing state and mutable data.

KEY PRINCIPLES

Pure functions — same input always gives same output; no side effects

Immutability — variables once assigned cannot change; no mutation

First-class functions — functions are values that can be passed and returned

Higher-order functions — functions that take or return other functions

Recursion used instead of loops (no mutable loop counter)

FP vs IMPERATIVE

Imperative: "HOW to do it" — step-by-step instructions, mutable state (e.g. Java, Python loops)

Functional: "WHAT to compute" — describe the transformation, no side effects

FP code is often shorter, easier to reason about, and naturally parallelisable

Languages: Haskell (purely functional), F#, Erlang; FP features also in Python, JavaScript, OCaml

Core Concept

Pure Functions & Immutability

PURE FUNCTION — DEFINITION

A function is pure if it satisfies both conditions:

Deterministic — given the same input, it ALWAYS returns the same output (referential transparency)

No side effects — it does NOT modify any state outside itself (no writing to files, no changing global variables, no I/O)

SIDE EFFECTS — WHAT TO AVOID

Modifying a global variable or object

Writing to a file or database

Printing to the screen (console output)

Throwing exceptions that change control flow

PURE vs IMPURE EXAMPLES (Haskell-style pseudocode)

-- PURE: same input → same output
double :: Int → Int
double x = x * 2

-- double 5 always returns 10

-- IMPURE: depends on/changes
-- external state
getInput :: IO String -- reads stdin
printLine :: String → IO ()

Immutability: once a value is bound to a name, it CANNOT change. You create new values instead of mutating existing ones. Enables safe parallelism and easy reasoning.

Key Feature

First-Class & Higher-Order Functions

First-class functions — in FP languages, functions are treated as values: they can be stored in variables, passed as arguments to other functions, and returned as results from functions. This is a defining property of functional languages.

HIGHER-ORDER FUNCTION

A function that takes a function as a parameter OR returns a function as its result (or both).

map, filter, and fold (reduce) are the three fundamental higher-order functions in FP

They abstract common patterns of recursion and iteration over lists

LAMBDA EXPRESSIONS

A lambda (anonymous function) is a function defined inline without a name. Used to pass as arguments to higher-order functions without declaring a separate named function.

-- Named function
double x = x * 2

-- Equivalent lambda (anonymous)
\x → x * 2

-- λ (lambda) in Haskell is written \

Higher-Order Functions

Map · Filter · Fold

MAP

Applies a function to every element of a list and returns a new list of the same length.

-- map f [x1,x2,...] =
-- [f x1, f x2, ...]

map (*2) [1,2,3,4,5]
-- returns [2,4,6,8,10]

map (+1) [10,20,30]
-- returns [11,21,31]

FILTER

Returns a new list containing only elements for which the predicate function returns True.

-- filter p xs = all x
-- where p x = True

filter (>3) [1,2,3,4,5]
-- returns [4,5]

filter even [1..10]
-- returns [2,4,6,8,10]

FOLD (REDUCE)

Reduces a list to a single value by repeatedly applying a function with an accumulator.

-- foldl f acc [x1,x2,...]
-- accumulates left to right

foldl (+) 0 [1,2,3,4,5]
-- = 0+1+2+3+4+5 = 15

foldl (*) 1 [1,2,3,4,5]
-- = 1*1*2*3*4*5 = 120

Exam tip: Map transforms every element (output list = same length as input). Filter selects elements based on a condition (output list ≤ input length). Fold collapses a list to a single value using an accumulator.

Advanced Concepts

Composition & Partial Application

FUNCTION COMPOSITION

Combining two functions so the output of one becomes the input of the next. Written as f ∘ g (f after g), meaning apply g first, then f.

-- (f . g) x = f (g x)

double x = x * 2
addOne x = x + 1

doubleThenAdd = addOne . double
doubleThenAdd 5
-- addOne(double(5)) = addOne(10) = 11

PARTIAL APPLICATION (CURRYING)

Currying transforms a function with multiple arguments into a chain of functions each taking ONE argument. Partial application = applying a function to some (but not all) of its arguments to produce a new function.

-- add takes 2 args
add :: Int → Int → Int
add x y = x + y

-- Partial application: fix x=5
addFive = add 5 -- function!
addFive 3 -- returns 8
addFive 10 -- returns 15

In Haskell, ALL functions are automatically curried — every function takes exactly one argument and returns a value or another function.

Functional Syntax

List Comprehension

A list comprehension is a concise way to construct a new list by specifying: (1) an output expression, (2) a generator (source list), and optionally (3) one or more guards (filters). Inspired by mathematical set-builder notation.

SYNTAX & EXAMPLES

-- Mathematical: { x² | x ∈ {1..10}, x is even }
-- Haskell: [x^2 | x <- [1..10], even x]

-- Squares of even numbers from 1 to 10
[ x^2 | x <- [1..10], even x ]
-- returns [4,16,36,64,100]

-- All pairs (x,y) where x /= y
[ (x,y) | x <- [1..3], y <- [1..3], x /= y ]
-- [(1,2),(1,3),(2,1),(2,3),(3,1),(3,2)]

PARTS OF A LIST COMPREHENSION

Output expression: what each element looks like (left of |)

Generator: x <- [list] draws elements from a source list

Guard: boolean condition to filter elements (e.g., even x)

LIST COMPREHENSION vs MAP/FILTER

[x*2 | x <- xs, x>3]
is equivalent to:
map (*2) (filter (>3) xs)

Both are valid FP — comprehensions are syntactic sugar over HOFs.

Exam Practice

Cambridge-style questions

Question 1

The following Haskell function is defined: result = foldl (+) 0 (map (*3) (filter even [1..6]))

Show the value of result by tracing the evaluation step by step, naming each higher-order function used. [4]

1

filter even [1..6] — keeps only even numbers → [2, 4, 6]

1

map (*3) [2,4,6] — multiplies each by 3 → [6, 12, 18]

1

foldl (+) 0 [6,12,18] — sums with accumulator starting at 0: 0+6=6, 6+12=18, 18+18=36 → 36

1

result = 36

Exam Practice

Cambridge-style questions

Question 2

Explain what is meant by a "pure function" and state TWO benefits of using pure functions in a program. [3]

1

Pure function definition: A function that given the same input always returns the same output (deterministic) AND has no side effects (does not modify any state outside of the function or perform I/O).

1

Benefit 1: Easier to test and debug — a pure function can be tested in isolation by checking that specific inputs produce the expected output, without needing to set up or check external state.

1

Benefit 2: Safe for parallel execution — since pure functions don't share or mutate state, multiple calls can run concurrently without race conditions or synchronisation issues.

Common Mistakes

Don't lose easy marks

1

Confusing map and filter — MAP applies a function to every element and changes each element's value (same-length list). FILTER applies a predicate and KEEPS or REMOVES elements (shorter or equal length list). A common error is to describe filter as "applying a function to change elements" — it selects, not transforms.

2

Saying a function with I/O is "pure" — printing to screen (console output), reading from a file, or generating a random number are ALL side effects. These make a function impure. Pure functions can ONLY use their input parameters and return a value.

3

Confusing foldl and foldr — foldl (fold left) processes the list from the LEFT with the accumulator on the left: ((acc op x1) op x2)... foldr processes from the RIGHT: (x1 op (x2 op ... acc)). For non-commutative operations like subtraction or list construction, these give different results. Know which direction the fold goes.

Topic Summary — 4.6.1

What You Need to Know

CORE CONCEPTS

Pure function: deterministic, no side effects; same input → same output always

Immutability: values don't change; create new values instead of mutating

First-class functions: functions are values; can pass/return them

HIGHER-ORDER FUNCTIONS

map f list → transforms every element; same length

filter p list → keeps elements where p is True

foldl f acc list → reduces to single value (left to right)

SYNTAX TO KNOW

Lambda: \x → expr (anonymous function)

Composition: f . g means apply g then f

List comprehension: [expr | x <- list, guard]

Currying: partial application creates new function

CSZone

One More to Go!

Paper 4 · Final Topic

4.6.2

Declarative Programming

Prolog · Facts & Rules · Backtracking · Logic Programming

Head to CSZone.co.uk for the complete worksheet, quiz, and interactive tools

FunctionalProgramming

What is Functional Programming?

Pure Functions & Immutability

First-Class & Higher-Order Functions

Map · Filter · Fold

Composition & Partial Application

List Comprehension

Cambridge-style questions

Cambridge-style questions

Don't lose easy marks

What You Need to Know

One More to Go!

Functional
Programming