Mathematical Notation

Sequence Notation in Code

In this class, we use mathematical notation for sequences, sets and tables (mappings) in the code that will be given in class and in the lecture notes. The notation has a natural translation to our SML library. Here is the translation for sequences.

Sequence Notation Equivalent SML with SEQUENCE library
\[S_i\] nth S i
\[|S|\]length S
\[\langle \; \rangle\]empty()
\[\langle v \rangle\]singleton v
\[\langle i, \ldots, j \rangle\]tabulate (fn k => i + k) (j - i + 1)
\[S \langle i, \ldots, j \rangle\]subseq S (i, j - i + 1)
\[\langle e : p \in S \rangle\]map (fn p => e) S
\[\langle e : 0 \leq i < n \rangle\]tabulate (fn i => e)
\[\langle p \in S \;|\; e \rangle\]filter (fn p => e) S
\[\langle e_1 : p \in S \;|\; e_2\rangle\]map (fn p => e1) (filter (fn p => e2) S)
\[\langle e : p_1 \in S_1,\; p_2 \in S_2 \rangle\]flatten(map (fn p1 => map (fn p2 => e) S2) S1)
\[\langle e : 0 \leq i < n,\; 0 \leq j < i \rangle\]flatten(tabulate (fn i => tabulate (fn j => e) i) n)
\[\sum_{p \in S} e\]reduce add 0 (map (fn p => e) S)
\[\sum_{i = k}^n e\]reduce add 0 (map (fn i => e) $\langle k, \ldots, n\rangle$)

The meaning of add and 0 in the reduce will depend on the type (e.g. Int.+ and 0 for integers or Real.+ and 0.0 for reals). Also the $\sum$ can be replaced with $\min$, $\max$, $\cup$ and $\cap$ with the presumed meanings. For example \[\bigcup_{p \in S} e\] translates to: reduce Set.union Set.empty (map (fn p => e) S).

Set and Table Notation in Code

A listing that includes sets and tables can be found here.