Higher-order Functions and Set Theory

Higher-order function (HOF) is a type of nested function that offers a higher level of abstraction than ordinary functions, where instead of taking primitives or variables as arguments (parameters) and outputting objects, functions are taken in and output by HOFs.

The subtleties between a function composition and HOF can be shown through the syntax of Python, which can result in different behaviours depending on how we close the parentheses.

A classic example is demonstrated as follows.

def thrice(f):
    return lambda x: f(f(f(x)))

add1 = lambda x: x + 1

x = thrice(thrice(add1))(0) # 9
y = thrice(thrice)(add1)(0) # 27

In the example above, x will output 9 because the defining line of code is interpreted ‘right-to-left’ (like function composition), first composing the add1 function thrice to produce a function equivalent to lambda x: x + 3, then composing the first output thrice to produce a function equivalent to lambda x: x + 9, thus 0 + 9 = 9.

As for y, it will output 27 because it is defined ‘left-to-right’, first composing the thrice function itself three times, resulting in an HOF that effectively composes an input function \(3^3=27\) times, which then takes in the function add1 to produce a function equivalent to lambda x: x + 27, and finally we get 0 + 27 = 27.

Higher-order functions are closely related to mathematics, in the sense that they enable the implementation of operators in mathematics, as well as a family of functions, using code.

For example¹, in set theory, we can define a family of functions \(F\), which itself is also considered a function from \(\mathbb{N}^{\mathbb{N}}\) to \(\mathbb{N}^{\mathbb{N}}\). This operator \(F\) takes in a function \(f : \mathbb{N} \to \mathbb{N}\) and outputs another function \(F(f) : \mathbb{N} \to \mathbb{N}\) that takes in whatever \(f\) takes in and outputs whatever \(f\) outputs plus one.

Phrased in a set-theoretic language as ‘pure’ as possible, \(F\) is defined as \[F=\{(f,\{(n,f(n)+1) : n \in \mathbb{N}\}) : f \in \mathbb{N}^{\mathbb{N}}\}.\]

An HOF implementation of \(F\) in Python can then look like the following:

# The following type hints are to indicate that the functions are in N^N, and are unnecessary for practical purposes.
from typing import Annotated, Callable
from annotated_types import Ge # requires additional pip install: https://pypi.org/project/annotated-types/

def F(f: Callable[Annotated[int, Ge(0)], Annotated[int, Ge(0)]]) -> Callable[Annotated[int, Ge(0)], Annotated[int, Ge(0)]]:
    def output(n: Annotated[int, Ge(0)]) -> Annotated[int, Ge(0)]:
        return f(n) + 1
    return output

f = lambda x: x + 1
F(f)(0) # 2