Определители списков и математические последовательности

Пожалуй, Haskell — это единственный язык программирования, который позволяет прос­то и быстро конструировать списки, основанные на какой-нибудь простой ма­те­ма­ти­чес­кой формуле. Этот подход уже был использован при построении функции быстрой сор­тировки списка методом Хоара (см. пример 1.2 в лекции 1). Наиболее общий вид оп­ре­де­ли­телей списков выглядит так:

[ x | x <- xs ]

Эта запись может быть прочитана как "Список из всех таких x, взятых из xs". Струк­тура "x ¬ xs" называется генератором. После такого генератора (он должен быть один и сто­ять первым в записи определителя списка) может стоять некоторое число выражений ох­раны, разделённых запятыми. В этом случае выбираются все такие x, значения всех вы­ра­жений охраны на которых истинно. Т.е. запись:

[ x | x <- xs, x > m, x < n ]

Можно прочитать как "Список из всех таких x, взятых из xs, что (x больше m) И (x мень­ше n)".

Другой важной особенностью Haskell’а является простая возможность формирования бес­конечных списков и структур данных. Бесконечные списки можно формировать как на ос­нове определителей списков, так и с помощью специальной нотации. Например, ниже по­казан бесконечный список, состоящий из последовательности натуральных чисел. Вто­рой список представляет бесконечную последовательность нечётных натуральных чисел:

[1, 2 ..]

[1, 3 ..]

При помощи двух точек можно также определять любую арифметическую прогрессию, как конечную, так и бесконечную. Если последовательность конечна, то в ней задаются пер­вый и последний элементы. Разность арифметической прогрессии вычисляется на ос­но­ве первого и второго заданного элементов — в приведенных выше примерах разность в пер­вой прогрессии равна 1, а во второй — 2. Т.е. чтобы определить список всех нечётных на­туральных чисел вплоть до 10, необходимо записать: [1, 3 .. 10]. Результатом будет спи­сок [1, 3, 5, 7, 9].

Бесконечные структуры данных можно определять на основе бесконечных списков, а мож­но использовать механизм рекурсии. Рекурсия в данном случае используется как об­ра­щение к рекурсивным функциям. Третий способ создания бесконечных структур дан­ных состоит в использовании бесконечных типов.

Пример 4.1. Определение типа для представления двоичных деревьев.

data Tree a = Leaf a

| Branch (Tree a) (Tree a)

Branch :: Tree a -> Tree a -> Tree a

Leaf :: a -> Tree a

В этом примере показан способ определения бесконечного типа. Видно, что без ре­кур­сии тут не обошлось. Однако если нет необходимости создавать новый тип данных, бес­ко­неч­ную структуру можно получить при помощи функций:

ones = 1 : ones

numbersFrom n = n : numberFrom (n + 1)

squares = map (^2) (numbersFrom 0)

Первая функция определяет бесконечную последовательность, полностью состоящую из единиц. Вторая функция возвращает последовательность целых чисел, начиная с за­дан­но­го. Третья возвращает бесконечную последовательность квадратов натуральных чисел вмес­те с нулем.