Генераторы списков

Если вы изучали курс математики, то, возможно, сталкивались со способом задания множества путём описания характерных свойств, которыми должны обладать его элементы. Обычно этот метод используется для построения подмножеств из множеств.

Вот пример простого описания множества. Множество, состоящее из первых десяти чётных чисел, это S = {2 · x | x ? N, x ? 10}, где выражение перед символом | называется производящей функцией (output function), x – переменная, N – входной набор, а x ? 10 – условие выборки. Это означает, что множество содержит удвоенные натуральные числа, которые удовлетворяют условию выборки.

Если бы нам потребовалось написать то же самое на языке Haskell, можно было бы изобрести что-то вроде: take 10 [2,4..]. Но что если мы хотим не просто получить первые десять удвоенных натуральных чисел, а применить к ним некую более сложную функцию? Для этого можно использовать генератор списков. Он очень похож на описание множеств:

ghci> [x*2 | x <– [1..10]]

[2,4,6,8,10,12,14,16,18,20]

В выражении [x*2 | x <– [1..10]] мы извлекаем элементы из списка [1..10], т. е. x последовательно принимает все значения элементов списка. Иногда говорят, что x связывается с каждым элементом списка. Часть генератора, находящаяся левее вертикальной черты |, определяет значения элементов результирующего списка. В нашем примере значения x, извлечённые из списка [1..10], умножаются на два.

Теперь давайте добавим к этому генератору условие выборки (предикат). Условия идут после задания источника данных и отделяются от него запятой. Предположим, что нам нужны только те элементы, которые, будучи удвоенными, больше либо равны 12.

ghci> [x*2 | x <– [1..10], x*2 >= 12]

[12,14,16,18,20]

Это работает. Замечательно! А как насчёт ситуации, когда требуется получить все числа от 50 до 100, остаток от деления на 7 которых равен 3? Легко!

ghci> [ x | x <– [50..100], x `mod` 7 == 3]

[52,59,66,73,80,87,94]

И снова получилось!

ПРИМЕЧАНИЕ. Заметим, что прореживание списков с помощью условий выборки также называется фильтрацией.

Мы взяли список чисел и отфильтровали их условиями. Теперь другой пример. Давайте предположим, что нам нужно выражение, которое заменяет каждое нечётное число больше 10 на БАХ!", а каждое нечётное число меньше 10 – на БУМ!". Если число чётное, мы выбрасываем его из нашего списка. Для удобства поместим выражение в функцию, чтобы потом легко использовать его повторно.

boomBangs xs = [if x < 10 then "БУМ!" else "БАХ!" | x <– xs, odd x]

ПРИМЕЧАНИЕ. Помните, что если вы пытаетесь определить эту функцию в GHCi, то перед её именем нужно написать let. Если же вы описываете её в отдельном файле, а потом загружаете его в GHCi, то никакого let не требуется.

Последняя часть описания – условие выборки. Функция odd возвращает значение True для нечётных чисел и False – для чётных. Элемент включается в список, только если все условия выборки возвращают значение True.

ghci> boomBangs [7..13]

["БУМ!","БУМ!","БАХ!","БАХ!"]

Мы можем использовать несколько условий выборки. Если бы по требовалось получить все числа от 10 до 20, кроме 13, 15 и 19, то мы бы написали:

ghci> [x | x <– [10..20], x /= 13, x /= 15, x /= 19]

[10,11,12,14,16,17,18,20]

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

ghci> [x+y | x <- [1,2,3], y <- [10,100,1000]]

[11,101,1001,12,102,1002,13,103,1003]

Здесь x берётся из списка [1,2,3], а y – из списка [10,100,1000]. Эти два списка комбинируются следующим образом. Во-первых, x становится равным 1, а y последовательно принимает все значения из списка [10,100,1000]. Поскольку значения x и y складываются, в начало результирующего списка помещаются числа 11, 101 и 1001 (1 прибавляется к 10, 100, 1000). После этого x становится равным 2 и всё повторяется, к списку добавляются числа 12, 102 и 1002. То же самое происходит для x равного 3.

Таким образом, каждый элемент x из списка [1,2,3] всеми возможными способами комбинируется с каждым элементом y из списка [10,100,1000], а x+y используется для построения из этих комбинаций результирующего списка.

Вот другой пример: если у нас есть два списка [2,5,10] и [8,10,11], и мы хотим получить произведения всех возможных комбинаций из элементов этих списков, то можно использовать следующее выражение:

ghci> [x*y | x <– [2,5,10], y <– [8,10,11]]

[16,20,22,40,50,55,80,100,110]

Как и ожидалось, длина нового списка равна 9.

Допустим, нам потребовались все возможные произведения, которые больше 50:

ghci> [x*y | x <– [2,5,10], y <– [8,10,11], x*y > 50]

[55,80,100,110]

А как насчёт списка, объединяющего элементы списка прилагательных с элементами списка существительных… с довольно забавным результатом?

ghci> let nouns = ["бродяга","лягушатник","поп"]

ghci> let adjs = ["ленивый","ворчливый","хитрый"]

ghci> [adj ++ " " ++ noun | adj <– adjs, noun <– nouns]

["ленивый бродяга","ленивый лягушатник","ленивый поп",

"ворчливый бродяга","ворчливый лягушатник", "ворчливый поп",

"хитрый бродяга","хитрый лягушатник","хитрый поп"]

Генераторы списков можно применить даже для написания своей собственной функции length! Назовём её length': эта функция будет заменять каждый элемент списка на 1, а затем мы все эти единицы просуммируем функцией sum, получив длину списка:

length' xs = sum [1 | _ <– xs]

Символ _ означает, что нам неважно, что будет получено из списка, поэтому вместо того, чтобы писать имя образца, которое мы никогда не будем использовать, мы просто пишем _. Поскольку строки – это списки, генератор списков можно использовать для обработки и создания строк. Вот функция, которая принимает строку и удаляет из неё всё, кроме букв в верхнем регистре:

removeNonUppercase st = [c | c <– st, c `elem` ['А'..'Я']]

Всю работу здесь выполняет предикат: символ будет добавляться в новый список, только если он является элементом списка ['А'..'Я']. Загрузим функцию в GHCi и проверим:

ghci> removeNonUppercase "Ха-ха-ха! А-ха-ха-ха!"

"ХА"

ghci> removeNonUppercase "ЯнеЕМЛЯГУШЕК"

"ЯЕМЛЯГУШЕК"

Вложенные генераторы списков также возможны, если вы работаете со списками, содержащими вложенные списки. Допустим, список содержит несколько списков чисел. Попробуем удалить все нечётные числа, не разворачивая список:

ghci> let xxs = [[1,3,5,2,3,1,2],[1,2,3,4,5,6,7],[1,2,4,2,1,6,3,1,3,2]]

ghci> [[x | x <– xs, even x ] | xs <– xxs]

[[2,2],[2,4,6],[2,4,2,6,2]]

ПРИМЕЧАНИЕ. Вы можете писать генераторы списков в несколько строк. Поэтому, если вы не в GHCi, лучше разбить длинные генераторы списков, особенно вложенные, на несколько строк.