Functional programming paradigm

What you'll learn

How to read a function type such as $\rightarrow B$ .
Why functions can be treated as first-class objects.
What happens when a function is applied to one or more arguments.
How partial application and function composition build new functions from existing ones.

Big picture: what is functional programming?

A programming paradigm is a style of programming: a set of ideas about how programs should be structured. In the functional programming paradigm, computation is mainly described by evaluating functions and combining functions.

This topic is mostly about the notation AQA expects you to recognise and use. You do not need to learn a particular functional language here; focus on the mathematical ideas behind functions.

4.12.1.1 Function type

Definition

Function type

A function $f$ has a type written $\rightarrow B$ . This means the function takes an input from set $A$ and returns an output from set $B$ . The type itself is $\rightarrow B$ .

The set $A$ is the argument type. It is also called the domain: the set from which input values are chosen.

The set $B$ is the result type. It is also called the co-domain: the set from which output values are chosen.

A data type is a category of values, such as integer, character, Boolean or string. The domain and co-domain are always subsets of objects in some data type. For example, the set of lowercase letters is a subset of character values, and the set ${0,1,2,…,25}\{0,1,2,\dots,25\}$ is a subset of integer values.

A function does not have to use every value in its co-domain. It only needs to return values that belong to the co-domain.

The diagram shows a function from a domain to a co-domain, and also previews how two functions can be composed later in this topic.

Diagram showing domain, co-domain, unused co-domain values, and function composition

Key Idea

Domain versus co-domain

The domain is where inputs come from. The co-domain is where outputs are allowed to come from. Not every co-domain value must actually be produced.

For example, suppose:

\{a,b,c,\dots,z\} \rightarrow \{0,1,2,\dots,25\}

with the rule that $\mapsto 0$ , $\mapsto 1$ , and so on. Here the input values are letters, and the output values are integers from 0 to 25.

Example

Finding a function type

A function lengthOfWord takes one lowercase word and returns the number of characters in it. Assume the longest allowed word has 20 characters.

Choose the domain by identifying the possible inputs: the input is one lowercase word, so the domain is a set of lowercase strings.
Choose the co-domain by identifying the allowed outputs: the output is a whole number from 0 to 20, so the co-domain is ${0,1,2,…,20}\{0,1,2,\dots,20\}$ .
Write the function type using arrow notation: $lengthOfWord:lowercaseString→{0,1,2,…,20}\text{lengthOfWord}: \text{lowercaseString} \rightarrow \{0,1,2,\dots,20\}$ .

Common Mistake

Confusing co-domain with actual outputs

Do not assume the co-domain is exactly the set of values that will be produced. It is the set of values that may be used as outputs.

4.12.1.2 First-class object

Definition

First-class object

A first-class object is a value that may appear in expressions, be assigned to a variable, be passed as an argument, and be returned from a function call.

In many languages, integers, floating-point values, characters and strings are first-class objects. In functional programming languages, functions are also first-class objects.

Some imperative programming languages also support first-class functions. An imperative programming language is one where programs are mainly written as sequences of commands that update state. If such a language supports first-class functions, a function can be handled like other values.

This means a function can be:

stored in a variable;
passed into another function;
returned as the result of a function call;
used in an expression.

A function that takes another function as an argument, or returns a function, is often called a higher-order function.

Example

Passing a function as an argument

Suppose double is a function where $double(n)=n×2\text{double}(n) = n \times 2$ , and applyTwice is defined as $applyTwice(functionValue,x)=functionValue(functionValue(x))\text{applyTwice}(functionValue, x) = functionValue(functionValue(x))$ .

Pass the function double as the first argument and 5 as the second argument: $applyTwice(double,5)\text{applyTwice}(\text{double}, 5)$ .
Apply the inner function call first: $double(5)=10\text{double}(5) = 10$ .
Apply the function again to the result: $double(10)=20\text{double}(10) = 20$ .
Therefore, treating double as a first-class object allows applyTwice to return 20.

Tip

Spotting first-class functions

If a function is being passed around like data, stored in a variable, or returned by another function, it is being treated as a first-class object.

4.12.1.3 Function application

Definition

Function application

Function application means giving particular argument values to a function.

For example, $add(3,4)\text{add}(3,4)$ is the application of the function add to the integer arguments 3 and 4.

A two-argument function can be described using the Cartesian product. The Cartesian product of two sets is the set of all ordered pairs formed by taking one value from each set.

So the type of add can be written as:

add:integer×integer→integer\text{add}: \text{integer} \times \text{integer} \rightarrow \text{integer}

Although we usually say add takes two arguments, formally this version takes one argument that is a pair, such as (3, 4).

Example

Applying a function to a pair

Let $add:integer×integer→integer\text{add}: \text{integer} \times \text{integer} \rightarrow \text{integer}$ , where $add(x,y)=x+y\text{add}(x,y) = x + y$ . Find $add(7,9)\text{add}(7,9)$ .

Treat the input as one ordered pair: (7, 9) belongs to $integer×integer\text{integer} \times \text{integer}$ .
Substitute the pair values into the rule: $add(7,9)=7+9\text{add}(7,9) = 7 + 9$ .
Evaluate the result: $7 + 9 = 16$ , so the output is an integer, as required by the co-domain.

4.12.1.4 Partial function application

Definition

Partial function application

Partial function application means applying a function to fewer arguments than it ultimately needs, producing a new function that expects the remaining argument or arguments.

This idea relies on functions being first-class objects, because the result of partial application is itself a function.

One-argument functions

A one-argument function has type:

\rightarrow B

If you apply its single argument, the result has type $B$ . There are no remaining arguments, so there is no useful partial application left to do.

Two-argument functions

A two-argument function can be viewed like this:

add:integer→(integer→integer)\text{add}: \text{integer} \rightarrow (\text{integer} \rightarrow \text{integer})

This means add takes one integer and returns a function. That returned function takes another integer and returns an integer.

The brackets may be dropped:

add:integer→integer→integer\text{add}: \text{integer} \rightarrow \text{integer} \rightarrow \text{integer}

So $4\text{add}\ 4$ returns a new function that adds 4 to whatever integer it is later given.

Three-argument functions

A three-argument function can be viewed as:

\rightarrow B \rightarrow C \rightarrow D

This means:

\rightarrow (B \rightarrow (C \rightarrow D))

So:

applying the first argument gives a function of type $\rightarrow C \rightarrow D$ ;
applying the first two arguments gives a function of type $\rightarrow D$ ;
applying all three arguments gives a final value of type $D$ .

Tip

Arrow notation is right-associative

Read $\rightarrow B \rightarrow C$ as $\rightarrow (B \rightarrow C)$ , not as $\rightarrow B) \rightarrow C$ .

Example

Partially applying a three-argument function

Let $scaleAdd:integer→integer→integer→integer\text{scaleAdd}: \text{integer} \rightarrow \text{integer} \rightarrow \text{integer} \rightarrow \text{integer}$ , with $scaleAdd(a,b,x)=a⋅x+b\text{scaleAdd}(a,b,x) = a \cdot x + b$ . Work out what function is produced by $3\text{scaleAdd}\ 2\ 3$ .

Apply the first argument, 2, to fix $a = 2$ . The result is a function waiting for $b$ and $x$ .
Apply the second argument, 3, to fix $b = 3$ . The result is now a function waiting for only $x$ .
Substitute the fixed values into the rule: $\cdot x + b$ becomes $\cdot x + 3$ .
Therefore, $3\text{scaleAdd}\ 2\ 3$ is the function $\mapsto 2 \cdot x + 3$ .

Common Mistake

Forgetting that partial application returns a function

$4\text{add}\ 4$ is not the final numerical answer. It is a new function waiting for another integer.

4.12.1.5 Composition of functions

Definition

Composition of functions

Function composition combines two functions to produce a new function.

Given:

\rightarrow B

and:

\rightarrow C

the composition $\circ f$ has type:

\circ f: A \rightarrow C

This is read as “ $g$ composed with $f$ ”. The important order is: apply $f$ first, then apply $g$ to the result.

In function notation:

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

Example

Composing two functions

Let $f (x) = x + 2$ and $g(y) = y^3$ . Find $\circ f)(x)$ and then evaluate it when $x = 3$ .

Apply $f$ first: $f (x) = x + 2$ .
Use the result of $f$ as the input to $g$ : $g (f (x)) = g (x + 2)$ .
Substitute into the rule for $g$ : $g(x + 2) = (x + 2)^3$ .
Evaluate for $x = 3$ : $3 + 2)^3 = 5^3 = 125$ .

Common Mistake

Reversing the order of composition

$\circ f$ means apply $f$ first, then $g$ . It does not mean apply $g$ first.

Key Idea

Compatibility of types

For $\circ f$ to work, the output type of $f$ must match the input type of $g$ . If $\rightarrow B$ and $\rightarrow C$ , then $\circ f: A \rightarrow C$ .

Exam technique

In the exam

When you see $\rightarrow B$ , identify $A$ as the domain and $B$ as the co-domain.
For partial application, state the type of the function that is returned after each argument is supplied.
For composition, write $\circ f)(x) = g(f(x))$ to avoid reversing the order.

Self review

Check yourself

What is the difference between a function’s domain and its co-domain?
Why does partial function application require functions to be first-class objects?
If $\rightarrow B$ and $\rightarrow C$ , what is the type of $\circ f$ ?

Functional programming paradigm

What you'll learn

Big picture: what is functional programming?

4.12.1.1 Function type

4.12.1.2 First-class object

4.12.1.3 Function application

4.12.1.4 Partial function application

One-argument functions

Two-argument functions

Three-argument functions

4.12.1.5 Composition of functions

You've reached the end

Functional programming paradigm Revision Guide