Задача, с которой часто приходится сталкиваться программисту — обработка последовательно поступающих данных. Примерами подобных вычислений являются подсчёт суммы последовательности чисел, поиск максимального или минимального числа, среднего арифметического. В этой главе мы рассмотрим общий подход к решению таких задач.

Пространство последовательностей

Пусть $X$ — некоторое множество. Назовём $n$ -элементной последовательностью над множеством $X$ упорядоченный набор $ω = 〈x_{1}, x_{2}, \dots, x_{n}〉$ , $x_{i} \in X$ . Формально выражаясь, последовательностью над $X$ является отображение из множества первых $n$ натуральных чисел $\{1, 2, \dots, n\}$ в $X$ : каждому числу $i$ ставится в соответствие некоторый элемент $x_{i}$ множества $X$ . При $n = 0$ получается пустая последовательность $〈〉$ , заслуживающая такого же внимания, как и непустые. Последовательности над множеством иногда называют также цепочками.

Обозначим множество последовательностей над $X$ как $Ω (X)$ .

Из последовательности $ω = 〈x_{1}, x_{2}, \dots, x_{n}〉 \in Ω (X)$ и элемента $x \in X$ можно сконструировать новую последовательность $ω ∟ x = 〈x_{1}, x_{2}, \dots, x_{n}, x〉$ . Операция удлинения $∟$ отображает декартово произведение $Ω (X) \times X$ в $Ω (X)$ , добавляя в конец последовательности $ω$ новый элемент $x$ . Любая последовательность может быть построена путём многократного удлинения пустой последовательности: $〈x_{1}, x_{2}, \dots, x_{n}〉 = 〈〉 ∟ x_{1} ∟ x_{2} ∟ \dots ∟ x_{n}$ (мы не стали злоупотреблять скобками, предполагая, что операция удлинения левоассоциативна, то есть группируется слева направо).


Несколько примеров		Индуктивные функции на пространстве последовательностей

Глава 21. Индуктивные вычисления

Пространство последовательностей