Functional Programming Paradigm

In functional programming, a function is a mathematical mapping from an input set to an output set.

$f:A\to B$

• $A$ is the domain — the set of all valid inputs (the input type)
• $B$ is the co-domain — the set of all possible outputs (the output type)

Worked examples:

Function	Notation	Meaning
Integer addition	$\text{add}:\mathbb{Z}\times \mathbb{Z}\to \mathbb{Z}$	Takes two integers; returns an integer
String length	$\text{length}:\text{String}\to \mathbb{N}$	Takes a string; returns a natural number (non-negative integer)
Even predicate	$\text{isEven}:\mathbb{Z}\to \text{Bool}$	Takes an integer; returns a Boolean

The notation $f:A\to B$ specifies the function's type. For a function to be composable with another, the types must be compatible.

Multi-argument functions: modelled as functions of a Cartesian product: $f:A\times B\to C$

This takes a pair $(a,b)$ from the Cartesian product $A\times B$ and maps it to an element of $C$.

In functional programming, functions are first-class objects — they can be used anywhere any other value can be used:

1. Assigned to a variable:

   double = \x -> x * 2
   

2. Passed as an argument to another function:

   map double [1, 2, 3]  -- applies double to every element
   

3. Returned from a function:

   makeAdder n = \x -> x + n
   add5 = makeAdder 5
   add5 10  -- returns 15
   

4. Stored in data structures:

   operations = [double, (+1), (*3)]
   

Treating functions as first-class values enables the higher-order function patterns (map, filter, fold) that make functional programming expressive.

Function application is the act of applying a function to its argument(s).

$f(x)\text{ or simply }fx\text{ (Haskell notation — no brackets required)}$

Examples:

square 5         -- evaluates to 25
not True         -- evaluates to False
length "hello"   -- evaluates to 5

Multi-argument application:

add 3 4    -- evaluates to 7

In Haskell, multi-argument functions are applied one argument at a time (currying). add 3 4 is (add 3) 4 — first apply add to 3, getting a function, then apply that function to 4.

Partial function application applies a function to fewer arguments than it expects, producing a new function that takes the remaining arguments.

Type signature: $\text{add}:\text{integer}\to \text{integer}\to \text{integer}$

This reads: add takes an integer and returns a function from integer to integer. In other words, the arrow groups right-to-left: $\text{integer}\to (\text{integer}\to \text{integer})$.

Partial application example:

add : integer -> integer -> integer
add 4 : integer -> integer   -- partially applied: add 4 returns a new function
add 4 6 = 10                 -- fully applied

add 4 is a function that adds 4 to any integer. It can be passed to map:

map (add 4) [1, 2, 3]   -- evaluates to [5, 6, 7]

This is the power of partial application: specifying some arguments now and the rest later, creating specialised functions from general ones.

Function composition combines two functions into a single function, applying one after the other.

$g\circ f:A\to C\text{where }f:A\to B\text{ and }g:B\to C$

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

Key constraint: the co-domain of $f$ must equal the domain of $g$. The output type of $f$ must be the input type of $g$.

Worked example:

Let $f:\text{String}\to \mathbb{Z}$ be length (maps strings to integers) and $g:\mathbb{Z}\to \text{Bool}$ be isEven (maps integers to booleans).

$g\circ f:\text{String}\to \text{Bool}$

$(g\circ f)(\text{"hello"})=g(f(\text{"hello"}))=g(5)=\text{False}$

lengthIsEven = isEven . length   -- composition in Haskell uses (.)
lengthIsEven "hello"             -- False
lengthIsEven "hi"                -- True

Why composition matters: it allows building complex transformations from simple, tested functions — a core principle of functional programming.

1. Confusing domain and co-domain

The domain is the input type (what the function accepts). The co-domain is the output type (what it returns). $f:A\to B$ — A is the domain, B is the co-domain. Swapping them in type notation is a common error.

2. Confusing function application with function definition

square 5 is applying the function square to the value 5 — it evaluates to 25. It is not defining a function called square 5. Function application produces a value; function definition creates a function.

3. Misreading the arrow notation for partial application

$\text{add}:\text{integer}\to \text{integer}\to \text{integer}$ does not mean add takes two separate arguments simultaneously. It means add takes one integer and returns a function $(\text{integer}\to \text{integer})$. The arrow is right-associative.

4. Applying composition in the wrong order

$(g\circ f)(x)=g(f(x))$ — $f$ is applied first, then $g$. Reading $g\circ f$ left-to-right, $g$ appears first — but it is applied second. The rightmost function in the composition chain runs first.