Списковое включение

Спи́сковое включение (списочное выражение, абстракция списков; англ. list comprehension) в синтаксисе некоторых языков программирования — это способ компактного описания операций обработки списков.

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

 [ n | n <- [1..]; n rem 2 = 0 ] 

что читается так: «список всех n, таких что n входит в [1..] и остаток от деления n на 2 равен нулю».

По аналогии со списковыми включениями в других языках программирования есть выражения битовых строк (Erlang), включения списков и словарей (Python в версии 3).

Терминология

В переводе книги Филда и Харрисона «Функциональное программирование» вводится термин «абстракция списков» и «включение списков». Тем не менее в литературе используются также «списковое выражение», «списочное выражение», «выделение списка», «списочное встраивание», «генератор списка» (возможно, не очень удачный перевод, так как в функциональном программировании есть отдельное понятие для генератора списка, англ. list generator), «определитель списка».

В аксиоматике теории множеств Цермело-Френкеля есть аксиома выделения, которая позволяет строить множество на основе имеющегося, путём выбора элементов, соответствующих некоторому предикату. Абстракция списков является аналогией выделения для списков и иногда можно даже встретить термин ZF-выражение.

Примеры из различных языков программирования

Python

Чётные числа от 2 до 9998 включительно:

[n for n in range(1, 10000) if n % 2 == 0] 

Списковые включения могут использовать вложенные итерации по переменным:

[(x, y) for x in range(1, 10) for y in range(1, 10) if x % y == 0] 

В языке Python есть и выражения-генераторы, которые имеют схожий со списковыми включениями синтаксис, но возвращают (итератор). Сумма чётных чисел из предыдущего примера:

sum(n for n in range(1, 10000) if n % 2 == 0) 

В данном случае дополнительные скобки не нужны, но в общем случае их отсутствие вызовет синтаксическую ошибку.

Как уже говорилось выше, Python предоставляет аналогичные возможности для создания множеств и словарей.

>>> {x for x in range(10)} {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} >>> {x: x**2 for x in range(10)} {0: 0, 1: 1, 2: 4, 3: 9, 4: 16, 5: 25, 6: 36, 7: 49, 8: 64, 9: 81} 

Ruby

Чётные числа от 2 до 9998 включительно:

(1...10000).select{ |i| i%2 == 0 } # с неявным вызовом метода to_proc в отношении символа :even? (1...10000).select(&:even?) 

Erlang

В Erlang генератор списка будет выглядеть следующим образом:

[ N || N <- [1, 2, 3, 4, 5, 6], N rem 2 == 0 ]. 

Haskell

Пример с чётными числами на Haskell:

[x | x <- [1..], x `mod` 2 == 0] -- бесконечный список: [2,4,6,8,10..] 

В Haskell выражение вида x <- выр называется генератором. В одном выделении может быть несколько генераторов:

[(x, y) | x <- [1..4], y <- [1..4], x `mod` y == 0] -- 8 уникальных пар: [(1,1),(2,1),(2,2),(3,1),(3,3),(4,1),(4,2),(4,4)] 

LINQ в C#

LINQ для C# 3.0 имеет несколько сходных со списковыми включениями синтаксических конструкций для запросных выражений:

var s = Enumerable.Range(0, 100).Where(x => x*x > 3).Select(x => x*2); 

Альтернативный синтаксис, напоминающий SQL:

var s = from x in Enumerable.Range(0, 100) where x*x > 3 select x*2; 

Julia

Синтаксис списковых включений в (Julia) позаимствован из Python.

Пример со списком чётных чисел:

[n for n in 1:1000 if iseven(n)] 

Аналогичный синтаксис применяется для наполнения других типов контейнеров:

# кортеж Tuple(n^2 for n in -10:10) # множество Set(abs(n) for n in -10:10) # словарь Dict(c=>codepoint(c) for c in 'a':'z') 

Как и в Python, поддерживаются вложенные итерации по нескольким переменным:

julia> [(x,y) for x in 1:3 for y in 1:3 if x ≠ y] 6-element Array{Tuple{Int64,Int64},1}:  (1, 2)  (1, 3)  (2, 1)  (2, 3)  (3, 1)  (3, 2) 

Примечания

1. Филд, Харрисон, 1993, с. 93-94.
2. См. академические источники в Google Scholar.
3. Алексей Бешенов. Функциональное программирование на Haskell : Часть 4. Свертки списков, IBM  (неопр.). Дата обращения: 14 декабря 2013. 14 декабря 2013 года.
4. И опять о функциональном программировании на Python, перевод Intersoft Lab  (неопр.). Дата обращения: 14 декабря 2013. 14 декабря 2013 года.
5. Дэвид Мертц, Очаровательный Python: Функциональное программирование на языке Python, Часть 1  (неопр.). Дата обращения: 14 декабря 2013. 14 декабря 2013 года.
6. Душкин, 2007, с. 110.
7. Чезарини, Томпсон, 2012, с. 27.
8. Душкин, 2007, с. 110-116.
9. Алексей Бешенов. Функциональное программирование на Haskell: Часть 3. Определение функций, IBM  (неопр.). Дата обращения: 14 декабря 2013. 14 декабря 2013 года.
10.   (неопр.). Дата обращения: 14 декабря 2013. Архивировано из оригинала 16 декабря 2013 года.
11. Прохоренок, 2011, с. 124.
12. Albahari, Albahari, 2012, p. 328—331.

Литература

• Душкин Р. Функциональное программирование на языке Haskell.. — ДМК-Пресс, 2007. — 608 с. — .
• Прохоренок Н. А. Python. Самое необходимое.. — БХВ-Петербург, 2011. — 416 с. — .
• Филд А., Харрисон П. Функциональное программирование = Functional Programming. — М.: Мир, 1993. — 637 с. — .
• Чезарини Ф. Томпсон С. Программирование в Erlang = Erlang Programming. — ДМК Пресс, 2012. — 487 с. — .
• Albahari, J. and Albahari, B. C# 5.0 in a Nutshell: The Definitive Reference. — O'Reilly Media, Incorporated, 2012. — 1042 p. — .

Ссылки

• Списочные выражения. Модель памяти для типов языка Python — хендбук Академии Яндекса «Основы Python».