Понимание списка

— Понимание списка это синтаксическая конструкция, доступная в некоторых языках программирования для создания списка на основе существующих списков . Он следует форме математической нотации построителя множеств ( понимание множеств ), в отличие от использования функций карты и фильтра .

Обзор

Рассмотрим следующий пример в математической нотации построителя множеств .

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

или часто

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

Это можно прочитать» $S$ это набор всех чисел "2 раза $x$" ТАКОЕ ТАКОЕ $x$ является ЭЛЕМЕНТОМ или ЧЛЕНОМ множества натуральных чисел ( $\mathbb {N}$), И $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.

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

$S=\{\underbrace {2\cdot x} _{\color {Violet}{\text{output expression}}}\mid \underbrace {x} _{\color {Violet}{\text{variable}}}\in \underbrace {\mathbb {N} } _{\color {Violet}{\text{input set}}},\ \underbrace {x^{2}>3} _{\color {Violet}{\text{predicate}}}\}$

• $x$ — это переменная, представляющая элементы входного набора.
• $\mathbb {N}$ представляет входной набор, который в этом примере представляет собой набор натуральных чисел
• $x^{2}>3$ — это выражение предиката, действующее как фильтр для членов входного набора.
• $2\cdot x$ — это выходное выражение, создающее элементы нового набора из элементов входного набора, которые удовлетворяют выражению предиката.
• $\{\}$ фигурные скобки указывают, что результатом является набор
• $\mid$ $,$ вертикальная черта читается как «ТАКОЕ ЭТО». Черта и двоеточие «:» взаимозаменяемы.
• запятые разделяют предикаты и могут читаться как «И».

Понимание списка имеет те же синтаксические компоненты, которые представляют генерацию списка по порядку из входного списка или итератора :

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

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

В синтаксисе распознавания списков Haskell эта конструкция set-builder будет записана аналогично:

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

Вот список [0..] представляет $\mathbb {N}$, x^2>3 представляет предикат, и 2*x представляет выходное выражение.

Понимание списков дает результаты в определенном порядке (в отличие от членов наборов); и генераторы списков могут генерировать элементы списка по порядку, а не создавать весь список, что позволяет, например, использовать предыдущее определение Haskell членов бесконечного списка.

История

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

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

Система компьютерной алгебры AXIOM (1973) имеет аналогичную конструкцию, обрабатывающую потоки .

Впервые термин «понимание» для таких конструкций был использован в Родом Берстоллом и Джоном Дарлингтоном описании их функционального языка программирования NPL в 1977 году. В его ретроспективе «Некоторые истории языков функционального программирования» Дэвид Тернер вспоминает:

NPL был реализован в POP2 Берстоллом и использован Дарлингтоном в работе по преобразованию программ (Burstall & Darlington 1977). Язык был первого порядка, строго (но не полиморфно) типизированным, чисто функциональным, с вызовом по значению. У него также были «устоявшиеся выражения», например

setofeven (X)  <=  <:x : x in X & even(x):>}}

В сноске к термину «понимание списка» Тернер также отмечает:

Первоначально я назвал эти выражения ZF , отсылая к теории множеств Цермело-Френкеля — именно Фил Уодлер придумал лучший термин «понимание списка» .

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

Понимания были предложены в качестве нотации запроса для баз данных. и были реализованы на языке запросов к базе данных Клейсли .

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

Основная статья: Сравнение языков программирования (понимание списков)

Подобные конструкции

Понимание монады

В Haskell понимание монад — это обобщение понимания списков на другие монады функционального программирования .

Установить понимание

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

>>> s = {v for v in 'ABCDABCD' if v not in 'CB'}
>>> print(s)
{'A', 'D'}
>>> type(s)
<class 'set'>
>>>

Понимания наборов ракеток генерируют наборы ракеток вместо списков.

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

Понимание словаря

В языке Python появился новый синтаксис для понимания словаря в версии 2.7 , похожий по форме на понимание списков, но который генерирует словари Python вместо списков.

>>> s = {key: val for key, val in enumerate('ABCD') if val not in 'CB'}
>>> s
{0: 'A', 3: 'D'}
>>>

Понимания хеш-таблиц Racket генерируют хеш-таблицы Racket (одна реализация типа словаря Racket).

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

Понимание параллельного списка

Компилятор Glasgow Haskell имеет расширение, называемое параллельным пониманием списка (также известное как zip-comrehension ), которое позволяет использовать несколько независимых ветвей квалификаторов в синтаксисе понимания списка. В то время как квалификаторы, разделенные запятыми, являются зависимыми («вложенными»), ветви квалификаторов, разделенные вертикальной чертой, оцениваются параллельно (это не относится к какой-либо форме многопоточности: это просто означает, что ветви заархивированы ) .

-- regular list comprehension
a = [(x,y) | x <- [1..5], y <- [3..5]]
-- [(1,3),(1,4),(1,5),(2,3),(2,4) ...

-- zipped list comprehension
b = [(x,y) | (x,y) <- zip [1..5] [3..5]]
-- [(1,3),(2,4),(3,5)]

-- parallel list comprehension
c = [(x,y) | x <- [1..5] | y <- [3..5]]
-- [(1,3),(2,4),(3,5)]

Стандартная библиотека понятий Racket содержит параллельные и вложенные версии своих понятий, отличающиеся в названии буквами «for» и «for*». Например, векторные выражения «for/vector» и «for*/vector» создают векторы путем параллельной, а не вложенной итерации над последовательностями. Ниже приведен код Racket для примеров понимания списков Haskell.

> (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 мы могли бы сделать следующее:

>>> # regular list comprehension
>>> a = [(x, y) for x in range(1, 6) for y in range(3, 6)]
[(1, 3), (1, 4), (1, 5), (2, 3), (2, 4), ...
>>>
>>> # parallel/zipped list comprehension
>>> b = [x for x in zip(range(1, 6), range(3, 6))]
[(1, 3), (2, 4), (3, 5)]

В Юлии практически тех же результатов можно добиться следующим образом:

# regular array comprehension
>>> a = [(x, y) for x in 1:5 for y in 3:5]

# parallel/zipped array comprehension
>>> b = [x for x in zip(1:3, 3:5)]

с той лишь разницей, что вместо списков в Джулии у нас массивы.

XQuery и XPath

Как и исходное использование NPL, это по сути языки доступа к базе данных.

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

В XPath выражение:

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

концептуально оценивается как серия «шагов», где каждый шаг создает список, а следующий шаг применяет функцию фильтра к каждому элементу в выходных данных предыдущего шага.

В XQuery доступен полный XPath, но FLWOR , которые являются более мощной конструкцией понимания. также используются операторы

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

Здесь XPath //book оценивается для создания последовательности (также известной как список); предложениеwhere является функциональным «фильтром», порядок сортирует результат, а <shortBook>...</shortBook> Фрагмент XML на самом деле представляет собой анонимную функцию , которая создает/преобразует XML для каждого элемента последовательности, используя подход «карты», используемый в других функциональных языках.

Итак, на другом функциональном языке приведенный выше оператор FLWOR может быть реализован следующим образом:

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

LINQ в C#

В C# 3.0 имеется группа связанных функций под названием LINQ , которая определяет набор операторов запроса для управления перечислениями объектов.

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;

LINQ предоставляет возможности по сравнению с обычными реализациями понимания списков. Когда корневой объект понимания реализует IQueryable Интерфейс, а не просто выполнение связанных методов понимания, вся последовательность команд преобразуется в объект абстрактного синтаксического дерева (AST), который передается объекту IQueryable для интерпретации и выполнения.

Это позволяет, среди прочего, IQueryable

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

С++

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

#include <algorithm>
#include <list>
#include <numeric>

using namespace std;

template<class C, class P, class T>
C comprehend(C&& source, const P& predicate, const T& transformation)
{
  // initialize destination
  C d = forward<C>(source);

  // filter elements
  d.erase(remove_if(begin(d), end(d), predicate), end(d));

  // apply transformation
  for_each(begin(d), end(d), transformation);

  return d;
}

int main()
{
  list<int> range(10);
      // range is a list of 10 elements, all zero
  iota(begin(range), end(range), 1);
      // range now contains 1, 2, ..., 10

  list<int> result = comprehend(
      range,
      [](int x) { return x * x <= 3; },
      [](int &x) { x *= 2; });
      // result now contains 4, 6, ..., 20
}

Предпринимаются некоторые усилия по обеспечению C++ конструкциями/синтаксисом понимания списков, аналогичными нотации построителя множеств.

• В Бусте . В библиотеке Range [1] существует понятие адаптеров [2] , которые можно применять к любому диапазону и выполнять фильтрацию, преобразование и т. д. С этой библиотекой исходный пример Haskell будет выглядеть так (с использованием Boost.Lambda [3] для анонимной фильтрации и функции преобразования) ( Полный пример ):

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

• Этот реализация использует макрос и перегружает оператор <<. Он оценивает любое выражение, допустимое внутри «if», и может быть выбрано любое имя переменной. это не потокобезопасно Однако . Пример использования:

list<int> N;
list<double> S;

for (int i = 0; i < 10; i++)
    N.push_back(i);

S << list_comprehension(3.1415 * x, x, N, x * x > 3)

• Этот реализация обеспечивает разделение головы и хвоста с использованием классов и перегрузки операторов, а | оператор фильтрации списков (с использованием функций). Пример использования:

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

list<int> l, t;
int x, y;

for (int i = 0; i < 10; i++)
     l.push_back(i);

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

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

• Язык встроенных запросов и обхода (LEESA ) — это встроенный DSL в C++, который реализует запросы типа X-Path с использованием перегрузки операторов. Запросы выполняются на широко типизированных деревьях XML, полученных с использованием привязки xml к C++ из XSD. Строкового кодирования абсолютно нет. Даже имена тегов xml являются классами, поэтому опечатки исключены. Если выражение LEESA образует неправильный путь, которого нет в модели данных, компилятор C++ отклонит код.
  Рассмотрим 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/разделителя. // Разделитель XPath, который «пропускает» промежуточные узлы в дереве, реализован в LEESA с использованием так называемого стратегического программирования. В приведенном ниже примере каталог_, книга_, автор_ и имя_ являются экземплярами классов каталога, книги, автора и имени соответственно.

// Equivalent X-Path: "catalog/book/author/name"
std::vector<name> author_names = 
evaluate(root, catalog_ >> book_ >> author_ >> name_);

// Equivalent X-Path: "catalog//name"
std::vector<name> author_names = 
evaluate(root, catalog_ >> DescendantsOf(catalog_, name_));

// Equivalent X-Path: "catalog//author[country=="England"]"
std::vector<name> author_names = 
evaluate(root, catalog_  >> DescendantsOf(catalog_, author_)
                         >> Select(author_, [](const author & a) { return a.country() == "England"; })
                         >> name_);

См. также

• Обозначение построителя множеств
• Инструкция SELECT вместе с ее предложениями FROM и WHERE в SQL.

Примечания и ссылки

• Понимание списков в Бесплатном онлайн-словаре по информатике, редактор Денис Хоу.
• Уодлер, Филип (1990). «Понимание монад» . Материалы конференции ACM 1990 года по LISP и функциональному программированию, Ницца .

Внешние ссылки

• SQL-подобные операции над множествами с однострочниками для понимания списков в кулинарной книге Python
• Обсуждение списков в Scheme и связанных с ними конструкциях
• Список понятий на разных языках

Аксиома

• Примеры потоков аксиом

Кложур

• Документация API Clojure — для макросов

Общий Лисп

• Реализация макроса понимания Lisp от Гая Лапальма

Хаскелл

• Отчет Haskell 98, глава 3.11. Понимание списков .
• Руководство пользователя системы компиляции Glorious Glasgow Haskell, глава 7.3.4. Понимание параллельных списков .
• Руководство пользователя Hugs 98, глава 5.1.2. Понимание параллельных списков (также известное как понимание zip) .

OCaml

• Батарейки OCaml в комплекте
• Расширения языка, представленные в OCaml. Батареи в комплекте.

Питон

• Учебник по Python, Понимание списков .
• Справочник по языку Python, отображается список .
• Предложение по усовершенствованию Python PEP 202: Понимание списков .
• Справочник по языку Python, выражения-генераторы .
• Предложение по усовершенствованию Python PEP 289: Генераторные выражения .