Главная » Haskell » Определители списков

0

В языке Haskell имеется возможность просто и быстро конструировать списки, основанные на какой-нибудь простой математической формуле. Для этих целей используется технология, которая известна как определители списков. При помощи неё можно определять самые незаурядные последовательности, выраженные посредством списков. К таким последовательностям относятся как числовые ряды, основанные на какой-либо математической формуле, так и списки значений произвольных типов.

Наиболее общий вид определителей списков выглядит следующим образом:

[x | x  < xs]

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

[x  |  x  < xs, x  >  m,

x  < n]

можно  прочитать  как  «список  из  всех  таких   x,   взятых  из   списка  xs, что (x строго больше m) и (x строго меньше n)».

могут использоваться для создания списков из более сложных структур данных, нежели простые значения. Для этого можно использовать столько образцов, сколько требуется, и таких типов, которые требуются для решения задачи. Например:

[(x,  y)  |  x  < xs, y  < ys, x  <=  y]

Эта запись читается так:  «список пар из всех элементов  списков xs и ys, при этом первый элемент пары должен быть не больше второго элемента». Как  видно, дело это несложное.

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

primes  = [x | x  < [2..], isPrime  x]

where

isPrime x  = (dividers x  == [1, x])

dividers x  = [y | y  < [1..x],

x  ‘mod‘  y  == 0]

Функция primes возвращает список всех таких натуральных x, то есть взятых из множества натуральных чисел [2..] (единица выкинута из этого множества, так как она не является простым числом по определению), при этом на каждом таком значении x предикат isPrime должен давать истинное значение. Этот предикат возвращает значение  «ИСТИНА»  только для простых чисел, поскольку сравнивает список делителей заданного числа со списком, состоящим из значения «1» и самого числа, и если в полном соответствии с определением он равен такому списку, то предикат возвращает значение «ИСТИНА».  В противном случае он возвращает значение «ЛОЖЬ».

Список делителей заданного числа вычисляется опять же при помощи технологии создания определителя списка. В список делителей заданного числа входят все такие числа, меньшие либо равные  самому числу, остаток от деления исходного числа на которые равен нулю (остаток от целочисленного деления вычисляется при помощи функции mod из стандартного модуля Prelude,  которая детально описывается на стр. 147).

Как  видно из представленных примеров, язык Haskell предоставляет удивительную возможность для генерации списков довольно сложной природы. Причём дело не ограничивается только натуральными числами — в качестве значений, которые могут создаваться при помощи технологии определителей списков, как уже сказано могут использоваться любые структуры данных.

Источник: Душкин Р. В., Справочник по языку Haskell. М.: ДМК Пресс, 2008. 544 с., ил.

По теме:

  • Комментарии