Задача, с которой часто приходится сталкиваться программисту — обработка последовательно поступающих данных. Примерами подобных вычислений являются подсчёт суммы последовательности чисел, поиск максимального или минимального числа, среднего арифметического. В этой главе мы рассмотрим общий подход к решению таких задач.
Пусть — некоторое множество. Назовём -элементной последовательностью над множеством упорядоченный набор , . Формально выражаясь, последовательностью над является отображение из множества первых натуральных чисел в : каждому числу ставится в соответствие некоторый элемент множества . При получается пустая последовательность , заслуживающая такого же внимания, как и непустые. Последовательности над множеством иногда называют также цепочками.
Обозначим множество последовательностей над как .
Из последовательности и элемента можно сконструировать новую последовательность . Операция удлинения отображает декартово произведение в , добавляя в конец последовательности новый элемент . Любая последовательность может быть построена путём многократного удлинения пустой последовательности: (мы не стали злоупотреблять скобками, предполагая, что операция удлинения левоассоциативна, то есть группируется слева направо).