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

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

Обзор [ править ]

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

${\ 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 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  =  [  2 * x  |  x  <-  [ 0 .. ],  x ^ 2  >  3  ]

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

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

История [ править ]

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

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

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

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

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

setofeven (X) <= <: x: x в X и даже (x):>}}

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

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

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

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

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

Подобные конструкции [ править ]

Понимание монад [ править ]

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

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

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

>>>  сек  =  { V  для  V  в  'ABCDABCD' ,  если  v  не  в  'СВ' } >>>  печать ( ы ) { 'А' ,  'D' } >>>  тип ( ы ) < класс  ' множества '> >>>

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

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

Понимание словаря [ править ]

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

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

- составление регулярного списка 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 содержит параллельные и вложенные версии своих интерпретаций, которые отличаются в названии «for» vs «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 )) >  ( для / 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  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  for  x  in  zip ( 1 : 3 ,  3 : 5 )]

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

XQuery и XPath [ править ]

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

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

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

/ library / book // параграф [ @style = 'first-in-chapter' ]

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

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

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

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

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

map (  newXML ( shortBook ,  newXML ( заголовок ,  $ 1. заголовок ),  newXML ( firstPara ,  $ 1 ...))  filter (  lt ( $ 1. pages ,  400 ),  xpath (// книга )  ) )

LINQ в C # [ править ]

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

var  s  =  Перечислимый . Диапазон ( 0 ,  100 ). Где ( x  =>  x  *  x  >  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 ++ [ править ]

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 . Стирание ( remove_if ( начинают ( д ),  конец ( д ),  предикат ),  конец ( д )); // применяем преобразование  for_each ( begin ( d ),  end ( d ),  transformation ); return  d ; }Int  Основной () {  список < INT >  Диапазон ( 10 );  // диапазон - это список из 10 элементов, все ноль  йоты ( begin ( range ),  end ( range ),  1 );  // диапазон теперь содержит 1, 2, ..., 10 список < int >  result  =  comprehend (  диапазон ,  [] ( int  x )  {  return  x  *  x  <=  3 ;  },  [] ( int  & x )  {  x  * =  2 ;  });  // результат теперь содержит 4, 6, ..., 20 }

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

• In Boost . В библиотеке Range [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 ;  я ++ )  Н . push_back ( я );S  <<  list_comprehension ( 3,1415  *  x ,  x ,  N ,  x  *  x  >  3 )

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

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

• Language for Embedded Query and Traversal (LEESA ^[8] ) - это встроенный DSL в C ++, который реализует запросы, подобные X-Path, с использованием перегрузки операторов. Запросы выполняются на XML-деревьях с богатой типизацией, полученных с помощью привязки XML-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: "каталог / книга / автор / имя" std :: vector < имя >  author_names  =  оценить ( root ,  catalog_  >>  book_  >>  author_  >>  name_ );// Эквивалент X-Path: "Каталог // имя" станд :: вектор < имя >  AUTHOR_NAMES  =  оценка ( корень ,  catalog_  >>  DescendantsOf ( catalog_ ,  name_ ));// Эквивалент X-Path: "Каталог // автор [страна ==" Англия "]" станд :: вектор < имя >  AUTHOR_NAMES  =  оценка ( корень ,  catalog_  >>  DescendantsOf ( catalog_ ,  author_ )  >>  Выбрать ( author_ ,  [ ] ( const  author  &  a )  {  return  a . country ()  ==  "England" ;  })  >>  name_ );

См. Также [ править ]

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

Примечания и ссылки [ править ]

• Понимание списков в бесплатном он-лайн словаре по вычислительной технике, редактор Денис Хоу.
• Триндер, Фил (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 [ править ]

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

Python [ править ]

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

Common Lisp [ править ]

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

Clojure [ править ]

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

Аксиома [ править ]

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

Внешние ссылки [ править ]

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