Basics of Functional Programming Revision Notes for AQA A-Level Computer Science

Basics of Functional Programming

Introduction

In previous studies, you learned about mathematical functions - operations that take input values from one set and produce output values in another set. For instance, a function might accept the numbers {1, 2, 3, 4, 5} and output their squares {1, 4, 9, 16, 25}, where the rule is $f(x) = x^2$ . This concept of functions extends beyond mathematics into programming.

infoNote

The connection between mathematical functions and programming functions is fundamental to understanding functional programming. Just as a mathematical function consistently maps inputs to outputs, programming functions in the functional paradigm maintain this same predictable behavior.

In programming languages, functions work as subroutines that receive arguments (input data) and perform operations to return results. The functional programming paradigm takes this idea further by building entire programs primarily through function calls, treating functions similarly to mathematical operations. This chapter explores how functions serve as the fundamental building blocks for constructing algorithms and solving problems in a functional programming style.

This simple diagram illustrates the basic concept of a function: it receives an input, processes it according to its defined rule, and produces an output.

The functional programming paradigm

What is a programming paradigm?

A programming paradigm represents a methodology or approach to writing programs. Throughout your studies, you've encountered different paradigms that shape how programmers think about and structure their code. The two most common paradigms are:

Procedural languages (also called imperative languages) require programmers to write sequences of instructions that the computer executes step by step. The programmer explicitly states how to accomplish a task through a series of commands. Languages like Python, Java, and C can be used procedurally.

Object-oriented languages allow programmers to create self-contained objects that bundle together both code (methods) and data (attributes). This approach organizes programs around objects that interact with each other. Many modern languages support object-oriented programming.

Understanding the functional programming paradigm

The functional programming paradigm represents an example of declarative programming, where programmers specify what properties a result should have rather than detailing the exact steps to achieve it. In functional programming, every line of code consists of calls to functions, which themselves may call other functions or produce values directly.

Functional programs behave like mathematical functions: they take inputs and produce outputs according to defined rules. The crucial characteristic is that all operations use functions to perform calculations. The program centers around one main function that calls additional functions as needed to accomplish specific tasks. Each function may invoke other functions, building a hierarchy of function calls that ultimately generates results.

Key principle: predictable behaviour

chatImportant

The Core Principle of Functional Programming

When you provide the same input to a function, it will always return the same output. This consistency means there are no "unforeseen side effects" - the function doesn't unexpectedly change values elsewhere in the program or behave differently depending on external factors.

This contrasts with procedural programming languages, where variables can change value throughout program execution. In procedural programs, modifications made within one subroutine might affect another subroutine, creating dependencies that make debugging challenging. Programmers often spend considerable time tracking variable values to locate where programs have gone wrong. Well-designed functional programs eliminate this problem by ensuring functions produce consistent, predictable results.

Advantages of functional programming

Several compelling reasons motivate the use of functional programming:

Clearer abstractions: Program requirements can be defined more naturally as a series of function-based abstractions rather than complex sequences of procedural steps.
Fewer implementation errors: Using broader abstractions reduces the likelihood of mistakes during coding.
High reusability: Functions can be applied at any level of data abstraction, making them highly reusable throughout a program.
Easier testing and debugging: Since each function cannot have side effects, it only needs testing once. You can verify that a function works correctly in isolation, knowing it will behave the same way every time it's called.
No concurrency issues: Because functional programs don't modify data, multiple threads cannot simultaneously alter the same information, eliminating race conditions and synchronisation problems.
Multi-processor efficiency: In multi-processor environments, the order in which functions are evaluated becomes less critical, allowing better parallel execution.

Real-world applications

infoNote

Practical Applications of Functional Programming

Functional programs excel in applications requiring extensive calculations. Because they use mathematical expressions extensively, functional programming proves valuable for:

Improving the reliability of mobile telephone networks
Analysing large volumes of financial data
Creating control systems in robotics
Developing aerospace industry applications

Programming languages supporting functional programming

Some languages specifically use the functional programming paradigm, including Lisp, Haskell, Standard ML, Scheme, and Erlang. Additionally, many languages traditionally used procedurally or in object-oriented ways now provide support for functional programming techniques. These include Python, Perl, C#, D, F#, Java 8, and Delphi XE. This flexibility allows programmers to choose functional approaches when they best suit the problem at hand.

Function types

Understanding function types

A function type describes the way a function expression is constructed. All functions follow the pattern $A \rightarrow B$ , where the function takes an argument from set $A$ and produces a result in set $B$ . This notation shows both the input type ( $A$ ) and the output type ( $B$ ).

In our earlier example, if $A$ represents the set {1, 2, 3, 4, 5} and $B$ represents {1, 4, 9, 16, 25}, then the function $f: A \rightarrow B$ describes a function that accepts values from $A$ and produces values in $B$ .

Domain and codomain

Two important concepts help us understand function types:

Domain: This represents the set of data of the same type that serves as the inputs for a function. In the example above, the domain $A$ contains the integers {1, 2, 3, 4, 5}. The domain defines what types of values the function can accept.

Codomain: This represents the set of values from which the function's outputs must be drawn. In our example, the codomain $B$ contains {1, 4, 9, 16, 25}. The codomain defines the range of possible output values.

infoNote

Understanding Domain, Codomain, and Range

It's important to note that whilst the domain contains the actual inputs, the codomain represents all possible outputs that could be produced. The values actually used are referred to as the range.

Arguments in functional programming

When you pass a value to a function, this value is called an argument. For example:

In the expression $a = f(x)$ , $x$ is the argument
In the expression $b = f(2, 4)$ , both 2 and 4 are arguments

Arguments provide the specific data that functions operate upon. A function might accept one argument, multiple arguments, or even no arguments depending on its purpose.

First-class objects and higher order functions

First-class objects explained

Within functional programming environments, a function is treated as a first-class object. This means functions possess certain properties that allow them to be used in particular ways within programs. The broad definition states that a first-class object is any object that can be passed as an argument to a function or returned as a result from a function call.

In functional programming, this means functions themselves can be:

Passed as arguments to other functions
Returned as results from functions
Stored in data structures
Assigned to variables

Other objects, such as integer values, can also be first-class objects. The key characteristic is the ability to pass them around within the program just like any other data.

Higher order functions

A function that accepts another function as an argument is called a higher order function. The three most common higher order functions are:

map - applies a function to every element in a list
fold - combines elements using a function to produce a single result
filter - selects elements that satisfy a condition

These powerful tools allow you to write concise, expressive code by operating on collections of data using functions.

Example: The map function in Haskell

lightbulbExample

Worked Example: Using the Map Function

Consider this example written in Haskell that demonstrates a first-class object:

map (*2) [1,2,3,4,5]

Let's break down what's happening:

map is itself a function that takes another function and applies it to every element in a list
(*2) represents "multiply by two" - this is the function that map will use
[1,2,3,4,5] is the list of numbers to process

The result of this higher order function would be [2,4,6,8,10].

In this example, map serves as the higher order function, whilst *2 and the numbers 1, 2, 3, 4, and 5 are all first-class objects. The function *2 is being treated just like data - passed as an argument to another function.

Function application

The process of function application

Function application describes the process of calculating a function's result by providing it with data to work on. When you apply a function, you're taking an input value from the domain and using the function's rule to produce an output in the codomain.

Let's return to our earlier example where $f(x) = x^2$ . We have:

Domain $A$ containing integers
Codomain $B$ containing integers
The function rule: square the input

When we input a single value from $A$ , this can be described as the function "taking its argument" or "the argument being passed to the function." The function applies its rule to the argument - in this case, squaring it - to produce an output in $B$ .

Function application with multiple arguments

Functions often require multiple pieces of data to operate. Consider a function designed to calculate the volume of a box:

$\text{volume} = \text{int} \times \text{int} \times \text{int} \rightarrow \text{int}$

This notation shows that the function accepts three integer inputs and produces an integer output. In this case, the three values represent the height, width, and breadth of the box. The argument is actually three values, which would be defined within the code appropriately.

lightbulbExample

Worked Example: Calculating Cuboid Volume

Here's how this might be written in code:

let cuboidvolume height width breadth = height * width * breadth

To apply this function, you would provide all three measurements:

cuboidvolume 3 4 5

Step-by-step calculation:

The function cuboidvolume receives three arguments: 3, 4, and 5
It multiplies them together: $3 \times 4 \times 5$
The result is 60

This demonstrates full function application where all required arguments are provided simultaneously.

Partial function application

Understanding partial application

In the cuboid volume example, the function requires three values as a single argument to perform its calculation. However, it's possible to pass fewer than the complete number of arguments to a function. When you do this, you're using partial function application.

The concept behind partial application is creating an intermediate function by fixing some of the arguments. When you have a function that takes many arguments, partially applying it allows you to effectively create a new function that performs part of the calculation. The partial application of a function can produce results that are useful independently, in addition to contributing to the full application of the function.

Comparing full and partial application

Consider two different notations for a function that adds two integers together:

Full application: $\text{add}: \text{int} \times \text{int} \rightarrow \text{int}$

Partial application: $\text{add}: \text{int} \rightarrow \text{int} \rightarrow \text{int}$

These represent different approaches:

The first notation shows a full application where the function accepts two integers as arguments and adds them together to produce a result (also an integer). Both values are passed as arguments simultaneously.

The second notation represents a partial application. This creates a new function that always adds the first argument value to another number. This new intermediate function is then applied to the second argument to produce the final result.

Practical example of partial application

lightbulbExample

Worked Example: Full vs Partial Application

Let's see how this works in practice with an add function:

Full function application would add $x$ and $y$ simultaneously:

add (x,y): add (2,3) = 5

Partial function application creates an intermediate function:

add (x,y): add (2,3) = add2 (3) = 5

In the partial application:

The function first receives the argument value 2
This creates a new function called add2 that will add 2 to whatever number it receives
The new function add2 is then applied to the argument 3
The final result is still 5

Partial application proves particularly useful when you want to create specialized versions of general functions, or when you want to build up complex operations step by step.

Function composition

Building complex functions from simple ones

Function composition describes the process of combining two or more existing functions together to create more complex functions. This represents one of the core principles of functional programming: complex operations are built from simpler building blocks. Each component function produces its result, which is then passed as an argument to the next function. This process continues for each component function until a final result emerges for the complete, complex function.

How composition works with domain and codomain

Imagine you have two functions:

Function $f$ is applied to domain $A$
Function $g$ is applied to domain $B$

We can write these as:

$f: A \rightarrow B$
$g: B \rightarrow C$

When we compose these functions, the result of function $f$ becomes the input for function $g$ .

infoNote

Understanding Composition Through Domains

For function $f$ , $A$ serves as the domain and $B$ serves as the codomain, so applying $f$ to $A$ produces results in $B$ .

For function $g$ , $B$ serves as the domain and $C$ serves as the codomain, so applying $g$ to $B$ produces results in $C$ .

When we perform function composition of these two functions, $A$ becomes the overall domain and $C$ becomes the overall codomain, producing the final range (output).

This diagram illustrates how composition chains functions together. The output from the first function becomes the input for the second function, ultimately producing the final result.

Worked example of function composition

lightbulbExample

Worked Example: Composing Two Functions

Let's work through a concrete example. Assume:

Function $f$ is $f(x) = x^2$
Function $g$ is $g(x) = x + 3$

To work out the composition of $g$ and $f$ , follow these steps:

Step 1: Pass an argument with a value, for example 4

Step 2: Function $f$ squares it: $f(4) = 4^2 = 16$

Step 3: The value 16 becomes the input for function $g$

Step 4: Function $g$ adds 3 to the result: $g(16) = 16 + 3 = 19$

Step 5: The result of the combined function is 19

Notation for function composition

Function composition can be shown using the following notation:

$g \circ f$

where the symbol $\circ$ indicates composition of functions $g$ and $f$ .

For our example:

$f(x) = x^2$
$g(x) = x + 3$
$g \circ f$ becomes $g(f(x)) = x^2 + 3$

This notation shows that we first apply $f$ to $x$ (squaring it), then apply $g$ to the result (adding 3). The composite function directly expresses what happens to the input through both operations combined.

chatImportant

Order Matters in Function Composition

Function composition allows you to build sophisticated operations by chaining together simpler functions, making your code more modular, reusable, and easier to understand. Remember that the order of composition is crucial: $g \circ f$ means "apply $f$ first, then apply $g$ to the result."

Remember!

bookmarkSummary

Key Points to Remember:

Functional programming treats functions like mathematical operations, where the same input always produces the same output, eliminating unpredictable side effects and making programs easier to test and debug.
Functions are first-class objects that can be passed as arguments, returned as results, and manipulated like any other data. Higher order functions like map, fold, and filter accept other functions as arguments to perform powerful operations.
Function types describe the domain (input set) and codomain (output set) using notation like $f: A \rightarrow B$ , helping you understand what data a function accepts and what it can produce.
Partial application allows you to create specialized functions by fixing some arguments whilst leaving others variable, providing flexibility in how you apply functions.
Function composition ( $g \circ f$ ) combines simpler functions to build more complex operations, with the output of one function becoming the input of the next, embodying the modular nature of functional programming.

Basics of Functional Programming (AQA A-Level Computer Science): Revision Notes