First-class functions, composition and folds

By UK A Level Computer Science · independent study · myAudience

Original textbook concept plate generated with OpenAI imagegen; labels and states checked against the lesson model. · Generated original teaching artwork; pending operator rights/provenance review before publication.

First-class functions, composition and folds

A mathematical function assigns one output to each input in its domain. In f:A→B, A is the domain and B the codomain; the image consists of outputs actually obtained and may be a proper subset of B. A pure program function models this idea when its output depends only on its input and it does not mutate external state. A function that reads a clock or changes a global counter has extra dependencies and effects, even if its syntax begins with def. Functional programming emphasises function application, immutable data and explicit transformations rather than a sequence of shared-state updates.

A first-class value can be bound to a name, passed as an argument and returned as a result. Python functions have these capabilities. offset_by(3) returns a function that maps x to x+3; the returned function captures delta in its enclosing scope. A higher-order function takes a function argument or returns a function, so offset_by and compose are higher-order. Calling the returned function is different from constructing it. The captured binding is not a prediction about all closures being pure: a closure can capture mutable state and produce effects.

For add:integer×integer→integer, supplying two arguments as a pair is one view of application. A curried view uses integer→(integer→integer): applying the first integer produces a function expecting the second. Partial application fixes some arguments without yet supplying all of them. Python's ordinary two-argument functions are not automatically curried; offset_by deliberately constructs the one-argument result. Our example covers the idea, while formal one-, two- and three-argument partial-application notation still needs further practice.

Composition connects compatible functions. If f:A→B and g:B→C, then g∘f:A→C applies f first and g second. For f(x)=x+3 and g(x)=2x, g∘f(x)=2x+6, while f∘g(x)=2x+3; order matters. The intermediate outputs of f must be accepted by g. If f returns a possibly empty string and g parses a positive integer, the apparent composition has a domain mismatch unless it filters, validates or exposes failure. Types and value-domain assumptions are therefore useful when assembling pipelines.

map transforms each input, filter retains inputs satisfying a predicate, and a fold combines a sequence using an accumulator and an initial value. Our reading pipeline filters negative values, maps x to 2x+1 and folds with addition starting at zero. The explicit zero gives a meaningful empty-input result. Fold order matters for non-associative operations such as subtraction; parallel regrouping is valid only under suitable algebraic and effect assumptions. Python map/filter are lazy iterators, not automatically materialised lists. The pipeline takes Θ(n) time and O(1) auxiliary iterator/accumulator words under a bounded-integer cost model, without promising constant bit storage for an unbounded sum.

A functional list can be viewed as a head element and a tail list. For [4,8,1], the head is 4 and the tail is [8,1]; for a singleton [4], the tail is empty. Accessing the head of an empty list requires a defined failure or optional result. Python slicing makes a new outer list, so returning values[1:] costs O(n), unlike a persistent linked-list tail reference. Programming paradigms do not erase representation costs. Immutable inputs and pure transformations can simplify distributed reasoning, but they alone do not guarantee efficient distribution, fault tolerance or freedom from every error.

Reading the diagram: The top pipeline retains [3,0,5], maps it to [7,1,11], then folds with zero to 19; it does not mutate the original [-2,3,0,5]. The lower paths apply the rightmost function first: g∘f sends 4 to 7 to 14, while f∘g sends 4 to 8 to 11. The arrows represent application order rather than storage ownership. Regrouping a fold would need its own associativity/effect assumptions, and this integer-addition picture does not justify arbitrary floating-point regrouping.

Runnable original Python 3, independently executed on Python the related topic. Read the stated input contract before running. These examples use fictional data and are teaching models, not production services.

```python
def offset_by(delta):
"""Return a first-class pure function adding the captured integer delta."""
return lambda value: value + delta

def compose(after, before):
"""Compose compatible pure functions: result(x) = after(before(x))."""
return lambda value: after(before(value))

def reading_pipeline(values):
"""Filter nonnegative integer readings, map x to 2x+1, fold by addition."""
from functools import reduce
selected = filter(lambda value: value >= 0, values)
mapped = map(lambda value: 2 * value + 1, selected)
return reduce(lambda total, value: total + value, mapped, 0)
```

Worked example: Apply reading_pipeline to [−2,3,0,5], then compare two compositions at input 4.

Filtering retains [3,0,5]; mapping x to 2x+1 yields [7,1,11].

Folding addition with initial zero gives 0+7+1+11=19. No input list element is mutated.

With f(x)=x+3 and g(x)=2x, g(f(4))=14 while f(g(4))=11. Constructing compose(g,f) creates a callable; applying it to 4 computes 14.

Answer: Pipeline result=19; g∘f(4)=14 and f∘g(4)=11.

Check your understanding: 1. What is the result on [] or [−3,−1]? 2. Give the head and tail of [9]. 3. Why can a subtraction fold not be regrouped like addition? Show a counterexample and state another practical assumption needed even for addition.

Answer: 1. Both yield zero through the explicit initial accumulator. 2. Head=9 and tail=[]. 3. (10−3)−2=5 differs from 10−(3−2)=9, so subtraction is not associative. Even addition needs an appropriate value model: real floating-point addition is not perfectly associative because of rounding. Parallel regrouping also assumes pure operations without order-dependent effects.

Why: First-class describes how values can be used; it does not mean the first function called. Domain and codomain are not the same as actual image. Composition applies the right-hand function first. A functional style cannot justify ignoring integer bit growth, list copying or floating-point rounding.