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

Синтаксическая конструкция для создания списка на основе существующих списков

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

Обзор

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

${\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\}}$

Это можно прочитать так: « это множество всех чисел «2 раза », ТАКОЕ, ЧТО ЯВЛЯЕТСЯ ЭЛЕМЕНТОМ или ЧЛЕНОМ множества натуральных чисел ( ), И в квадрате больше ». ${\displaystyle S}$ ${\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", оно задается как S = {4, 6, 8, 10,...}. Другими словами, S — это множество всех четных чисел, больших 2.

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

${\displaystyle 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}}}\}}$

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

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

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

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

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

с = [ 2 * х | х <- [ 0 .. ], х ^ 2 > 3 ]           

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

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

История

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

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

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

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

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

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

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

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

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

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

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

Похожие конструкции

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

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

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

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

>>> s  =  { v  для  v  в  'ABCDABCD'  если  v  не  в  'CB' } >>> print ( s ) {'A', 'D'} >>> type ( s ) <class 'set'> >>>

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

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

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

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

>>> s  =  { key :  val  для  key ,  val  в  enumerate ( 'ABCD' )  если  val  не  в  '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 имеет расширение, называемое parallel list comprehension (также известное как zip-comprehension ), которое допускает несколько независимых ветвей квалификаторов в синтаксисе list comprehension. В то время как квалификаторы, разделенные запятыми, являются зависимыми («вложенными»), ветви квалификаторов, разделенные вертикальными чертами, оцениваются параллельно (это не относится к какой-либо форме многопоточности: это просто означает, что ветви сжаты ).

-- обычное списочное включение a = [( x , y ) | x <- [ 1 .. 5 ], y <- [ 3 .. 5 ]] -- [(1,3),(1,4),(1,5),(2,3),(2,4) ...         -- сжатый список 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's comprehensions содержит параллельные и вложенные версии своих comprehensions, различающиеся по "for" и "for*" в названии. Например, векторные comprehensions "for/vector" и "for*/vector" создают векторы путем параллельной и вложенной итерации по последовательностям. Ниже приведен код Racket для примеров спискового comprehensions на Haskell.

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

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

>>> # обычное включение списка >>> 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), ... >>> >>> # параллельное/сжатое включение списка >>> b  =  [ x  for  x  in  zip ( range ( 1 ,  6 ),  range ( 3 ,  6 ))] [(1, 3), (2, 4), (3, 5)]

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

# регулярное понимание массива >>> a = [( x , y ) for x in 1 : 5 for y in 3 : 5 ]            # параллельное/сжатое понимание массива >>> b = [ x for x in zip ( 1 : 3 , 3 : 5 )]        

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

XQuery и XPath

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

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

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

/ библиотека / книга // абзац [ @style = 'first-in-chapter' ]

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

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

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

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

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

карта ( newXML ( shortBook , newXML ( title , $ 1. title ), newXML ( firstPara , $ 1...)) фильтр ( lt ( $ 1. pages , 400 ), xpath (// book ) ) )          

LINQ в C#

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

var s = Перечислимый . Диапазон ( 0 , 100 ). Где ( x => x * x > 3 ). Выбрать ( x => x * 2 );              

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

var s = from x in Enumerable . Диапазон ( 0 , 100 ) , где x * x > 3 select x * 2 ;                 

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

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

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

С++

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

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

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

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

  counting_range ( 1 , 10 ) | отфильтровано ( _1 * _1 > 3 ) | преобразовано ( ret < int > ( _1 * 2 ))          

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

список < int > N ; список < double > S ;  для ( int i = 0 ; i < 10 ; i ++ ) N . push_back ( i );         S << list_comprehension ( 3.1415 * x , x , N , x * x > 3 )           

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

bool even ( int x ) { return x % 2 == 0 ; } bool x2 ( int & x ) { x *= 2 ; return true ; }                   список < целое > l , t ; целое x , y ;    для ( int i = 0 ; i < 10 ; i ++ ) l . push_back ( i );         ( x , t ) = l | x2 ; ( t , y ) = t ;        t = l < 9 ; t = t < 7 | четно | x2 ;            

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

<каталог> <книга> <название> Гамлет </название> <цена > 9,99 </цена> <автор> <имя> Уильям Шекспир </название> <страна> Англия </страна> </автор> < /книга> <книга> ... </книга>          ...</каталог>

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

// Эквивалентный X-Path: "catalog/book/author/name" std :: vector < name > author_names = estimate ( root , catalog_ >> book_ >> author_ >> name_ );          // Эквивалентный X-Path: "catalog//name" std :: vector < name > author_names = evaluation ( root , catalog_ >> DescendantsOf ( catalog_ , name_ ));       // Эквивалентный X-Path: "catalog//author[country=="England"]" std :: vector < name > author_names = evaluation ( root , catalog_ >> DescendantsOf ( catalog_ , author_ ) >> Select ( author_ , []( const author & a ) { return a . country () == "England" ; }) >> name_ );                     

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

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

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

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

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

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

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

Аксиома

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

Кложур

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

Общий Лисп

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

Хаскелл

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

OCaml

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

Питон

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