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

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

Обзор

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

$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 будет записана аналогично:

с   =   [   2  *  х   |    х   <-   [  0  ..  ],   х  ^  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 в X & Even(x):>}} 

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

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

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

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

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

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

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

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

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

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

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

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

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

(  for/set   ([  v   "ABCDABCD"  ]   #:unless   (  member   v   (  строка->список   "CB"  ))) 
          v  )) 

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

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

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

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

(  for/hash   ([(  val   key  )   (  индексированный   "ABCD"  )] 
            #:unless   (  member   val   (  строка->список   "CB"  ))) 
   (  значения   ключа   val  )) 

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

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

-- регулярное понимание списка 
 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   =   [ (  Икс  ,  у  )   |    х   <-   [  1  ..  5  ]   |    y   <-   [  3  ..  5  ]] 
 -- [(1,3),(2,4),(3,5)] 

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

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

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

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

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

 # параллельное/архивированное понимание массива 
 >>>   b   =   [  x   for   x   in   zip  (  1  :  3  ,   3  :  5  )] 

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

XQuery и XPath

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

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

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

/  библиотека  /  книга  //  абзац  [  @style  =  'первый в главе'  ] 

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

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

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

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

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

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

LINQ в C#

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

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

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

var   s   =   from   x   в   Enumerable  .   Диапазон  (  0  ,   100  )   , где   x   *   x   >   3,   выберите   x   *   2  ; 

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

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

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

С++

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

#include   <алгоритм> 
 #include   <list> 
 #include   <numeric> 

 using   namespace   std  ; 

  шаблон  <  класс   C  ,   класс   P  ,   класс   T  > 
 C   comprehend  (  C  &&   источник  ,   const   P  &   предикат  ,   const   T  &   преобразование  ) 
 { 
   // инициализируем пункт назначения 
   C   d   =   вперед  <  C  >  (  источник  ); 

    // элементы фильтра 
   d  .   стереть  (  remove_if  (  begin  (  d  ),   end  (  d  ),   predicate  ),   end  (  d  )); 

    // применяем преобразование 
   for_each  (  begin  (  d  ),   end  (  d  ),   Transformation  ; 

    вернуть   д  ; 
  } 

 int   main  () 
 { 
   list  <  int  >   range  (  10  ); 
        // диапазон — это список из 10 элементов, все ноль 
   йот  (  begin  (  range  ),   end  (  range  ),   1  ); 
        // диапазон теперь содержит 1, 2, ..., 10 

   list  <  int  >   result   =   comprehend  ( 
       range  , 
       [](  int   x  )   {   return   x   *   x   <=   3  ;   }, 
       [](  int   &  x  )   {   x   *=   2  }   ); 
        // результат теперь содержит 4, 6, ..., 20 
 } 

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

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

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

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

список  <  интервал  >   N  ; 
  список  <  двойной  >   S  ; 

  для   (  int   я   знак равно   0  ;   я   <   10  ;   я  ++  ) 
     N  .   push_back  (  я  ); 

  S   <<   list_comrehension  (  3,1415   *   x  ,   x  ,   N  ,   x   *   x   >   3  ) 

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

bool   Even  (  int   x  )   {   return   x   %   2   ==   0  ;    } 
 bool   x2  (  int   &  x  )   {   x   *=   2  ;    вернуть   истину  ;    } 

 список  <int> ​ ​   л  ,   т  ; 
  интервал   х  ,   у  ; 

  для   (  int   я   знак равно   0  ;   я   <   10  ;   я  ++  ) 
      л  .   push_back  (  я  ); 

  (  Икс  ,   т  )   знак равно   л   |    х2  ; 
  (  т  ,   у  )   знак равно   т  ; 

  т знак   равно   л   <   9  ; 
  т   знак равно   т   <   7   |    даже   |    х2  ; 

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

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

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

// Эквивалентный X-путь: «каталог/книга/автор/имя» 
 std  ::  вектор  <  имя  >   имя_автора   =  
 оценить  (  root  ,   каталог_   >>   книга_   >>   автор_   >>   имя_  ); 

  // Эквивалентный X-путь: "catalog//name" 
 vector  <name>  author_names  =  ::  Assessment   catalog_   (  
 root  ,  Catalog_  >>   DescendantsOf   (   ,  name_  std  )   )  ; 

  // Эквивалентный X-путь: "catalog//author[country=="England" 
 std  ::  vector  <name>  root  "   author_names   =  
 Assessment  (  ,  ]   catalog_    >>   DescendantsOf  (  catalog_  ,   author_  ) 
                          >>   Select  (  author_  ,   [ ](  constauthor   )   &   a  )   {   return   a  .  страна  ()   ==   "Англия"  >>   } 
                          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: Генераторные выражения .