Revision notes for AQA A Level Computer Science Writing functional programs. Open the guide for explanations and worked examples. Written against the AQA A Level Computer Science specification, so the content matches what's examinable rather than general Computer Science background.

Writing functional programs

What you'll learn

  • How to recognise and write simple programs in a functional style.
  • What a higher-order function is and why it is useful.
  • How to use map, filter, and reduce/fold on lists.
  • How to trace a small functional pipeline step by step.

4.12.2.1 Functional language programs

Functional programming is a way of writing programs by building and applying functions. Instead of focusing on changing variables step by step, you describe transformations from inputs to outputs.

AQA expects you to have experience constructing simple programs in a functional programming language or in a language with functional features.

Functional programming languages include:

  • Haskell
  • Standard ML
  • Scheme
  • Lisp

Many multi-paradigm languages also support functional programming, including Python, F#, C#, Scala, Java 8 onwards, Delphi XE onwards, and VB.NET 2008 onwards.

Definition

Functional programming language

A functional programming language is a language designed to support programs built mainly from functions, often treating functions as values and encouraging expressions that produce results rather than commands that change state.

You do not need to use the same language as another student. The important thing is that you can read, write, and trace simple functional ideas such as passing a function into another function.

Functions as values

In functional programming, a function can often be treated like data: it can be stored in a variable, passed into another function, or returned as the result of a function.

Definition

First-class function

A first-class function is a function that can be used as a value: assigned to a name, passed as an argument, or returned from another function.

For example, a function called double could be passed into another function that applies it to every item in a list.

You will also often see short unnamed functions.

Definition

Anonymous function

An anonymous function, often called a lambda, is a function written without giving it a permanent name. It is useful when a small function is only needed once.

In pseudocode, you might see a lambda written like this:

x -> x * 2

This means “take x and return x * 2”.

Higher-order functions

A higher-order function is one of the most important ideas in this topic.

Definition

Higher-order function

A function is higher-order if it takes a function as an argument, returns a function as a result, or does both.

For example:

applyTwice(functionToApply, value)

could be higher-order because one of its inputs is itself a function.

Example

Identifying higher-order functions

Decide which of these functions are higher-order:

  • square(x) returns x * x
  • applyTwice(f, x) returns f(f(x))
  • makeAdder(n) returns the function x -> x + n
  1. square(x) takes an ordinary value and returns an ordinary value, so it is not higher-order.
  2. applyTwice(f, x) takes f as an argument, and f is used like a function, so applyTwice is higher-order.
  3. makeAdder(n) returns a new function, x -> x + n, so makeAdder is higher-order.
Key Idea

Why higher-order functions matter

Higher-order functions let you separate what operation should be done from how the data structure is processed.

The three core operations: map, filter, reduce/fold

The most common higher-order functions you need to use are map, filter, and reduce/fold. They are usually applied to lists.

The three standard operations are easiest to compare as a data flow.

Diagram comparing map, filter and reduce/fold on the list [1, 2, 3, 4]

map: transform every item

map applies a given function to each element of a list, returning a list of results.

Definition

map

map is a higher-order function that applies a supplied function to every element in a list and returns a new list containing the results.

For example, mapping x -> x * 2 over [1, 2, 3] gives [2, 4, 6].

The key point is that map keeps the same number of elements. Each item is transformed, but no items are removed.

Example

Tracing map

A list stores temperatures in Celsius:

temperatures <- [0, 10, 20]

Use map with the function F=1.8C+32F = 1.8C + 32F=1.8C+32 to convert each temperature to Fahrenheit.

  1. Apply the function to the first value: 1.8×0+32=321.8 \times 0 + 32 = 321.8×0+32=32.
  2. Apply the same function to the second value: 1.8×10+32=501.8 \times 10 + 32 = 501.8×10+32=50.
  3. Apply the same function to the third value: 1.8×20+32=681.8 \times 20 + 32 = 681.8×20+32=68.
  4. Collect the results in the same order, giving [32, 50, 68].
Key Idea

map keeps the shape

If the input list has five items, the output from map also has five items. The values may change, but the list length does not.

filter: keep only matching items

filter uses a condition to decide which elements should stay in a list.

Definition

Predicate

A predicate is a function that returns a Boolean value: either TRUE or FALSE.

Definition

filter

filter is a higher-order function that processes a data structure, usually a list, and returns a new data structure containing exactly the elements that satisfy a given condition.

For example, filtering [3, 8, 10, 15] with the predicate x -> x >= 10 gives [10, 15].

Example

Tracing filter

A list stores file sizes in MiB:

sizes <- [12, 55, 8, 73, 30]

Use filter to keep only files larger than or equal to 50 MiB.

  1. Test 12 against the condition size >= 50; it is false, so remove it from the result.
  2. Test 55; it satisfies the condition, so keep it.
  3. Test 8; it does not satisfy the condition, so remove it.
  4. Test 73; it satisfies the condition, so keep it.
  5. Test 30; it does not satisfy the condition, so remove it.
  6. The filtered list is [55, 73].
Common Mistake

Confusing map and filter

map changes every item and keeps the list length the same. filter keeps or removes whole items and may make the list shorter.

reduce or fold: combine a list into one result

reduce, also called fold, repeatedly applies a combining function to reduce a list of values to a single value.

Definition

Accumulator

An accumulator is a value that stores the result built up so far during a reduce/fold operation.

Definition

reduce or fold

reduce or fold is a higher-order function that reduces a list to a single value by repeatedly applying a combining function to the list values.

A fold normally needs:

  • a starting accumulator value
  • a combining function
  • a list to process

For summing numbers, the starting accumulator is usually 0, because adding 0 does not change the total.

Example

Tracing a fold

Fold the list [4, 7, 2] using the combining function accumulator + item, starting with accumulator 0.

  1. Start with accumulator 0, then combine with the first item: 0 + 4 gives accumulator 4.
  2. Combine accumulator 4 with the next item: 4 + 7 gives accumulator 11.
  3. Combine accumulator 11 with the final item: 11 + 2 gives accumulator 13.
  4. The list is exhausted, so the fold result is 13.
Common Mistake

Fold order can matter

If the combining operation is not order-independent, such as subtraction or string concatenation, changing the fold direction or the item order can change the result.

Building a simple functional program

A typical simple functional program uses a pipeline:

  1. filter to select the data you care about
  2. map to transform that data
  3. fold/reduce to combine the transformed data into one result
Definition

Pipeline

A pipeline is a sequence of operations where the output of one operation becomes the input to the next.

Suppose you have exam scores. You want to:

  • keep only scores of 60 or more
  • add 2 moderation marks to each remaining score
  • calculate the total of the moderated scores

In language-neutral pseudocode:

scores <- [42, 76, 58, 91, 63]

passingScores <- filter(score -> score >= 60, scores)

moderatedScores <- map(score -> score + 2, passingScores)

total <- fold((accumulator, score) -> accumulator + score, 0, moderatedScores)
Example

Building a functional pipeline

Trace the program above.

  1. Apply the filter condition score >= 60 to the original list [42, 76, 58, 91, 63], giving [76, 91, 63].
  2. Apply the map function score -> score + 2 to each remaining score, giving [78, 93, 65].
  3. Fold the moderated list with addition from starting accumulator 0: 0 + 78 gives 78, then 78 + 93 gives 171, then 171 + 65 gives 236.
  4. The final value of total is 236.

Here is the same idea in Python 3:

from functools import reduce

scores = [42, 76, 58, 91, 63]

passing_scores = list(filter(lambda score: score >= 60, scores))
moderated_scores = list(map(lambda score: score + 2, passing_scores))
total = reduce(lambda accumulator, score: accumulator + score, moderated_scores, 0)
Tip

Python 3 map and filter

In Python 3, map and filter produce iterable objects. Use list(...) when you want to display or store the actual list of results.

Choosing the right operation

When you read a problem, decide what kind of job is being described:

  • “Apply this calculation to every item” usually means map.
  • “Keep only the items that meet this condition” usually means filter.
  • “Combine all items into one total, maximum, string, or result” usually means reduce or fold.
Common Mistake

Changing the order without checking meaning

filter then map may not mean the same thing as map then filter. For example, filtering passing scores before adding bonus marks is different from adding bonus marks before checking who passed.

Exam technique

In the exam

  1. Identify whether the task is transforming items, selecting items, or combining items; then choose map, filter, or reduce/fold.
  2. When tracing, write the intermediate list after each operation rather than trying to jump straight to the final answer.
  3. For higher-order functions, explicitly say whether a function is being passed in, returned, or both.
Self review

Check yourself

  • What is the difference between map and filter?
  • Why is fold described as reducing a list to a single value?
  • How can a function be higher-order even if it never processes a list?
You've reached the end

Test yourself on this topic, or move on to the next guide.

FlashcardsSelf-test with active recall
Lists in functional programmingUp next

How was this guide?

Writing functional programs Revision Guide