Recursion

A function is recursive when it calls itself (Def 1.17). Recursion is how SML expresses loops and iteration.

Every well-formed recursive function has two parts:
1. Base case(s) — handle the smallest input directly, without recursion.
2. Recursive case(s) — handle larger inputs by calling the function on a smaller sub-piece.

Example — length of a list:

Base case: empty list has length 0. Recursive case: a non-empty list has length 1 plus the length of its tail.

Example — sum of a list:

Example — factorial (n!):

Tail calls (Def 1.37, slides p.227): when the recursive call is the LAST thing the function does, modern compilers optimize it into a loop. So tail-recursive functions are as efficient as for-loops. Compare:
fun sum (h :: t) = h + sum t; — NOT tail-recursive (the + happens after the recursive call returns).
fun sum_tr nil acc = acc | sum_tr (h :: t) acc = sum_tr t (acc + h); — tail-recursive with an accumulator.

Theorem. $f: A \to B$ is bijective if and only if it has an inverse $f^{-1}: B \to A$ with $f^{-1}(f(a)) = a$ and $f(f^{-1}(b)) = b$ for all $a \in A, b \in B$.

Proof. ($\Rightarrow$) Assume $f$ is bijective.
- Injectivity: for each $b \in B$, there is at most one $a$ with $f(a) = b$.
- Surjectivity: for each $b \in B$, there is at least one $a$ with $f(a) = b$.
- Combined: there is exactly one $a$ per $b$. Define $f^{-1}(b)$ to be that $a$.
- Then $f^{-1}(f(a)) = a$ (by definition) and $f(f^{-1}(b)) = b$ (also by definition). ✓

($\Leftarrow$) Assume $f^{-1}$ exists with both composition identities.
- Injectivity: if $f(a_1) = f(a_2) = b$, then $a_1 = f^{-1}(b) = a_2$. ✓
- Surjectivity: for any $b \in B$, let $a = f^{-1}(b)$. Then $f(a) = b$. ✓

So $f$ is bijective. $\square$

The fold (or reduce) operator collapses a list into a single value by repeatedly combining adjacent elements. For binary operation $\oplus$ with identity $e$:
- $\text{fold}_\oplus([x_1, x_2, \ldots, x_n]) = (\cdots((e \oplus x_1) \oplus x_2) \oplus \cdots \oplus x_n)$

Examples:
- $\text{fold}_+([1,2,3,4]) = 10$ (sum).
- $\text{fold}_\times([1,2,3,4]) = 24$ (product).
- $\text{fold}_\wedge([T,T,F]) = F$ (AND).
- $\text{fold}_\vee([F,T,F]) = T$ (OR).

In SML this is foldl and foldr (with the difference being association order).