First-Class and Higher-Order Functions

Two of the most important ideas in functional programming are first-class functions and higher-order functions. They are easy to confuse — and AQA examiners deliberately test whether you can tell them apart — so this lesson defines each precisely, shows the function type signatures that make Haskell's treatment of functions explicit, and works through traced examples. Everything that follows in the topic (map, filter, fold, composition, currying) depends on these two foundations.

---

Spec Mapping

This lesson covers AQA 7517 §4.12.2 Writing functional programs, focusing on the ideas that functions are first-class objects and that higher-order functions take other functions as arguments and/or return functions as results. You must be able to define both terms, give examples, read and write function type signatures in Haskell (including the higher-order signatures with bracketed function arguments), and explain why the abstraction is useful. It is the direct prerequisite for §4.12.3 (map, filter, fold), for function composition and partial application, and it draws on the paradigm characteristics of §4.12.1.

Descriptions here are our own restatement of the assessable content, not a verbatim quotation of AQA's specification.

---

First-Class Functions

A language has first-class functions (equivalently, functions are first-class objects or first-class citizens) when a function can be used anywhere any other value can be used. Concretely, a first-class function can be:

1. Bound to a name (assigned to a variable).
2. Passed as an argument to another function.
3. Returned as the result of another function.
4. Stored in a data structure (a list, tuple, map, etc.).

The litmus test is simple: can I treat this function exactly like I treat an Int or a String? In Haskell the answer is always yes — all functions are first-class by default. The term "first-class" is historical: in some older languages functions were "second-class", meaning you could call them but not pass them around or store them, which made higher-order programming impossible. Granting functions the same rights as ordinary values is what "first-class" celebrates, and it is the single most important enabling feature of the whole functional paradigm.

First-class functions in Haskell

-- 1. Bound to a name (a function value stored under 'double')
double :: Int -> Int
double = (*2)

-- 2. Passed as an argument
applyFunc :: (Int -> Int) -> Int -> Int
applyFunc f x = f x
applyFunc double 5      -- 10

-- 3. Returned as a result
makeAdder :: Int -> (Int -> Int)
makeAdder n = (+ n)
addFive = makeAdder 5
addFive 3               -- 8

-- 4. Stored in a list (a list whose ELEMENTS are functions)
ops :: [Int -> Int]
ops = [double, (+1), (^2)]
map (\f -> f 4) ops     -- [8, 5, 16]

Look carefully at ops :: [Int -> Int] — its type is "a list of functions from Int to Int". The fact that a function type can sit inside a list type is exactly what "first-class" means.

The same ideas in Python (imperative contrast)

# 1. Bind a function to a name
def greet(name):
    return f"Hello, {name}!"
say_hello = greet
print(say_hello("Alice"))      # Hello, Alice!

# 3. Return a function from a function
def make_multiplier(factor):
    def multiplier(x):
        return x * factor
    return multiplier
triple = make_multiplier(3)
print(triple(5))               # 15

# 4. Store functions in a list
operations = [say_hello, str.upper]

Python supports first-class functions too, which is why functional techniques work there — but Haskell is built around them from the ground up.

---

Function Type Signatures (read these carefully)

Because Haskell makes types explicit, you can see whether a function is higher-order just by reading its signature. The rules:

• -> separates argument types from the return type and associates to the right.
• A pair of brackets around an arrow means "a function is expected here".

Signature	Reading
Int -> Int	takes an Int, returns an Int (first-order)
Int -> Int -> Int	really Int -> (Int -> Int): takes an Int, returns a function
(Int -> Int) -> Int -> Int	takes a function and an Int, returns an Int (higher-order: argument is a function)
Int -> (Int -> Int)	takes an Int, returns a function (higher-order: result is a function)
(a -> b) -> [a] -> [b]	the type of map: a function plus a list, giving a list

The bracketed function type is the visual signature of a higher-order function — train your eye to spot it.

---

Higher-Order Functions

A higher-order function (HOF) is a function that does at least one of the following:

1. Takes one or more functions as arguments, and/or
2. Returns a function as its result.

A function that does neither (it only takes and returns ordinary values) is called first-order. HOFs are powerful because they let you abstract a pattern of computation and supply the varying part — the per-element operation, the test, the combining rule — as a function argument.

Higher-order function	What it abstracts
map	"do this to every element"
filter	"keep the elements satisfying this test (predicate)"
foldr / foldl	"combine all elements using this rule"
sortBy	"order elements using this comparison"

map — taking a function as an argument

-- map :: (a -> b) -> [a] -> [b]
squared = map (^2) [1, 2, 3, 4, 5]
-- squared = [1, 4, 9, 16, 25]

Here map is higher-order because its first argument, (^2), is itself a function.

filter — taking a predicate

-- filter :: (a -> Bool) -> [a] -> [a]
evens = filter even [1..10]
-- evens = [2, 4, 6, 8, 10]

even :: Int -> Bool is a predicate — a function returning a Boolean — and filter keeps every element for which the predicate is True.

makeAdder — returning a function

-- makeAdder :: Int -> (Int -> Int)
makeAdder n = \x -> x + n

addTen = makeAdder 10    -- addTen is itself a function, Int -> Int
addTen 5                 -- 15

makeAdder is higher-order in the second sense: applying it to 10 returns a new function.

Function factories and closures

When a function returns a function, the returned function often "remembers" the value it was built with. makeAdder 10 returns a function that has captured n = 10; makeAdder 3 returns a different function that captured n = 3. The captured environment is called a closure. This is the mechanism behind "function factories" — higher-order functions whose job is to manufacture specialised functions:

-- A factory that builds "multiply by k" functions
multiplyBy :: Int -> (Int -> Int)
multiplyBy k = \x -> x * k

double = multiplyBy 2     -- closure capturing k = 2
treble = multiplyBy 3     -- closure capturing k = 3
double 6                  -- 12
treble 6                  -- 18

Both double and treble come from the same definition; they differ only in the value each closed over. Closures are why returning functions is genuinely useful rather than a curiosity — they let one general definition spawn a whole family of related functions.

A higher-order function that does both

A single function can take a function and return one. Consider twice, which takes a function and returns a new function that applies it two times:

twice :: (a -> a) -> (a -> a)
twice f = \x -> f (f x)

quadruple = twice (*2)    -- returns a function that doubles, twice
quadruple 5               -- 20

Here twice (*2) returns the function quadruple, which itself took (*2) — both senses of "higher-order" in one definition. Note the signature (a -> a) -> (a -> a): a function in, a function out.

---

First-Class vs Higher-Order — Don't Confuse Them

This distinction is a classic exam trap.

Concept	What it describes	Whose property is it?
First-class functions	Functions are values — assignable, passable, returnable, storable	A property of the language
Higher-order functions	A function that takes or returns functions	A property of a particular function

The relationship is one-directional: first-class functions are a prerequisite for higher-order functions. You cannot pass (^2) to map unless functions can be passed as arguments in the first place. But the reverse does not hold — simply binding a function to a name (double = (*2)) uses first-class functions yet involves no higher-order function at all. In short: every HOF relies on first-class functions, but not every use of a first-class function is a HOF.

---

Lambda Expressions (Anonymous Functions)

A lambda expression is a function written without giving it a name. Lambdas are ideal as the throwaway function argument to a HOF when defining a separate named function would be overkill.

-- Named function...
square x = x * x

-- ...and the equivalent lambda
square' = \x -> x * x

-- Used inline with a higher-order function (no name needed)
result = map (\x -> x * x + 1) [1, 2, 3, 4, 5]
-- result = [2, 5, 10, 17, 26]

# Python's lambda keyword does the same job
result = list(map(lambda x: x * x + 1, [1, 2, 3, 4, 5]))

The backslash \x -> is Haskell's lambda syntax, echoing the λx. of lambda calculus (§4.12.1).

Named function or lambda — which to use?

Both define a function, so when should you prefer each? Use a named function when the logic is non-trivial, reused in several places, or benefits from a descriptive name and an explicit type signature — names document intent and aid debugging. Use a lambda when the function is short, used only once, and passed directly to a higher-order function, where inventing a separate name would only add noise. For example map (\x -> x * x + 1) xs is clearer inline than defining a one-line f elsewhere, whereas a complex tax calculation deserves a named, typed, testable function. A lambda that grows beyond a line, or that you find yourself copying, is a signal to promote it to a named definition.

---

Worked Example — applyTwice Traced

Task: write a higher-order function applyTwice that takes a function f and a value x and applies f to x twice.

applyTwice :: (a -> a) -> a -> a
applyTwice f x = f (f x)

applyTwice (+3) 10     -- ?
applyTwice (*2) 5      -- ?

Note the signature (a -> a) -> a -> a: the bracketed (a -> a) is the function argument, confirming this is higher-order. Now trace the evaluation by substitution:

  applyTwice (+3) 10
= (+3) ((+3) 10)        -- substitute f = (+3), x = 10
= (+3) 13               -- inner (+3) 10 reduces to 13
= 16

  applyTwice (*2) 5
= (*2) ((*2) 5)
= (*2) 10
= 20

Because f is supplied at call time, the one definition of applyTwice works for adding, doubling, or any other a -> a function — that reuse is the whole point of higher-order functions.

---

Implementing a Higher-Order Function from Scratch

Higher-order functions are not built-in magic; you can define your own, and seeing how clarifies what map and filter really do. Both are written by recursion over a list (covered fully in the recursion lesson), and both take a function as their first argument — which is exactly what makes them higher-order.

-- our own map: apply f to the head, recurse on the tail
myMap :: (a -> b) -> [a] -> [b]
myMap _ []     = []
myMap f (x:xs) = f x : myMap f xs

-- our own filter: keep the head only if the predicate holds
myFilter :: (a -> Bool) -> [a] -> [a]
myFilter _ []     = []
myFilter p (x:xs)
    | p x       = x : myFilter p xs
    | otherwise = myFilter p xs

Now define a brand-new HOF of our own, applyN, which applies a function n times:

applyN :: Int -> (a -> a) -> a -> a
applyN 0 _ x = x                        -- base case: zero applications
applyN n f x = f (applyN (n - 1) f x)   -- apply f to the (n-1)-fold result

Trace applyN 3 (*2) 1 — "double 1, three times":

  applyN 3 (*2) 1
= (*2) (applyN 2 (*2) 1)
= (*2) ((*2) (applyN 1 (*2) 1))
= (*2) ((*2) ((*2) (applyN 0 (*2) 1)))
= (*2) ((*2) ((*2) 1))     -- base case returns x = 1
= (*2) ((*2) 2)
= (*2) 4
= 8

The function argument f threads all the way through the recursion untouched — passing a function as a parameter is no different in principle from passing a number, which is precisely the freedom that first-class functions give you.

---

Higher-Order Functions in the Real World

HOFs are not an academic flourish; they are everywhere in production code, and the AQA specification expects you to recognise practical uses.

Sorting with a custom ordering

A sort function that takes a comparison or key function is higher-order — you supply the rule, the library does the ordering:

import Data.List (sortBy)
import Data.Ord (comparing)

students = [("Alice", 85), ("Bob", 92), ("Carol", 78)]
-- sort by the score (second element), highest first
ranked = sortBy (comparing (negate . snd)) students
-- [("Bob",92), ("Alice",85), ("Carol",78)]

# The same idea in Python: sorted takes a key function (a HOF)
students = [("Alice", 85), ("Bob", 92), ("Carol", 78)]
ranked = sorted(students, key=lambda s: s[1], reverse=True)