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

Рассмотрим следующий пример на математическом языке собирающей записи множества:

${\displaystyle S=\{2\cdot x\mid x\in \mathbb {N} ,\ x^{2}>3\}}$

или чаще

${\displaystyle S=\{2\cdot x:x\in \mathbb {N} ,\ x^{2}>3\}}$

Это читается как: «${\displaystyle S}$ — это множество всех чисел вида "2 умножить на ${\displaystyle x}$", такое что ${\displaystyle x}$ — элемент множества натуральных чисел (${\displaystyle \mathbb {N} }$), и ${\displaystyle x}$ в квадрате больше 3».

Наименьшее натуральное число, x = 1, не удовлетворяет условию x² > 3 (так как 1² > 3 неверно), поэтому 2·1 не входит в S. Следующее натуральное число, 2, уже удовлетворяет условию (2² > 3), как и все последующие натуральные числа. Таким образом, x принимает значения 2, 3, 4, 5 … Поскольку множество S состоит из всех чисел типа "2·x", оно задаётся как S = {4, 6, 8, 10, ...}. То есть S — это множество всех чётных чисел, больших 2.

В аннотированной записи примера:

${\displaystyle S=\{\underbrace {2\cdot x} _{\color {Violet}{\text{выражение результата}}}\mid \underbrace {x} _{\color {Violet}{\text{переменная}}}\in \underbrace {\mathbb {N} } _{\color {Violet}{\text{исходное множество}}},\ \underbrace {x^{2}>3} _{\color {Violet}{\text{предикат}}}\}}$

• ${\displaystyle x}$ — переменная, представляющая элементы исходного множества.
• ${\displaystyle \mathbb {N} }$ — исходное множество, в данном примере — множество натуральных чисел.
• ${\displaystyle x^{2}>3}$ — предикат (логическое выражение, фильтрующее элементы исходного множества).
• ${\displaystyle 2\cdot x}$ — выражение результата, формирующее элемент нового множества на основе элемента исходного множества, удовлетворяющего предикату.
• К фигурным скобкам ${\displaystyle \{\}}$ относится то, что результат — это множество.
• ${\displaystyle \mid }$ или ${\displaystyle :}$ — вертикальная черта читается как «такое что» («such that»). Вертикальная черта и двоеточие используются взаимозаменяемо.
• Запятые разделяют предикаты и читаются как «и».

Списковое включение обладает теми же синтаксическими компонентами для создания списка из входного списка или итератора:

• Переменная, представляющая элемент входного списка.
• Входной список (или итератор).
• Необязательное предикатное выражение.
• Выражение результата, создающее элементы результирующего списка из элементов входящего итерируемого объекта, для которых истинен предикат.

Порядок элементов выходного списка соответствует порядку во входном.

В языке Haskell синтаксис спискового включения соответствует записи в стиле сбора множеств:

s = [ 2*x | x <- [0..], x^2 > 3 ]

Здесь список [0..] соответствует ${\displaystyle \mathbb {N} }$, x^2>3 — предикату, а 2*x — выражению результата.

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

Реализация подобных конструкций предшествовала появлению термина «списковое включение». Язык программирования SETL (1969) реализовал синтаксис построения множеств, аналогичный современным списковым включениям. Пример — вывод всех простых чисел от 2 до N:

print([n in [2..N] | ∀ m in {2..n - 1} | n mod m > 0]);

Система компьютерной алгебры Axiom (1973) также реализовала конструкцию обработки потоков.

Впервые термин «comprehension» для подобных конструкций был использован Родом Берстоллом (Rod Burstall) и Джоном Дарлингтоном (John Darlington) при описании их функционального языка NPL в 1977 году. В ретроспективе Some History of Functional Programming Languages^[1] Дэвид Тёрнер отмечал:

В сноске к термину list comprehension Тёрнер отмечает:

Работа Берстолла и Дарлингтона с NPL повлияла на развитие многих функциональных языков программирования 1980-х годов, но не все из них реализовали списковые включения. Исключение составил язык Miranda, выпущенный Тёрнером в 1985 году. Стандартный чистый ленивый функциональный язык Haskell, разработанный позднее, унаследовал многие черты Miranda, включая списковые включения.

Конструкции-компрехеншены были предложены также как средство для языков запросов к базам данных^[2] и реализованы в языке запросов Kleisli^[3].

В Haskell так называемое монадическое включение (monad comprehension) обобщает списковое включение на произвольные моноиды.

В языке Python синтаксис для включения в множества появился начиная с версии 2.7. По форме он повторяет списковое включение, но формирует множества:

from typing import Set

s: Set[str] = {v for v in 'ABCDABCD' if v not in 'CB'}
print(s)
# выводит {'A', 'D'}
print(type(s))
# выводит <class 'set'>

В Racket включения для множеств создают именно множества:

(for/set ([v "ABCDABCD"] #:unless (member v (string->list "CB")))
         v))

В Python с версии 2.7 добавлен синтаксис для включения в словарь (dictionary), формирующий словари вместо списков:

s: Set[str] = {key: val for key, val in enumerate('ABCD') if val not in 'CB'}
print(s)
# выводит {0: 'A', 3: 'D'}

В Racket включения для хеш-таблиц формируют соответствующий тип:

(for/hash ([(val key) (in-indexed "ABCD"]
           #:unless (member val (string->list "CB")))
  (values key val))

Glasgow Haskell Compiler реализует расширение параллельное списковое включение (parallel list comprehension, или zip-comprehension), позволяющее использовать несколько независимых веток генерации внутри одной конструкции включения. Квалификаторы, разделённые запятыми, зависимы (вложены), а разделённые вертикальными чертами выполняются "параллельно" (на деле — они не исполняются многопоточно, а просто зипуются):

-- обычное включение
a = [(x,y) | x <- [1..5], y <- [3..5]]
-- [(1,3),(1,4),(1,5),(2,3),(2,4) ...

-- zip-включение
b = [(x,y) | (x,y) <- zip [1..5] [3..5]]
-- [(1,3),(2,4),(3,5)]

-- параллельное включение
c = [(x,y) | x <- [1..5] | y <- [3..5]]
-- [(1,3),(2,4),(3,5)]

В Racket стандартная библиотека поддерживает как параллельные, так и вложенные варианты включений (используются for и for*). Например:

> (for*/list ([x (in-range 1 6)] [y (in-range 3 6)]) (list x y))
'((1 3) (1 4) (1 5) (2 3) (2 4) (2 5) (3 3) (3 4) (3 5) (4 3) (4 4) (4 5) (5 3) (5 4) (5 5))
> (for/list ([x (in-range 1 6)] [y (in-range 3 6)]) (list x y))
'((1 3) (2 4) (3 5))

В Python возможен следующий подход:

from typing import List, Tuple

# обычное включение
a: List[Tuple[int, int]] = [(x, y) for x in range(1, 6) for y in range(3, 6)]
print(a)
# выводит [(1, 3), (1, 4), (1, 5), (2, 3), (2, 4), ...
# параллельное/zip-включение
b: List[Tuple[int, int]] = [x for x in zip(range(1, 6), range(3, 6))]
print(b)
# выводит [(1, 3), (2, 4), (3, 5)]

В Julia достигается аналогичный эффект:

# обычное включение
a::Vector{Tuple{Int, Int}} = [(x, y) for x in 1:5 for y in 3:5]

# параллельное/zip-включение
b::Vector{Tuple{Int, Int}} = [x for x in zip(1:3, 3:5)]

— только элементы представлены в виде массивов.

Эти языки, как и NPL, ориентированы главным образом на доступ к базам данных, где концепция включения особенно важна — получить «весь список» элементов зачастую вычислительно нецелесообразно (например, когда исходное множество — целая база XML). В XPath выражение:

/library/book//paragraph[@style='first-in-chapter']

интерпретируется как последовательность шагов, каждый из которых строит новый список, а следующий шаг фильтрует результат предыдущего^[4].

В XQuery помимо XPath используются конструкции FLWOR, являющиеся более мощным вариантом включения^[5]:

for $b in //book
where $b[@pages < 400]
order by $b//title
return
  <shortBook>
    <title>{$b//title}</title>
    <firstPara>{($book//paragraph)[1]}</firstPara>
  </shortBook>

Здесь //book генерирует последовательность (список); where реализует фильтрацию, order by — сортировку результата, а <shortBook> ... </shortBook> — анонимную функцию преобразования элементов последовательности (аналог map в функциональных языках).

В функциональном языке эквивалент FLWOR-выражения мог бы выглядеть так:

map(
  newXML(shortBook, newXML(title, $1.title), newXML(firstPara, $1...))
  filter(
    lt($1.pages, 400),
    xpath(//book)
  )
)

В C# 3.0 реализована технология LINQ — группа операторов обработки перечислений объектов:

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

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

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

Существенное отличие от типичных списковых включений состоит в том, что если исходный объект реализует интерфейс IQueryable, то вся последовательность операторов преобразуется в абстрактное синтаксическое дерево (AST), интерпретируемое далее самим объектом IQueryable. Это позволяет:

• переписывать несовместимые или неэффективные включения,
• транслировать AST в другой язык запросов (например, SQL).

C++ не поддерживает списковые включения на уровне синтаксиса, однако перегрузка операторов (например, |, >>, >>=) позволяет реализовать выразительный синтаксис «встраиваемых» доменно-специализированных языков запросов. Также можно использовать идиому erase–remove для фильтрации и алгоритм for_each для преобразования элементов контейнера:

import std;

using std::vector;

template <typename Collection, typename Pred, typename Trans>
Collection comprehend(Collection&& source, const Pred& predicate, const Trans& transformation) {
    // инициализация результата
    Collection d = std::forward<C>(source);

    // фильтрация элементов
    d.erase(std::ranges::remove_if(d, predicate), d.end());

    // трансформация
    std::ranges::for_each(d, transformation);

    return d;
}

int main(int argc, char* argv[]) {
    vector<int> range(10);
    // range содержит 10 нулевых элементов
    std::ranges::iota(range, 1);
    // теперь range: 1, 2, ..., 10

    vector<int> result = comprehend(
        range,
        [](int x) -> bool { return x * x <= 3; },
        [](int& x) -> void { x *= 2; }
    );
    // result теперь: 4, 6, ..., 20
}

С помощью std::views можно записывать так:

import std;

using std::vector;
using std::ranges::to;
using std::views::filter;
using std::views::transform;

int main(int argc, char* argv[]) {
    vector<int> range(10);
    std::ranges::iota(range, 1);

    vector<int> result = range
        | filter([](int x) -> bool { return x * x > 3; })
        | transform([](int x) -> int { return x * 2; })
        | to<vector>();
}

Ведутся разработки синтаксиса списковых включений для C++:

• В библиотеке Boost (модуль Range)^[6] реализованы адаптеры ^[7] (см. также Boost.Lambda), поддерживающие композицию фильтрации/трансформации:

counting_range(1,10) | filtered( _1*_1 > 3 ) | transformed(ret<int>( _1*2 ))

• Эта реализация^[8] использует макросы и перегружает оператор <<. Поддерживается любая валидная логика, хотя реализация не является потокобезопасной:

using std::vector;

vector<int> a(10);
vector<double> b;

std::ranges::iota(a, 1);

b << list_comprehension(3.1415 * x, x, a, x * x > 3)

• Другая реализация^[9] поддерживает срезы и фильтрацию с помощью перегрузки операторов:

using std::vector;

bool even(int x) { 
    return x % 2 == 0; 
}
bool x2(int& x) { 
    x *= 2; 
    return true; 
}

vector<int> l(10); 
vector<int> t;
int x = 0; 
int y = 0;

std::ranges::iota(l, 1);

(x, t) = l | x2;
(t, y) = t;

t = l < 9;
t = t < 7 | even | x2;

• Язык для встроенных запросов и обхода (LEESA^[10]) реализует XPath-подобные запросы к richly typed xml-деревьям с помощью перегруженных операторов. Например:

<catalog>
  <book>
    <title>Hamlet</title>
    <price>9.99</price>
    <author>
      <name>William Shakespeare</name>
      <country>England</country>
    </author>
  </book>
  <book>...</book>
...
</catalog>

LEESA использует оператор >> для XPath-разделителя / и позволяет строить проверки на структуру во время компиляции.

using std::vector;

// объявленные переменные
Catalog catalog;
Book book;
Author author;
Name name;

// XPath: "catalog/book/author/name"
vector<Name> authorNames = 
evaluate(root, catalog >> book >> author >> name);

// XPath: "catalog//name"
std::vector<Name> authorNames = 
evaluate(root, catalog >> descendantsOf(catalog, name));

// XPath: "catalog//author[country=="England"]"
vector<name> authorNames = 
evaluate(root, catalog  >> descendantsOf(catalog, author)
                        >> select(author, [](const Author& a) -> bool { return a.country() == "England"; })
                        >> name);