Понимание списка - List comprehension

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

Обзор

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

{ 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}$ в квадрате больше, чем ${ displaystyle 3}$ ."

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

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

{ displaystyle S = { underbrace {2 cdot x} _ { color {Violet} { text {output expression}}} mid underbrace {x} _ { color {Violet} { text {переменная }}} in underbrace { mathbb {N}} _ { color {Violet} { text {input set}}}, underbrace {x ^ {2}> 3} _ { color {Violet} { text {предикат}}} }}

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

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

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

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

В Haskell's синтаксис понимания списка, эта конструкция построителя наборов будет записана аналогично, как:

s = [ 2*Икс | Икс <- [0..], Икс^2 > 3 ]

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

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

История

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

print ([n в [2..N] | для всех m в {2..n - 1} | n mod m> 0]);

В система компьютерной алгебры АКСИОМА (1973) имеет аналогичную конструкцию, которая обрабатывает потоки.

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

NPL был реализован в POP2 Берстоллом и использовался Дарлингтоном в работе над преобразованием программ (Burstall & Darlington 1977). Это был язык первого порядка, строго (но не полиморфно) типизированный, чисто функциональный, с вызовом по значению. В нем также были «устойчивые выражения», например
setofeven (X) <= <: x: x в X и даже (x):>}}

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

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

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

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

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

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

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

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

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

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

>>> s = {v за v в 'ABCDABCD' если v нет в 'CB'}>>> Распечатать(s){'А', 'D'}>>> тип(s)<учебный класс 'набор'>>>>

Ракетка Компоненты набора создают наборы Racket вместо списков.

(для / set ([v "ABCDABCD"] #:пока не (член v (строка-> список «CB»)))         v))

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

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

>>> s = {ключ: вал за ключ, вал в перечислять("ABCD") если вал нет в 'CB'}>>> s{0: 'А', 3: 'D'}>>>

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

(для / hash ([(вал ключ) (в индексе "ABCD")]           #:пока не (член вал (строка-> список «CB»)))  (значения ключ вал))

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

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

- регулярное понимание спискаа = [(Икс,у) | Икс <- [1..5], у <- [3..5]]-- [(1,3),(1,4),(1,5),(2,3),(2,4) ...- понимание заархивированного спискаб = [(Икс,у) | (Икс,у) <- застегивать [1..5] [3..5]]-- [(1,3),(2,4),(3,5)]- понимание параллельного спискаc = [(Икс,у) | Икс <- [1..5] | у <- [3..5]]-- [(1,3),(2,4),(3,5)]

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

> (для * / list ([Икс (в диапазоне 1 6)] [у (в диапазоне 3 6)]) (список Икс у))'((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))> (для / list ([Икс (в диапазоне 1 6)] [у (в диапазоне 3 6)]) (список Икс у))'((1 3) (2 4) (3 5))

В Python мы могли сделать следующее:

# регулярное понимание списка>>> а = [(Икс, у) за Икс в классифицировать(1, 6) за у в классифицировать(3, 6)][(1, 3), (1, 4), (1, 5), (2, 3), (2, 4), ...# понимание параллельного / сжатого списка>>> б = [Икс за Икс в застегивать(классифицировать(1, 6), классифицировать(3, 6))][(1, 3), (2, 4), (3, 5)]

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

# понимание регулярного массива>>> а = [(Икс, у) за Икс в 1:5 за у в 3:5]# понимание параллельного / заархивированного массива>>> б = [Икс за Икс в застегивать(1:3, 3:5)]

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

XQuery и XPath

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

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

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

/библиотека/книга//пункт[@стиль='первая в главе']

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

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

за $б в //книгакуда $б[@ страницы < 400]Сортировать по $б//заглавиевозвращаться  <shortBook><title>{$б//заглавие}</title><firstPara>{($книга//пункт)[1]}</firstPara></shortBook>

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

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

карта(  newXML(короткая книга, newXML(заглавие, $1.заглавие), newXML(firstPara, $1...))  фильтр(    lt($1.страницы, 400),    xpath(//книга)  ))

LINQ в C #

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

вар s = Перечислимый.Классифицировать(0, 100).Где(Икс => Икс * Икс > 3).Выбирать(Икс => Икс * 2);

Он также предлагает альтернативный синтаксис понимания, напоминающий SQL:

вар s = из Икс в Перечислимый.Классифицировать(0, 100) куда Икс * Икс > 3 Выбрать Икс * 2;

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

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

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

C ++

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

#включают <algorithm>#включают <list>#включают <numeric>с помощью пространство имен стандартное;шаблон<учебный класс C, учебный класс п, учебный класс Т>C постигать(C&& источник, const п& предикат, const Т& трансформация){  // инициализируем пункт назначения  C d = вперед<C>(источник);  // фильтрующие элементы  d.стереть(remove_if(начинать(d), конец(d), предикат), конец(d));  // применяем преобразование  для каждого(начинать(d), конец(d), трансформация);  возвращаться d;}int главный(){  список<int> классифицировать(10);      // диапазон - это список из 10 элементов, все нулевые  йота(начинать(классифицировать), конец(классифицировать), 1);      // диапазон теперь содержит 1, 2, ..., 10  список<int> результат = постигать(      классифицировать,      [](int Икс) { возвращаться Икс * Икс <= 3; },      [](int &Икс) { Икс *= 2; });      // результат теперь содержит 4, 6, ..., 20}

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

В Способствовать росту. Классифицировать [1] библиотека есть понятие переходников [2] который может применяться к любому диапазону и выполнять фильтрацию, преобразование и т. д. С этой библиотекой исходный пример Haskell будет выглядеть так (с использованием Boost.Lambda [3] для анонимных функций фильтрации и преобразования) (Полный пример ):
```
counting_range(1,10) | фильтрованный( _1*_1 > 3 ) | преобразованный(Ret<int>( _1*2 ))
```
Этот^[6] реализация использует макрос и перегружает оператор <<. Он оценивает любое выражение, допустимое внутри if, и может быть выбрано любое имя переменной. Это не потокобезопасный, тем не мение. Пример использования:

список<int> N;список<двойной> S;за (int я = 0; я < 10; я++)    N.отталкивать(я);S << list_comprehension(3.1415 * Икс, Икс, N, Икс * Икс > 3)

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

bool четное(int Икс) { возвращаться Икс % 2 == 0; }bool x2(int &Икс) { Икс *= 2; возвращаться истинный; }список<int> л, т;int Икс, у;за (int я = 0; я < 10; я++)     л.отталкивать(я);(Икс, т) = л | x2;(т, у) = т;т = л < 9;т = т < 7 | четное | x2;

Язык для встроенных запросов и обхода (LEESA^[8]) - это встроенный DSL в C ++, который реализует запросы, подобные X-Path, с использованием перегрузки операторов. Запросы выполняются на хорошо типизированных деревьях xml, полученных с помощью привязки xml-to-c ++ из XSD. Нет абсолютно никакой строковой кодировки. Даже имена тегов xml являются классами и, следовательно, недопустимы опечатки. Если выражение LEESA формирует неверный путь, которого нет в модели данных, компилятор C ++ отклонит код.
Рассмотрим каталог xml.

<catalog>  <book>    <title>Гамлет</title>    <price>9.99</price>    <author>      <name>Уильям Шекспир</name>      <country>Англия</country>    </author>  </book>  <book>...</book>...</catalog>

LEESA предоставляет >> для XPath / разделителя. Разделитель // XPath, который «пропускает» промежуточные узлы в дереве, реализован в LEESA с использованием так называемого стратегического программирования. В приведенном ниже примере catalog_, book_, author_ и name_ являются экземплярами классов catalog, book, author и name соответственно.

// Эквивалент X-Path: "каталог / книга / автор / имя"стандартное::вектор<имя> author_names = оценивать(корень, каталог_ >> книга_ >> author_ >> имя_);// Эквивалентный X-Path: "каталог // имя"стандартное::вектор<имя> author_names = оценивать(корень, каталог_ >> Потомки(каталог_, имя_));// Эквивалентный X-Path: "catalog // author [country ==" England "]"стандартное::вектор<имя> author_names = оценивать(корень, каталог_  >> Потомки(каталог_, author_)                         >> Выбирать(author_, [](const автор & а) { возвращаться а.страна() == "Англия"; })                         >> имя_);

Смотрите также

В ВЫБРАТЬ заявление вместе с его предложениями FROM и WHERE в SQL

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

^ Тернер, Дэвид (2012). «Немного истории функциональных языков программирования» (PDF). Международный симпозиум по тенденциям в функциональном программировании, Шпрингер, Берлин, Гейдельберг. С. 1–20.
^ Понимания, нотация запросов для DBPL
^ Функциональные внутренности системы запросов Kleisli
^ «2.1 Шаги по расположению». XML Path Language (XPath). W3C. 16 ноября 1999 г. Архивировано с оригинал 9 декабря 2012 г.. Получено 24 декабря 2008.
^ "Выражения XQuery FLWOR". W3Школы. Архивировано из оригинал на 2011-10-08.
^ «Понимание списка с одной переменной в C ++ с использованием макросов препроцессора». Архивировано из оригинал на 2011-08-21. Получено 2011-01-09.
^ "Составление списков C ++". Архивировано из оригинал на 2017-07-07. Получено 2011-01-09.
^ «Язык встроенных запросов и обхода (LEESA)».

Понимание списка в Бесплатном он-лайн словаре по вычислительной технике, редактор Денис Хоу.
Триндер, Фил (1992). «Понимания, нотация запросов для DBPL». Труды третьего международного семинара по языкам программирования баз данных: групповые типы и постоянные данные, Нафплион, Греция. С. 55–68.
Уодлер, Филип (1990). «Понимающие монады». Материалы конференции ACM 1990 г. по LISP и функциональному программированию, Ницца.
Вонг, Лимсун (2000). «Функциональные основы системы запросов Kleisli». Материалы пятой международной конференции ACM SIGPLAN по функциональному программированию. Международная конференция по функциональному программированию. С. 1–10.

Haskell

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

OCaml

Python

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

внешняя ссылка

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

[1] Тернер, Дэвид (2012). «Немного истории функциональных языков программирования» (PDF). Международный симпозиум по тенденциям в функциональном программировании, Шпрингер, Берлин, Гейдельберг. С. 1–20.

[2] Понимания, нотация запросов для DBPL

[3] Функциональные внутренности системы запросов Kleisli

[4] «2.1 Шаги по расположению». XML Path Language (XPath). W3C. 16 ноября 1999 г. Архивировано с оригинал 9 декабря 2012 г.. Получено 24 декабря 2008.

[5] "Выражения XQuery FLWOR". W3Школы. Архивировано из оригинал на 2011-10-08.

[6] «Понимание списка с одной переменной в C ++ с использованием макросов препроцессора». Архивировано из оригинал на 2011-08-21. Получено 2011-01-09.

[7] "Составление списков C ++". Архивировано из оригинал на 2017-07-07. Получено 2011-01-09.

[8] «Язык встроенных запросов и обхода (LEESA)».

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]