Computer Science (9645) | The functional programming paradigm

👋 Welcome to Functional Programming!

You are about to dive into the Functional Programming Paradigm. This is a very different way of thinking about coding compared to the procedural programming you might be used to (where you focus on sequences of steps and changing variables).

Functional Programming (FP) treats computation as the evaluation of mathematical functions and avoids changing state and mutable data. It's based on robust mathematical concepts, which makes the code often more predictable, easier to test, and excellent for tackling complex problems like Big Data processing!

Don't worry if it feels abstract at first—we'll break down the mathematical ideas into simple, manageable chunks using clear examples.

1. The Functional Programming Paradigm: Foundations

1.1 Functions as Mappings (The Mathematical View)

In functional programming, a function is treated like a mathematical rule that maps inputs to outputs.

Key Concept: Function Type Notation

Every function, \(f\), has a defined type that specifies what kind of input it takes and what kind of output it produces.

Notation:
$$f: A \rightarrow B$$

• A is the Domain (the set of all valid input values).
• B is the Co-domain (the set from which the output values are chosen).
• The arrow (\(\rightarrow\)) represents the 'maps to' relationship.

Example: If a function squares an integer, its type might be:

square: Integer $\rightarrow$ Integer

Important Note on Co-domain: Not every member of the co-domain (B) needs to be an actual output.
Example: The function $\texttt{sqr}: \mathbb{R} \rightarrow \mathbb{R}$ (squaring a real number) has the set of all Real Numbers (\(\mathbb{R}\)) as its co-domain. However, the result of a square cannot be negative, so negative numbers in \(\mathbb{R}\) are never outputs.

1.2 Common Number Systems (Domains and Co-domains)

You must be familiar with the standard mathematical sets used for function domains and co-domains:

• Natural Numbers ($\mathbb{N}$): The set of positive whole numbers, including zero.
  $$\mathbb{N} = \{0, 1, 2, 3, \ldots\}$$
• Integers ($\mathbb{Z}$): The set of all whole numbers (positive, negative, and zero).
  $$\mathbb{Z} = \{\ldots, -2, -1, 0, 1, 2, \ldots\}$$
• Rational Numbers ($\mathbb{Q}$): Numbers that can be written as a fraction (a ratio of two integers).
  Did you know? Since any integer \(n\) can be written as \(n/1\), all integers are also rational numbers.
• Real Numbers ($\mathbb{R}$): The set of all 'possible real-world quantities,' including integers, rational numbers, and irrational numbers (like \(\pi\) or \(\sqrt{2}\)).

2. First-Class Objects and Function Application

2.1 First-Class Objects (or Values)

In functional programming languages, functions themselves are given special importance. They are treated as first-class objects (or first-class values).

Think of 'first-class' like being a VIP—functions can go anywhere and do anything that standard data types (like integers or strings) can do.

A first-class object may:

1. Appear in expressions (e.g., \(2 \times (\texttt{add } 3)\)).
2. Be assigned to a variable (e.g., storing a function definition in a variable).
3. Be assigned as arguments (passed as input to another function).
4. Be returned in function calls (outputted by another function).

Did you know? This ability for functions to be passed around is what makes concepts like Higher-Order Functions possible!

2.2 Function Application and Arguments

The act of running a function with specific inputs is called function application.

Example: Applying the function $\texttt{add}$ to arguments 3 and 4 is written as $\texttt{add } (3, 4)$.

When a function takes multiple arguments, the domain is represented by a Cartesian product of the argument types.

Type notation for two arguments:
$$\texttt{add: integer } \times \texttt{ integer } \rightarrow \texttt{ integer}$$
This means the function $\texttt{add}$ takes a pair of integers (the Cartesian product) and returns a single integer.

3. Advanced Concepts: Higher-Order Functions (HOFs)

3.1 What is a Higher-Order Function?

A function is considered higher-order if it meets one or both of these conditions:

1. It takes one or more other functions as arguments.
2. It returns a function as its result.

Analogy: If a normal function makes coffee (takes milk and sugar, returns coffee), a HOF is like a coffee shop manager: it takes the recipe (a function) and the ingredients, and perhaps hands off the resulting coffee machine (another function) to someone else.

3.2 Composition of Functions

Functional composition is an operation that combines two functions to create a third, new function. The output of the first function becomes the input of the second.

Step-by-step composition:

Given two functions:
$$f: A \rightarrow B \text{ and } g: B \rightarrow C$$

The composition $g \circ f$ (pronounced "g after f" or "g composed with f") is a new function:
$$g \circ f: A \rightarrow C$$

• Step 1: Function $f$ is applied first to an input from domain $A$. It returns a value in co-domain $B$.
• Step 2: Function $g$ is then applied to the result returned by $f$. It returns a value in co-domain $C$.

Example using Real Numbers ($\mathbb{R}$):

• Let \(f(x) = x + 2\)
• Let \(g(y) = y^3\)

The composition \(g \circ f\) is:
$$g \circ f = (x + 2)^3$$

4. Essential Higher-Order Functions: Map, Filter, and Fold

These three functions are fundamental tools in functional programming, often applied to data structures like lists. You must be able to recognize and trace their use (often in Haskell syntax for exams).

4.1 Map

The $\texttt{map}$ function applies a given function to every element of a list, resulting in a new list of the results. The original list remains unchanged.

Example (Haskell syntax):
Imagine we have a function $\texttt{square x = x * x}$ and a list of numbers.

$$\texttt{numbers = [1, 2, 3, 4]}$$ $$\texttt{map square numbers}$$

Produces the list: $\texttt{[1, 4, 9, 16]}$

4.2 Filter

The $\texttt{filter}$ function processes a list by applying a Boolean condition (a function that returns $\texttt{True}$ or $\texttt{False}$) to each element. It returns a new list containing only the elements that satisfy the condition.

Example (Haskell syntax):
We want numbers less than 10.

$$\texttt{filter (<10) [15, 8, 20, 3]}$$

Produces the list: $\texttt{[8, 3]}$

4.3 Fold (or Reduce)

The $\texttt{fold}$ function reduces a list of values to a single value by repeatedly applying a combining function, starting with an initial value.

There are two types you need to know, depending on whether the function processes the list from the left or the right. The results are sometimes the same (e.g., for addition), but sometimes very different (e.g., for subtraction).

Fold Left ($\texttt{foldl}$)

$\texttt{foldl}$ starts with the leftmost item and works forward. The combining function is repeatedly applied, incorporating the initial value first.

$$\texttt{foldl} (\text{+}) \ 0 \ \texttt{[1, 2, 3, 4]}$$

Evaluation (Left to Right):
$$((((0 + 1) + 2) + 3) + 4) = 10$$

Now, let's try subtraction:
$$\texttt{foldl} (-) \ 0 \ \texttt{[1, 2, 3, 4]}$$
Evaluation (Left to Right):
$$((((0 - 1) - 2) - 3) - 4) = -10$$

Fold Right ($\texttt{foldr}$)

$\texttt{foldr}$ starts with the rightmost item and works backward.

$$\texttt{foldr} (-) \ 0 \ \texttt{[1, 2, 3, 4]}$$

Evaluation (Right to Left):
$$1 - (2 - (3 - (4 - 0)))$$ $$1 - (2 - (3 - 4))$$ $$1 - (2 - (-1))$$ $$1 - 3 = -2$$

⚠️ Common Mistake Alert: Always remember the directionality and the initial value when tracing $\texttt{foldl}$ and $\texttt{foldr}$, especially with non-commutative operations like subtraction!

5. Lists, Recursion, and Pattern Matching

5.1 Lists in Functional Programming

A list is a sequence of values, usually enclosed in brackets, e.g., $\texttt{[7, 2, 1]}$. The empty list is simply $\texttt{[]}$.

The Head and the Tail

In functional languages, a non-empty list is fundamentally viewed as two parts:

1. The Head: The first element (a single value).
2. The Tail: The remainder of the list (which is always another list, even if it is empty).

Example: The list $\texttt{[4, 3, 5]}$ is represented as $\texttt{4 : [3, 5]}$.
The Head is $\texttt{4}$.
The Tail is $\texttt{[3, 5]}$.

5.2 Essential List Operations (Haskell Examples)

You need to be able to describe and apply these standard operations:

• Return Head: $\texttt{head [1, 2, 3]}$ evaluates to $\texttt{1}$.
• Return Tail: $\texttt{tail [1, 2, 3]}$ evaluates to $\texttt{[2, 3]}$.
• Test for Empty: $\texttt{null [1, 2, 3]}$ evaluates to $\texttt{False}$. $\texttt{null []}$ evaluates to $\texttt{True}$.
• Return Length: $\texttt{length [1, 2, 3]}$ evaluates to $\texttt{3}$.
• List Concatenation: The $\texttt{++}$ operator joins two lists.
  $$\texttt{[1, 2, 3] ++ [4, 5]}$$ Evaluates to: $\texttt{[1, 2, 3, 4, 5]}$

5.3 Recursion and Pattern Matching

Since functional programming avoids traditional loops (iteration) and changing variables, complex tasks are often solved using recursion.

A recursive function calls itself, and it relies on two crucial components:

1. Base Case: The condition that causes the function not to call itself again, terminating the process. (Must exist to prevent indefinite recursion!)
2. Recursive Case: The condition where the function calls itself, usually working on a slightly smaller input.

Pattern Matching: Defining Cases

Pattern matching is a mechanism used to define different behaviours for a function based on the structure or value of its arguments (like defining the base case vs. the recursive case).

Example: Factorial Calculation (n! = n * (n-1)!)

In Haskell, we define the base and recursive cases clearly:
$$\texttt{fact 0 = 1}$$ (Base Case: Matches the input 0)
$$\texttt{fact n = n * fact (n-1)}$$ (Recursive Case: Matches any other number n)

Referring to Head and Tail in Recursion

When defining recursive functions that process lists, pattern matching allows us to directly refer to the head and tail of the list in the function definition, often using $\texttt{(x:xs)}$:

Example: Summing all elements in a list recursively
$$\texttt{sum [] = 0}$$ (Base Case: The sum of an empty list is 0)
$$\texttt{sum (x:xs) = x + sum xs}$$ (Recursive Case)

• If the input list is $\texttt{[8, 3, 2]}$, the function matches the $\texttt{(x:xs)}$ pattern.
• $\texttt{x}$ references the head ($\texttt{8}$).
• $\texttt{xs}$ references the tail ($\texttt{[3, 2]}$).
• The function returns: $\texttt{8 + sum [3, 2]}$ (calling itself on the smaller list).