Notes · Computer ScienceUK · A-Levels

Fundamentals of functional programming

Functional programming is a paradigm that treats computation as the evaluation of mathematical functions, avoiding changing state and mutable data. This chapter develops functions as first-class objects, purity and the absence of side effects, function application, composition and partial application, the higher-order functions map, filter and fold, and the list-processing operations that are its natural data structure. Its importance is amplified by its role in the safe parallelism of big-data processing.

4 sections~14 min reading time3 competenciesLevel Standard 1 · Advanced 3

T·111111 / 14

Exam profile

AO1 · Know the functional paradigm: first-class functions, purity, domain and co-domain, and list operationsAO2 · Apply function application, composition, partial application and the higher-order functions map, filter and foldAO3 · Reason about why functional code suits concurrency and big data

Operators:defineexplainapplycomposeevaluatetrace

basic level

The functional paradigm is primarily A-Level content; AS students meet functions and simple list ideas.

higher level

The full A-Level expects first-class functions, function application, composition and partial application, the higher-order functions map/filter/fold, and list processing.

Depth

Text

Contents · 4 sections

Fundamentals of functional programming

Functions and the functional paradigm#

AdvancedAQA 7517 4.12.1DfE GCE Computer Science - functional programming

A function as a mapping from domain to co-domain

Fig. 1The function square maps each element of the domain {1, 2, 3} to exactly one element of the co-domain: 1 to 1, 2 to 4, 3 to 9. A function's type signature (square : Integer to Integer) names its domain and co-domain.

The functional paradigm treats a program as the evaluation of mathematical functions and avoids changing state and mutable data, in deliberate contrast to the imperative paradigm (met in the programming chapter), which is built from statements that change variables step by step. Where an imperative program says how to do something as a sequence of state changes, a functional program says what the result is as a composition of functions. Haskell is a purely functional language; many mainstream languages (Python, JavaScript) support functional features alongside imperative ones.

A function in the mathematical sense maps each value of its domain (the set of allowed inputs) to exactly one value of its co-domain (the set of possible outputs), written

f : A \to B

(shown opposite). This precise view underpins type signatures: a function's type states its domain and co-domain, so

\texttt{length} : \text{String} \to \text{Integer}

takes a string and returns an integer. Thinking of functions this way - total mappings from inputs to outputs - is the mental shift the paradigm requires.

The defining property is the pure function: one whose output depends only on its inputs and which has no side effects - it does not read or modify any external or global state, perform I/O, or change its arguments. A consequence is referential transparency: a call can be replaced by its result value anywhere without changing the program's meaning, because it always returns the same output for the same input. Purity makes functional code far easier to reason about, test and - crucially - run in parallel, since pure functions cannot interfere with one another.

In functional programming, functions are first-class objects: they can be stored in variables, passed as arguments to other functions, and returned as results, exactly like any other value. This is what makes the higher-order functions (below) and composition possible, and it is the feature that most distinguishes the paradigm's flavour. The absence of mutable state and side effects is also precisely why functional programming underpins the safe, lock-free parallelism of big-data processing, as the previous chapter showed.

f : A \to B

A function's type

$f$ maps each element of the domain $A$ to exactly one element of the co-domain $B$ ; the type signature states $A$ and $B$ .

Worked example

Identifying pure functions

Classify each as pure or impure and justify: (a) double(x) returns 2*x; (b) addToLog(x) appends x to a global log and returns x; (c) roll() returns a random number.

double(x)
Its result depends only on x and it changes nothing external - pure. double(5) is always 10, so it is referentially transparent.
addToLog(x)
It modifies external state (the global log) - a side effect - so it is impure, even though it also returns a value.
roll()
It returns a different value each call, so its output does not depend only on its inputs - impure (and not referentially transparent).

Result: Only double is pure. Purity requires the output to depend solely on the inputs with no side effects, which is why only (a) qualifies.

Typical mistakes

Thinking a function that prints, reads input or changes a global variable is pure - any side effect breaks purity.
Confusing the imperative 'how' (a sequence of state changes) with the functional 'what' (a composition of functions with no shared state).

Active revision

State whether each is a pure function and why: (a) one that returns the square of its argument; (b) one that adds its argument to a running global total; (c) one that returns the current time. Give the domain and co-domain of a function that maps a string to its length.

Active recall

Recall the key points — then reveal.

Sources: GCE AS and A level subject content for computer science (Department for Education) · AQA A-level Computer Science 7517 specification (AQA)

Function application, composition and partial application#

AdvancedAQA 7517 4.12.2DfE GCE Computer Science - function operations

Function composition as a pipeline

Fig. 2The composition g after f feeds the output of f into g. With f(x) = x + 1 and g(x) = 2x, the input 3 becomes 4 after f, then 8 after g, so (g after f)(3) = 8. Data flows through a chain of transformations.

Function application is simply calling a function on an argument to get a result - applying

f

x

gives

f(x)

. In functional languages application is the basic operation, and because functions are first-class the argument can itself be a function. Function composition combines two functions into a new one by feeding the output of one into the other: the composition

g \circ f

(read 'g after f') is the function that first applies

f

and then applies

g

to the result, so

(g \circ f)(x) = g(f(x))

(shown opposite). Composition lets small, well-understood functions be built up into larger ones without any intermediate variables.

The order matters:

g \circ f

applies

f

first, then

g

, and in general

g \circ f \neq f \circ g

. If

f(x) = x + 1

and

g(x) = 2x

, then

(g \circ f)(3) = g(4) = 8

, whereas

(f \circ g)(3) = f(6) = 7

. Composition is the functional programmer's equivalent of a pipeline - data flows through a chain of transformations - and it is possible precisely because functions are first-class values that can be combined and passed around.

Partial application fixes some of a function's arguments to produce a new function of the remaining arguments. If

\texttt{add}(x, y) = x + y

, then partially applying it with

x = 5

yields a new one-argument function

\texttt{addFive}(y) = 5 + y

, so

\texttt{addFive}(3) = 8

. Partial application is a convenient way to specialise a general function - deriving 'add five' from 'add' - and to build the small, single-purpose functions that compose cleanly.

Application, composition and partial application together give functional programming its characteristic style: define a toolbox of small pure functions, specialise them by partial application, and wire them together by composition into a solution, with no mutable state anywhere in the chain. This compositional style is easy to reason about and to test piece by piece, and it is the natural way to describe the map/filter/reduce pipelines of the next section.

(g \circ f)(x) = g(f(x))

Function composition

Apply $f$ first, then $g$ ; the order matters, so in general $g \circ f \neq f \circ g$ .

Worked example

Composition and partial application

With f(x) = x + 1 and g(x) = 2x, evaluate (g o f)(3) and (f o g)(3). Then, from add(x, y) = x + y, partially apply to make addTen and evaluate addTen(7).

(g o f)(3)
Apply f first: $f(3) = 3 + 1 = 4$ . Then g: $g(4) = 2 \times 4 = 8$ .
(f o g)(3)
Apply g first: $g(3) = 6$ . Then f: $f(6) = 7$ . So the two compositions differ (8 vs 7) - order matters.
Partial application
Fix x = 10 in add to get addTen(y) = 10 + y. Then addTen(7) = 10 + 7 = 17.

Result: (g o f)(3) = 8, (f o g)(3) = 7 (different), and addTen(7) = 17. Composition respects order; partial application specialises a general function.

Typical mistakes

Applying a composition in the wrong order - $g \circ f$ means f first then g, not the reverse.
Confusing partial application (fixing some arguments to get a new function) with simply calling the function on all its arguments.

Active revision

Given $f(x) = x - 2$ and $g(x) = x^2$ , evaluate $(g \circ f)(5)$ and $(f \circ g)(5)$ and confirm they differ. Then, from a function $\texttt{multiply}(a, b) = a \times b$ , use partial application to define $\texttt{triple}$ and evaluate $\texttt{triple}(4)$ .

Active recall

Recall the key points — then reveal.

Sources: AQA A-level Computer Science 7517 specification (AQA)

Higher-order functions: map, filter and fold#

AdvancedAQA 7517 4.12.3DfE GCE Computer Science - higher-order functions

A map-filter-fold pipeline

Fig. 3The list [1,2,3,4] is filtered to the even elements [2,4], each is squared by map to [4,16], and fold with addition combines them to 20. Each stage produces a new immutable list (or value), and each applies a pure function element by element.

A higher-order function is one that takes another function as an argument or returns a function as its result - possible only because functions are first-class. Three higher-order functions over lists are the workhorses of functional programming and are examined by name (shown opposite as a pipeline). Each takes a function plus a list and produces a result, and each expresses a whole loop's worth of work in a single, declarative call with no mutable counter or accumulator visible.

map applies a given function to every element of a list, producing a new list of the same length of the results. Mapping the function 'double' over

[1, 2, 3]

gives

[2, 4, 6]

; mapping 'length' over a list of words gives a list of their lengths. map expresses 'transform each element' and, because each element is handled independently, it is trivially parallelisable - the direct link to the MapReduce map phase of the big-data chapter.

filter takes a predicate (a function returning true or false) and returns a new list of just the elements for which the predicate is true. Filtering

[1, 2, 3, 4, 5]

by 'is even' gives

[2, 4]

. filter expresses 'keep the elements that satisfy a condition' and, like map, produces a new list rather than modifying the original - consistent with immutability. fold (also called reduce) combines all the elements of a list into a single value using a two-argument function and a starting value: folding

[1, 2, 3, 4]

with addition and start 0 gives

10

; with multiplication and start 1 gives

24

Together, map, filter and fold replace the explicit loops of imperative programming with declarative, composable operations, and they chain naturally into pipelines: filter a list, map a transformation over what remains, then fold to a summary. Because each operates on immutable data with a pure function, the whole pipeline is easy to reason about and safe to parallelise - which is exactly why this style scales to the distributed processing of big data.

Worked example

Applying map, filter and fold

For the list [1, 2, 3, 4, 5], give the result of: (a) map (add 10); (b) filter (greater than 2); (c) fold with multiplication starting at 1.

map (add 10)
Apply 'add 10' to each element: $[1+10, 2+10, 3+10, 4+10, 5+10] = [11, 12, 13, 14, 15]$ - same length, each transformed.
filter (> 2)
Keep only elements greater than 2: $[3, 4, 5]$ - 1 and 2 are removed, so the list is shorter.
fold (x, start 1)
Combine all elements by multiplication from 1: $1 \times 1 \times 2 \times 3 \times 4 \times 5 = 120$ .

Result: (a) [11, 12, 13, 14, 15]; (b) [3, 4, 5]; (c) 120. map transforms, filter selects, fold reduces to one value - three loops expressed declaratively.

Typical mistakes

Confusing map (transforms every element, same-length list) with filter (keeps only elements passing a predicate, possibly shorter list).
Forgetting fold's starting (accumulator) value, or using the wrong identity (0 for sums, 1 for products).

Active revision

Starting from the list [1, 2, 3, 4, 5, 6], apply filter with 'is even', then map with 'square', then fold with addition (start 0). Show each intermediate list and the final value.

Active recall

Recall the key points — then reveal.

Sources: AQA A-level Computer Science 7517 specification (AQA)

List processing#

StandardAQA 7517 4.12.4DfE GCE Computer Science - list processing

A list as head and tail

Fig. 4The list [3, 5, 7] splits into its head (the first element, 3) and its tail (a new list of the rest, [5, 7]). This recursive head/tail structure - a list is a head followed by a tail that is itself a list - is the basis of recursive list processing.

The list is the fundamental data structure of functional programming, and it is processed through a small set of primitive operations rather than by index. The two most important are head, which returns the first element of a list, and tail, which returns a new list of everything except the first element (shown opposite). For the list

[3, 5, 7]

, the head is

3

and the tail is

[5, 7]

. This head/tail split is what makes lists naturally recursive - a list is either empty or a head followed by a tail that is itself a list.

Lists are built and extended by construction operations. Prepend (often called cons) adds an element to the front of a list, producing a new list - prepending

1

[2, 3]

gives

[1, 2, 3]

; append joins an element or list to the end. Consistent with immutability, these operations return a new list and leave the original unchanged, which is why functional data structures can be shared safely across parallel computations without copying or locking.

Two more operations complete the toolkit: isEmpty (or a test for the empty list) checks whether a list has any elements, and length returns how many it has. isEmpty is the essential base case for recursive list processing: a recursive function walks a list by handling the head and recursing on the tail, stopping when the list is empty. This head-tail-recursion pattern is the functional equivalent of a loop and expresses map, filter and fold themselves.

Because every operation returns a new list rather than mutating an existing one, list processing in the functional style is free of the aliasing and side-effect bugs that plague mutable structures, and it composes cleanly with the higher-order functions. Being able to state the result of head, tail, prepend, append, isEmpty and length on a given list, and to see how they combine recursively, is the examinable core of this section and ties the whole paradigm together.

Worked example

List operations and recursive summing

For the list [8, 6, 4, 2], give the head, tail, the result of prepending 9, and the length. Then outline a recursive sum using head, tail and isEmpty.

Head, tail, prepend, length
head = 8; tail = [6, 4, 2]; prepending 9 gives [9, 8, 6, 4, 2]; length = 4.
Base case
A recursive sum needs a base case: if the list isEmpty, its sum is 0.
Recursive case
Otherwise the sum is head + sum(tail): here 8 + sum([6, 4, 2]) unwinds to $8 + (6 + (4 + (2 + 0)))$ .

Result: head 8, tail [6,4,2], prepend gives [9,8,6,4,2], length 4; the recursive sum unwinds to $8 + 6 + 4 + 2 = 20$ . Head/tail with an empty-list base case is the functional loop.

Typical mistakes

Confusing head (the first element, a single value) with tail (the rest of the list, itself a list).
Assuming a list operation changes the original list - functional operations return a new list and leave the original unchanged.

Active revision

For the list [8, 6, 4, 2], give the head, the tail, the result of prepending 10, and the length. Then describe how you would sum a list recursively using head, tail and the empty-list test.

Active recall

Recall the key points — then reveal.

Sources: AQA A-level Computer Science 7517 specification (AQA)

References & sources

Sources

Department for Education

GCE AS and A level subject content for computer science

AQA

AQA A-level Computer Science 7517 specification

Fundamentals of functional programming

4 sections~14 min reading time3 competenciesLevel Standard 1 · Advanced 3

Fundamentals of functional programming

Key points

Identifying pure functions

Key points

Composition and partial application

Key points

Applying map, filter and fold

Key points

List operations and recursive summing

Sources

Fundamentals of functional programming

Key points

Identifying pure functions

Key points

Composition and partial application

Key points

Applying map, filter and fold

Key points

List operations and recursive summing

Sources