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

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

• 1 Обзор
• 2 История
• 3 Примеры на разных языках программирования
• 4 Подобные конструкции
  • 4.1 Понимание монад
  • 4.2 Задание понимания
  • 4.3 Понимание словаря
  • 4.4 Понимание параллельных списков
  • 4.5 XQuery и XPath
  • 4.6 LINQ в C #
  • 4.7 C ++
• 5 См. Также
• 6 Примечания и ссылки
  • 6.1 Haskell
  • 6.2 OCaml
  • 6.3 Python
  • 6.4 Common Lisp
  • 6.5 Clojure
  • 6.6 Axiom
• 7 Внешние ссылки

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

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

или часто

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

Это можно прочитать так:" $S\; \{\backslash \; displaystyle\; S\}$- это набор всех чисел "2 раза $x\; \{\backslash \; displaystyle\; x\}$"ТАКОЕ, ЧТО $x\; \{\backslash \; displaystyle\; x\}$является ЭЛЕМЕНТОМ или ЧЛЕНОМ набора натуральных чисел ($N\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{N\}\}$), И $x\; \{\backslash \; displaystyle\; x\}$в квадрате больше, чем $3\; \{\backslash \; displaystyle\; 3\}$. "

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

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

$S\; =\; \{2\; \cdot \; x\; ⏟\; выходное\; выражение\; \mid \; x\; ⏟\; переменная\; \in \; N\; ⏟\; входной\; набор,\; x\; 2>3\; ⏟\; предикат\}\; \{\backslash \; displaystyle\; S\; =\; \backslash \; \{\backslash \; underbrace\; \{2\; \backslash \; cdot\; x\}\; \_\; \{\backslash \; color\; \{Violet\}\; \{\backslash \; text\; \{output\; expression\}\}\}\; \backslash \; mid\; \backslash \; underbrace\; \{x\}\; \_\; \{\; \backslash \; color\; \{Violet\}\; \{\backslash \; text\; \{variable\}\}\}\; \backslash \; in\; \backslash \; underbrace\; \{\backslash \; mathbb\; \{N\}\}\; \_\; \{\backslash \; color\; \{Violet\}\; \{\backslash \; text\; \{input\; set\}\}\},\; \backslash \; \backslash \; underbrace\; \{x\; ^\; \{2\}>3\}\; \_\; \{\backslash \; color\; \{Violet\}\; \{\backslash \; text\; \{predicate\}\}\}\; \backslash \}\}$

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

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

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

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

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

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

Здесь список [0..]представляет $N\; \{\backslash \; displaystyle\; \backslash \; 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]) ;

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

Первое использование термина «понимание» для таких конструкции были в Rod Burstall и описание их функционального языка программирования NPL с 1977 года. В его ретроспективе «Some History of Functional Programming Languages» Дэвид Тернер напоминает:

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

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

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

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

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

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

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

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

Понимание множества

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

>>>s = {v вместо v в 'ABCDABCD', если v не в 'CB'}>>>print (s) {'A', 'D'}>>>тип (ы) >>>

Racket set computing создает наборы Racket вместо списков.

(для / set ([v "ABCDABCD"] #: if (member v (string->list "CB"))) v))

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

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

>>>s = {ключ: val для ключа, val в перечислении ('ABCD'), если val не в 'CB'}>>>s {0: 'A', 3: 'D'}>>>

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

(для / hash ([(ключ val) (индексированный "ABCD")] #: if (member val (string->list "CB"))) (values ​​key val))

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

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

- понимание обычного списка 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" vs "for *". Например, векторные представления «for / vector» и «for * / vector» создают векторы путем параллельного или вложенного итерации по последовательностям. Ниже приведен код Racket для примеров понимания списка Haskell.

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

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

# понимание обычного списка>>>a = [(x, y) для x в диапазоне (1, 6) для y в диапазоне (3, 6)] [(1, 3), (1, 4), (1, 5), (2, 3), (2, 4),... # понимание параллельных / сжатых списков>>>b = [x for x in zip (range (1, 6), range (3, 6))] [(1, 3), (2, 4), (3, 5)]

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

# понимание обычного массива>>>a = [(x, y) для x в 1: 5 для y в 3: 5] # понимание параллельного / заархивированного массива>>>b = [x для x в zip (1: 3, 3: 5)]

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

XQuery и XPath

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

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

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

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

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

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

для $ b в // книге, где $ b [@pages < 400] order by $b//title return {($ book // параграф) [1 ]}

Здесь XPath // книга оценивается для создания последовательности (также известной как список); предложение where является функциональным «фильтром», результат сортируется по порядку, а фрагмент 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), где x * x>3 select x * 2;

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

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

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

C ++

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

#include #include #include с использованием пространства имен std; template C comprehend (C source, const P predicate, const T transformation) {// инициализируем назначение C d = forward (source); // фильтруем элементы d.erase (remove_if (begin (d), end (d), predicate), end (d)); // применяем преобразование for_each (begin (d), end (d), transformation); return d; } int main () {список диапазон (10); // диапазон - это список из 10 элементов, все ноль йоты (begin (range), end (range), 1); // диапазон теперь содержит 1,2,..., 10 list result = comprehend (range, (int x) {return x * x <= 3;}, (int x){x *= 2;}); // result now contains 4,6,...,20 }

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

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

  counting_range (1,10) | filter (_1 * _1>3) | transformed (ret (_1 * 2))

• Однако эта реализация использует макрос и перегружает << operator. It evaluates any expression valid inside an 'if', and any variable name may be chosen. It's not threadsafe. Использование пример:

  list N; list 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) {х * = 2; вернуть истину; } список 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;

• Language for Embedded Query and Traversal (LEESA) - это встроенный DSL в C ++, который реализует запросы, подобные X-Path, с использованием перегрузки операторов. Запросы выполняются на деревьях XML с богатой типизацией, полученных с помощью xml -to-c ++ привязка из XSD. Нет абсолютно никакой строковой кодировки. Даже имена тегов xml являются классами и, следовательно, нет возможности для опечаток. Если выражение LEESA формирует неправильный путь, которого нет в данных модель, компилятор C ++ отклонит код.. Рассмотрим каталог xml.

  9.99Уильям ШекспирАнглия......

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

// Эквивалентный X-Path: "catalog / book / author / name" std :: vector author_names = оценка (корень, каталог_>>книга_>>автор_>>имя_); // Эквивалентный X-Path: "каталог // имя" std :: vector author_names = Assessment (root, catalog_>>DescendantsOf (catalog_, name_)); // Эквивалентный X-Path: "catalog // author [country ==" England "]" std :: vector author_names = Assessment (root, catalog_>>DescendantsOf (catalog_, author_)>>Select (author_, ( const author a) {return a.country () == "England";})>>name_);

• Оператор SELECT вместе с его предложениями FROM и WHERE в SQL

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

Haskell

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

OCaml

• OCaml Batteries Included
• Расширения языка, представленные в OCaml Batteries Included

Python

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

Common Lisp

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

Clojure

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

Axiom

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

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