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

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

Обзор

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

или часто

Это может быть прочитано: « это набор всех чисел» 2 раза «ТАКОЕ, ЧТО является ЭЛЕМЕНТОМ или ЧЛЕНОМ набора натуральных чисел ( ), И в квадрате больше, чем ».

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

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

  • - это переменная, представляющая элементы входного набора.
  • представляет входной набор, который в этом примере представляет собой набор натуральных чисел
  • - это выражение предиката, действующее как фильтр для элементов входного набора.
  • - это выходное выражение, создающее элементы нового набора из элементов входного набора, удовлетворяющих выражению предиката.
  • фигурные скобки указывают, что результатом является набор
  • вертикальная полоса читается как «ТАКОЕ». Полоса и двоеточие «:» взаимозаменяемы.
  • запятые разделяют предикаты и могут читаться как «И».

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

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

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

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

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

Здесь список [0..]представляет , представляет предикат и представляет собой выходное выражение. x^2>32*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 in X & even(x):>}}

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

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

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

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

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

Основная статья: Сравнение языков программирования (понимание списка) 
julia: 12x12 multiplication matrix 
[i*j for i=1:12,j=1:12]

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

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

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

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

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

>>> s = {v for v in 'ABCDABCD' if v not in 'CB'}
>>> print(s)
{'A', 'D'}
>>> type(s)
<class 'set'>
>>>

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

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

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

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

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

-- regular list comprehension
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. 

> (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))
> (for/list ([x (in-range 1 6)] [y (in-range 3 6)]) (list x y))
'((1 3) (2 4) (3 5))

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

# regular list comprehension
>>> 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), ...

# parallel/zipped list comprehension
>>> b = [x for x in zip(range(1, 6), range(3, 6))]
[(1, 3), (2, 4), (3, 5)]

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

# regular array comprehension
>>> a = [(x, y) for x in 1:5 for y in 3:5]

# parallel/zipped array comprehension
>>> b = [x for x in zip(1:3, 3:5)]

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

XQuery и XPath

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

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

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

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

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

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

for $b in //book
where $b[@pages < 400]
order by $b//title
return
  <shortBook>
    <title>{$b//title}</title>
    <firstPara>{($book//paragraph)[1]}</firstPara>
  </shortBook>

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

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

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

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

C ++

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

#include <algorithm>
#include <list>
#include <numeric>

using namespace std;

template<class C, class P, class T>
C comprehend(C&& source, const P& predicate, const T& transformation)
{
  // initialize destination
  C d = forward<C>(source);

  // filter elements
  d.erase(remove_if(begin(d), end(d), predicate), end(d));

  // apply transformation
  for_each(begin(d), end(d), transformation);

  return d;
}

int main()
{
  list<int> range(10);
      // range is a list of 10 elements, all zero
  iota(begin(range), end(range), 1);
      // range now contains 1, 2, ..., 10

  list<int> result = comprehend(
      range,
      [](int x) { return x * x <= 3; },
      [](int &x) { x *= 2; });
      // result now contains 4, 6, ..., 20
}

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

  • In Boost . В библиотеке Range [1] есть понятие адаптеров [2], которые могут применяться к любому диапазону и выполнять фильтрацию, преобразование и т. Д. С этой библиотекой исходный пример Haskell будет выглядеть так (с использованием Boost.Lambda [3] для анонимной фильтрации и функции преобразования) ( Полный пример ):
    counting_range(1,10) | filtered( _1*_1 > 3 ) | transformed(ret<int>( _1*2 ))
  • Эта реализация использует макрос и перегружает оператор <<. Он оценивает любое выражение, допустимое внутри 'if', и может быть выбрано любое имя переменной. Однако это небезопасно . Пример использования:
list<int> N;
list<double> 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) { x *= 2; return true; }

list<int> 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-C ++ из XSD. Нет абсолютно никакой строковой кодировки. Даже имена тегов xml являются классами, поэтому опечатки недопустимы. Если выражение LEESA формирует неправильный путь, которого нет в модели данных, компилятор C ++ отклонит код.
    Рассмотрим каталог xml.
<catalog>
  <book>
    <title>Hamlet</title>
    <price>9.99</price>
    <author>
      <name>William Shakespeare</name>
      <country>England</country>
    </author>
  </book>
  <book>...</book>
...
</catalog>

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

// Equivalent X-Path: "catalog/book/author/name"
std::vector<name> author_names = 
evaluate(root, catalog_ >> book_ >> author_ >> name_);

// Equivalent X-Path: "catalog//name"
std::vector<name> author_names = 
evaluate(root, catalog_ >> DescendantsOf(catalog_, name_));

// Equivalent X-Path: "catalog//author[country=="England"]"
std::vector<name> author_names = 
evaluate(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). «Функциональные внутренности системы запросов Kleisli» . Материалы пятой международной конференции ACM SIGPLAN по функциональному программированию . Международная конференция по функциональному программированию. С. 1–10.

Haskell

OCaml

Python

Common Lisp

Clojure

Аксиома

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