Lists and Tuples

Lists and tuples are SML's main ways to group values.

Tuples have a fixed length; each component can have a different type.
val p = (1, "one", true);
The type is int * string * bool. Access components with pattern matching:
val (n, s, b) = p; binds n=1, s="one", b=true.

Lists have arbitrary length; all elements must share one type. Per Def 1.12 (slides p.211), lists have two constructors:
- nil (written []) — the empty list.
- :: (pronounced "cons") — prepends one element to a list.

So [1, 2, 3] is sugar for 1 :: 2 :: 3 :: []. The list [1, 2, 3] has type int list; [1, "a"] is a TYPE ERROR because int and string differ.

Pattern matching (Def 1.6) lets you destructure structured values:
val (x, _) = (10, 20); binds x = 10; the _ is an anonymous variable (Def 1.8) — we don't care about that component. This is the foundation for the case expression we'll use on lists and datatypes.

The set of all functions from set $A$ to set $B$ is itself a set, written $A \to B$ or $B^A$. We can apply set operations to function spaces: $|B^A| = |B|^{|A|}$.

Examples:
- $\mathbb{B}^{\mathbb{B}}$ is the set of all boolean functions of one boolean argument. There are $2^2 = 4$ such functions (constant true, constant false, identity, negation).
- $\mathbb{N} \to \mathbb{N}$ is the set of all sequences of naturals.

An indexed family is a set indexed by another set: $\{a_i\}_{i \in I}$ where $I$ is the index set. The order is irrelevant — what matters is the function $i \mapsto a_i$.

Examples:
- The rows of a database table: indexed by row id.
- The coefficients of a polynomial: $p(x) = \sum_{i=0}^n a_i x^i$ — coefficients $\{a_0, a_1, \ldots, a_n\}$ indexed by $\{0, 1, \ldots, n\}$.
- The pages of a book: indexed by page numbers.

The indexed family is a function from the index set $I$ to the value set: $a: I \to V$ with $a(i) = a_i$.

A k-ary relation on sets $A_1, \ldots, A_k$ is a subset of $A_1 \times A_2 \times \cdots \times A_k$. So:
- Binary relation: $R \subseteq A \times B$ (the usual case).
- Ternary relation: $R \subseteq A \times B \times C$ (e.g. 'between': $b$ is between $a$ and $c$).
- k-ary: $R \subseteq A_1 \times \cdots \times A_k$.

A k-ary function $f: A_1 \times \cdots \times A_k \to B$ takes $k$ arguments and returns one value. Equivalently, $f$ corresponds to a (k+1)-ary relation $\{((a_1,\ldots,a_k), f(a_1,\ldots,a_k)) \mid (a_1,\ldots,a_k) \in A_1 \times \cdots \times A_k\}$.