HookThe messaging app that beat 450 million users with 32 engineers
When Facebook bought WhatsApp in February 2014 for around $19 billion, the detail that startled engineers was not the price but the headcount: WhatsApp was serving something like 450 million monthly users with an engineering team you could fit around a couple of dinner tables — roughly thirty. Their secret was the language underneath, Erlang, a functional language built for telephone exchanges, in which data is immutable, there is no shared mutable state, and a single server was reported to hold on the order of two million simultaneous connections. Immutability and the absence of side effects meant whole classes of bug — the race conditions and corrupted shared variables that sink ordinary concurrent code — simply could not occur, and a tiny team could reason about an enormous system with confidence.
That is the payoff this section is building towards, and its roots go back further than any computer: in the 1930s the mathematician Alonzo Church devised the lambda calculus, a model of computation based entirely on defining and applying functions, with no variables to reassign and no steps to sequence. Functional programming is that idea turned into a language. Instead of commanding the machine through a list of state-changing instructions — the imperative style you already know — you build a program by composing functions, each of which merely maps inputs to outputs and changes nothing. This section is the vocabulary of that world: what a function's type is, why functions are first-class objects, what it means to apply one, how to apply one partially, how to compose them, and how all of it comes together to process lists.
ModelFunction type and first-class objects
In functional programming a function is described by its type: the set its inputs are drawn from, the domain, and the set its outputs belong to, the co-domain. The type is written with an arrow, domain → co-domain. So isEven: integer → boolean reads 'isEven takes an integer and returns a boolean', and toUpper: char → char takes a character and returns a character. The domain and co-domain need not be the same, and either can itself be a complex type such as a list. Stating a function's type precisely is the functional programmer's equivalent of declaring a variable — it fixes what the function may consume and produce before you write a line of its body.
The idea that makes the whole paradigm tick is that a function is a first-class object: it is a value with the same rights as an integer or a string, meaning it can be stored in a variable, passed as an argument into another function, and returned as the result of a function. A function that takes or returns other functions is called a higher-order function. This is not a mere convenience — it is what lets you write map, filter and fold, each of which takes a function as an argument, and it is the mechanism behind partial application and composition in the blocks that follow. In an imperative language a function is a fixed lump of code; in a functional language it is a value you can pass around like any other.
Give the type of a function that returns the length of a list of characters. It consumes a list of characters and produces an integer, so its type is length: [char] → integer, where the square brackets denote 'list of'. Now consider a higher-order function such as map, whose type reveals its power: map: (a → b) → [a] → [b]. Read left to right, map takes a function of type (a → b) as its first argument, then a list of a-values, and produces a list of b-values. The very first thing in map's domain is another function — only possible because functions are first-class objects. Being able to write out a type like this, and say in words what each arrow means, is exactly what the exam asks for when it hands you an unfamiliar function.
ModelFunction application and partial application
Function application is simply the act of supplying a function with an argument to obtain a result. In functional notation you write the function name followed by its argument with no brackets required, so square 4 applies square to 4 and evaluates to 16, and isEven 7 evaluates to false. Application is the fundamental operation of the whole paradigm — where an imperative program runs statements in sequence, a functional program computes by applying functions to arguments and applying more functions to the results.
Functions of several arguments are, in most functional languages, handled by currying: a two-argument function is really a function that takes the first argument and returns a new function that takes the second. This is what makes partial function application possible — supplying only some of a function's arguments to produce a new, more specialised function of the remaining ones. Given a function add x y = x + y, applying it to a single argument, add 3, does not error; it returns a brand-new function that adds 3 to whatever it is later given. Partial application is a direct consequence of functions being first-class objects — a function has to be able to return a function for it to work — and it is the neat way functional programs build specialised tools out of general ones without repeating code.
Start with a general multiply function, multiply x y = x * y, whose type is multiply: integer → integer → integer. Full application supplies both arguments: multiply 6 7 evaluates to 42.
Now apply it partially. Writing multiply 2 supplies only the first argument, so instead of a number you get back a function — call it double — of type integer → integer that multiplies its input by 2. Apply that new function and it behaves as expected: double 5 evaluates to 10, and double 9 to 18. You have manufactured a specialised one-argument function out of a general two-argument one without writing any new logic. Likewise multiply 3 yields a treble function. This is the everyday use of partial application: fix the arguments that stay constant, and hand the resulting specialised function to something like map.
ModelComposition of functions
Composition combines two functions into one by feeding the output of the first into the input of the second. It is written with a small circle: (g ∘ f) means 'apply f first, then apply g to the result', so (g ∘ f)(x) = g(f(x)). The order is the classic trap — the function written on the right runs first, matching the way brackets nest in ordinary mathematics. Composition lets you build a complex transformation as a pipeline of simple, individually-tested functions, which is the essence of the functional style: small pure functions assembled, not large procedures written.
The types must line up for a composition to be valid. If f: A → B and g: B → C, then the co-domain of f (B) matches the domain of g (B), and the composition g ∘ f: A → C is well-typed, mapping an A straight to a C. If f produced a type that g could not consume, the composition would be meaningless — so checking that the arrow types meet in the middle is how you verify a composition is legal before you evaluate it. Because functions are first-class objects, composition itself can be treated as a higher-order function that takes two functions and returns a third, which is exactly how it is defined in a functional language.
Let addOne x = x + 1 (type integer → integer) and double x = x * 2 (type integer → integer). Compose them one way: (double ∘ addOne)(3) applies addOne first, giving 4, then double, giving 8. Compose them the other way: (addOne ∘ double)(3) applies double first, giving 6, then addOne, giving 7. Same two functions, different order, different answer — proof that composition is not commutative and that the right-hand function always runs first.
Now a type check on a mixed composition. Let len: [char] → integer and isEven: integer → boolean. The co-domain of len is integer, which is exactly the domain of isEven, so they compose: (isEven ∘ len): [char] → boolean, a single function that reports whether a string has an even number of characters. Applying it, (isEven ∘ len)('code') computes len('code') = 4, then isEven 4 = true. Had you tried len ∘ isEven the types would clash — isEven returns a boolean and len demands a list of characters — so that composition is rejected before it ever runs.
MechanismFunctional programs and list processing
A functional program is built almost entirely from function definitions and applications, and it deliberately avoids the machinery of imperative code. There is no assignment to mutable variables — a name, once bound, keeps its value — and therefore no side effects: a function's only job is to return a result. Where an imperative program uses a loop with a changing counter, a functional program uses recursion, a function defined in terms of itself with a base case that stops it. Everything is an expression that evaluates to a value rather than a statement that performs an action. These constraints are what give the paradigm its reliability, because a function that cannot alter anything outside itself is trivial to reason about and safe to run in parallel — the very property that let WhatsApp scale on Erlang.
The natural data structure of this world is the list. A list is either empty or an element joined to another list, so it is defined recursively, and it is taken apart the same way: the head is the first element and the tail is the list of everything after it, while prepend (construct) adds a new element to the front. On top of these sit the three higher-order list-processing functions that do the work of loops: map applies a function to every element and returns a new list of results; filter returns a new list of only the elements satisfying a test; and fold (reduce) collapses a whole list to a single value by repeatedly combining elements with a function and an accumulator. Each returns a new list rather than modifying the original, honouring immutability, and each takes a function as an argument, which is only possible because functions are first-class objects — the whole section closing on the idea it opened with.
Take the list [3, 1, 4, 1, 5, 9, 2, 6] and process it three ways. Decomposition first: its head is 3 and its tail is [1, 4, 1, 5, 9, 2, 6]; prepending 0 gives [0, 3, 1, 4, 1, 5, 9, 2, 6], leaving the original untouched.
Now the higher-order trio. map (multiply 2) [3, 1, 4, 1, 5, 9, 2, 6] — reusing the double function from earlier by partial application — returns [6, 2, 8, 2, 10, 18, 4, 12], every element transformed. filter isEven [3, 1, 4, 1, 5, 9, 2, 6] keeps only the even elements, returning [4, 2, 6]. And fold (+) 0 [3, 1, 4, 1, 5, 9, 2, 6] starts an accumulator at 0 and adds each element in turn — 0+3=3, +1=4, +4=8, +1=9, +5=14, +9=23, +2=25, +6=31 — collapsing the whole list to the single value 31. Three loops' worth of work, each expressed as one application of a higher-order function to a list and a function, with nothing anywhere mutated.
VocabularyKey terms the mark scheme pays for
TrapsMisconceptions that cost marks
ExamWhat examiners want
Functional programming is assessed on the written Paper 1 (7517/1), where the questions are precise and notation-heavy, so accuracy with the arrow notation is worth real marks. When asked for a function's type, write it as domain → co-domain and be exact about the types at each end — [char] → integer, not just 'a number' — and when a higher-order function is involved, remember the first part of its type is itself a bracketed function type, as in map: (a → b) → [a] → [b]. Practise reading such a type aloud, because 'explain what this function does' questions are answered straight from the type.
The two reliable traps are order and arguments. In composition, state explicitly that the right-hand function runs first and, if the marks are there, check that the co-domain of the first matches the domain of the second before evaluating — an examiner rewards the type check as well as the answer. In partial application, make clear that supplying fewer arguments returns a function, not an error, and show the specialised function you have created (multiply 2 becomes a doubling function). For list processing, be able to hand-evaluate map, filter and fold on a short list, showing each step — especially fold, where you should write out the running accumulator (0+3=3, +1=4, ...) because the method attracts the marks. Throughout, tie your reasoning back to first-class objects, immutability and no side effects: these three ideas underpin every other concept in the section, and naming them in an explanation is what lifts an answer from describing what the code does to explaining why the paradigm works.