Higher-Order Functions

A higher-order function (Def 1.23, slides p.209) is one that takes a function as an argument or returns a function as its result. Functions in SML are first-class values — they can be stored, passed, and returned just like ints or strings.

Examples of taking functions as arguments:
- map applies a function to every element of a list.
- filter keeps only elements satisfying a predicate.

Examples of returning functions:
- fn x => fn y => x + y takes x and returns a function that adds x to its argument. (This is currying.)
- fn k => fn _ => k takes k and returns a constant function.

Composition: the central idea is that we build new behavior by plugging functions together. map f is a function; filter p is a function; map f (filter p xs) chains them. This is the functional analogue of pipes.

Example — define map ourselves:

Test: mymap (fn x => x + 1, [10, 20, 30]) = [11, 21, 31].

A function can be written in two equivalent ways:

• Cartesian form: takes all arguments in one tuple. f(x, y) = x + y.
• Cascaded form: returns a function expecting the next argument. f x = fn y => x + y.

In SML, the cascaded form is the default since functions are curried. The cascaded form f x y is sugar for (f x) y. The cartesian form needs an explicit tuple: f (x, y).

Bracket elision rules (Def 1.26):
1. Application associates left: f a b c = ((f a) b) c.
2. Arrow -> associates right: a -> b -> c -> d = a -> (b -> (c -> d)).

These two rules together mean fn x => fn y => fn z => x + y + z can be written as the cascaded fn x => fn y => fn z => x + y + z and called as f 1 2 3.

The standard higher-order list functions can be re-implemented as my* functions for understanding:

Patterns:
- myexists p l returns true if at least one element of l satisfies p.
- myforall p l returns true if every element of l satisfies p.
- myfilter p l returns the sublist of elements satisfying p.

Order of recursion matters: all three traverse left-to-right. myexists short-circuits on the first true (good); myforall short-circuits on the first false (good); myfilter cannot short-circuit (must visit all elements to find the ones that pass).

Used in assignments 4.4 and 4.5.
- Assignment 4.4: define divisible d n (uses mod), then nextPrime n, then primes n (uses myexists).
- Assignment 4.5: implement myfilter, myexists, myforall.

Cascaded application. myexists (fn x => x > 5) [3, 7, 2]:
- $p(3) = (3 > 5) = \text{false}$. Continue.
- $p(7) = (7 > 5) = \text{true}$. Return true. ✓

SML's standard basis library provides List.nth and List.length. They can be re-implemented:

List.nth n l returns the $n$-th element of $l$ (0-indexed). Raises Subscript if $n \geq \text{length}(l)$.

List.length is identical to our length (built-in in the playground as length).

Used in assignment 4.8 for permutations: nth i perm accesses the i-th element of a permutation.

Lemma 6.3. A binary relation $R \subseteq A \times B$ can be viewed as a function $R: A \to \mathcal{P}(B)$ defined by $R(a) := \{b \in B \mid (a,b) \in R\}$.

Proof. The definition $R(a) := \{b \in B \mid (a,b) \in R\}$ is well-formed: for each $a \in A$ it produces a unique subset of $B$. Hence $R$ is a (total) function $A \to \mathcal{P}(B)$. Conversely, given any function $f: A \to \mathcal{P}(B)$, the relation $\{(a, b) \mid b \in f(a)\} \subseteq A \times B$ reconstructs $f$. So relations and $A \to \mathcal{P}(B)$ functions are equivalent representations. $\square$

Use. This view lets us apply functional concepts to relations: composition, identity, inverse.