Zrozumienie listy - List comprehension

Listowego jest składniowym konstrukcja dostępna w niektórych językach programowania do tworzenia listy na podstawie istniejących list . Jest to forma matematycznej notacji konstruktora zbiorów ( zbioru rozumienia ) w odróżnieniu od użycia funkcji mapowania i filtrowania .

Przegląd

Rozważmy następujący przykład w notacji konstruktora zestawów .

lub często

Można to odczytać, " jest zbiorem wszystkich liczb "2 razy " TAKIEGO, KTÓRY JEST ELEMENTEM lub CZŁONKIEM zbioru liczb naturalnych ( ), ORAZ kwadrat jest większy niż .

Najmniejsza liczba naturalna, x = 1, nie spełnia warunku x 2 > 3 (warunek 1 2 > 3 jest fałszywy), więc 2 ·1 nie jest zawarte w S. Następna liczba naturalna, 2, spełnia warunek ( 2 2 >3) jak każda inna liczba naturalna. Zatem x składa się z 2, 3, 4, 5... Ponieważ zbiór S składa się ze wszystkich liczb "2 razy x" jest to dane przez S = {4, 6, 8, 10,...}. Innymi słowy, S jest zbiorem wszystkich liczb parzystych większych od 2.

W tej opisanej wersji przykładu:

  • jest zmienną reprezentującą elementy zbioru wejściowego.
  • reprezentuje zbiór wejściowy, który w tym przykładzie jest zbiorem liczb naturalnych
  • jest wyrażeniem predykatu działającym jako filtr na elementach zbioru wejściowego.
  • jest wyrażeniem wyjściowym tworzącym elementy nowego zestawu z elementów zestawu wejściowego, które spełniają wymagania wyrażenia predykatu.
  • nawiasy klamrowe wskazują, że wynikiem jest zbiór
  • pionowa kreska jest czytana jako „TAK TO”. Słupek i dwukropek „:” są używane zamiennie.
  • przecinki oddzielają predykaty i mogą być odczytywane jako „ORAZ”.

Lista składana ma te same komponenty składniowe, które reprezentują generowanie listy w kolejności z listy wejściowej lub iteratora :

  • Zmienna reprezentująca członków listy wejściowej.
  • Lista wejść (lub iterator).
  • Opcjonalne wyrażenie predykatu.
  • I wyrażenie wyjściowe tworzące elementy listy wyjściowej z elementów iterowalnych danych wejściowych, które spełniają predykat.

Kolejność generowania elementów listy wyjściowej jest oparta na kolejności elementów na wejściu.

W składni listy składanej Haskella ta konstrukcja konstruktora zestawów zostałaby napisana w podobny sposób, jako:

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

W tym przypadku lista [0..]reprezentuje , reprezentuje predykat i reprezentuje wyrażenie wyjściowe. x^2>32*x

Listy składane dają wyniki w określonej kolejności (w przeciwieństwie do członków zbiorów); a listy złożone mogą generować elementy listy w kolejności, zamiast tworzyć całość listy, umożliwiając w ten sposób, na przykład, poprzednią definicję Haskella elementów listy nieskończonej.

Historia

Istnienie pokrewnych konstrukcji poprzedza użycie terminu „zrozumienie listy”. Język programowania SETL (1969) ma konstrukcję zestawu, która jest podobna do wyrażeń listowych. Np. ten kod wypisuje wszystkie liczby pierwsze od 2 do N :

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

System algebry komputerowej AXIOM (1973) ma podobną konstrukcję, która przetwarza strumienie .

Pierwsze użycie terminu „zrozumienie” dla takich konstrukcji miało miejsce w opisie ich funkcjonalnego języka programowania NPL autorstwa Roda Burstall i Johna Darlingtona z 1977 roku. W swojej retrospektywie „Some History of Functional Programming Languages” David Turner wspomina:

NPL został zaimplementowany w POP2 przez Burstall i wykorzystany w pracach Darlingtona nad transformacją programu (Burstall i Darlington 1977). Język był pierwszego rzędu, silnie (ale nie polimorficznie) typowany, czysto funkcjonalny, call-by-value. Miał również „ustawione wyrażenia”, np

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

W przypisie dołączonym do terminu „zrozumienie listy” Turner również zauważa:

Początkowo nazwałem te wyrażenia ZF , odniesieniem do teorii mnogości Zermelo-Frankela — to Phil Wadler ukuł lepsze rozumienie listy terminów .

Praca Burstalla i Darlingtona z NPL wpłynęła na wiele języków programowania funkcjonalnego w latach 80., ale nie wszystkie obejmowały rozumienie list. Wyjątkiem był wpływowy, czysty, leniwy, funkcjonalny język programowania Turnera Miranda , wydany w 1985 roku. Później rozwinięty standardowy, czysty, leniwy język funkcjonalny Haskell zawiera wiele cech Mirandy, w tym listy wyrażeń.

Zrozumienia zostały zaproponowane jako notacja zapytań dla baz danych i zostały zaimplementowane w języku zapytań bazy danych Kleisli .

Przykłady w różnych językach programowania

julia: 12x12 multiplication matrix 
[i*j for i=1:12,j=1:12]

Podobne konstrukcje

Zrozumienie monady

W Haskell, rozumienie monad jest uogólnieniem rozumienia listowego na inne monady w programowaniu funkcjonalnym .

Ustaw rozumienie

Wersje 3.xi 2.7 języka Python wprowadzają składnię dla zbioru rozumienia. Podobnie w formie do wyrażeń listowych, wyrażenia zbiorowe generują zestawy Pythona zamiast list.

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

Zrozumienia zestawu rakietowego generują zestawy rakietowe zamiast list.

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

Rozumienie słownika

Wersje 3.xi 2.7 języka Python wprowadziły nową składnię dla wyrażeń słownikowych , podobną w formie do wyrażeń listowych, ale generującą dyktowania Pythona zamiast list.

>>> s = {key: val for key, val in enumerate('ABCD') if val not in 'CB'}
>>> s
{0: 'A', 3: 'D'}
>>>

Tabele skrótu Racket generują tabele hash Racket (jedna implementacja typu słownika Racket).

(for/hash ([(val key) (in-indexed "ABCD")]
           #:unless (member val (string->list "CB")))
  (values key val))

Równoległe rozumienie listy

Glasgow Haskell Compiler ma rozszerzenie o nazwie lista równolegle ze zrozumieniem (znany również jako zip-zrozumieniem ), który umożliwia wiele niezależnych gałęzi kwalifikacyjnych w składni lista zrozumieniem. Podczas gdy kwalifikatory oddzielone przecinkami są zależne („zagnieżdżone”), gałęzie kwalifikatorów oddzielone potokami są oceniane równolegle (nie dotyczy to żadnej formy wielowątkowości: oznacza to jedynie, że gałęzie są skompresowane ).

-- 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)]

Standardowa biblioteka wyrażeń Racketa zawiera równoległe i zagnieżdżone wersje jego wyrażeń, rozróżniane w nazwie przez „for” i „for*”. Na przykład, wyrażenia wektorowe „dla/wektora” i „dla*/wektora” tworzą wektory przez równoległe i zagnieżdżone iteracje po sekwencjach. Poniżej znajduje się kod Racketa dla przykładów rozumienia listy Haskella.

> (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))

W Pythonie moglibyśmy zrobić tak:

# 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)]

W Julii praktycznie te same wyniki można osiągnąć w następujący sposób:

# 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)]

z tą tylko różnicą, że zamiast list w Julii mamy tablice.

XQuery i XPath

Podobnie jak oryginalne użycie NPL, są to zasadniczo języki dostępu do baz danych.

To sprawia, że ​​koncepcja rozumienia jest ważniejsza, ponieważ jest niewykonalne obliczeniowo, aby pobrać całą listę i operować na niej (początkowa „cała lista” może być całą bazą danych XML).

W XPath wyrażenie:

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

jest koncepcyjnie oceniany jako seria „kroków”, w których każdy krok tworzy listę, a następny krok stosuje funkcję filtrowania do każdego elementu w danych wyjściowych poprzedniego kroku.

W XQuery dostępna jest pełna ścieżka XPath, ale używane są również instrukcje FLWOR , co jest potężniejszą konstrukcją rozumienia.

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

Tutaj //książka XPath jest oceniana w celu utworzenia sekwencji (aka listy); klauzula where jest funkcjonalnym „filtrem”, kolejność według sortuje wynik, a <shortBook>...</shortBook>fragment XML jest w rzeczywistości anonimową funkcją, która buduje/transformuje XML dla każdego elementu w sekwencji przy użyciu podejścia „map” występującego w innych językach funkcjonalnych.

Tak więc w innym języku funkcjonalnym powyższa instrukcja FLWOR może być zaimplementowana w następujący sposób:

map(
  newXML(shortBook, newXML(title, $1.title), newXML(firstPara, $1...))
  filter(
    lt($1.pages, 400),
    xpath(//book)
  )
)

LINQ w C#

C# 3.0 ma grupę powiązanych funkcji o nazwie LINQ , która definiuje zestaw operatorów zapytań do manipulowania wyliczeniami obiektów.

var s = Enumerable.Range(0, 100).Where(x => x * x > 3).Select(x => x * 2);

Oferuje również alternatywną składnię rozumienia, przypominającą SQL:

var s = from x in Enumerable.Range(0, 100) where x * x > 3 select x * 2;

LINQ zapewnia możliwość nad typowymi implementacjami ze zrozumieniem list. Gdy obiekt główny zrozumienia implementuje IQueryableinterfejs, a nie tylko wykonuje powiązane metody zrozumienia, cała sekwencja poleceń jest konwertowana na obiekt abstrakcyjnego drzewa składni (AST), który jest przekazywany do obiektu IQueryable w celu zinterpretowania i wykonania .

Dzięki temu IQueryable może m.in.:

  • przepisać niezgodne lub nieefektywne rozumienie
  • przetłumacz AST na inny język zapytań (np. SQL) w celu wykonania

C++

C++ nie ma żadnych funkcji językowych bezpośrednio wspierających rozumienie list, ale przeciążanie operatorów (np. przeciążanie |, >>, >>=) zostało z powodzeniem użyte w celu zapewnienia wyrazistej składni dla "osadzanych" języków specyficznych dla domeny zapytań (DSL). Alternatywnie, listy składane mogą być skonstruowane przy użyciu idiomu erase-remove, aby wybrać elementy w kontenerze i algorytmu STL for_each, aby je przekształcić.

#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
}

Istnieje pewien wysiłek w dostarczaniu C++ z konstrukcjami/składniami składającymi się z listów podobnymi do notacji konstruktora zestawów.

  • W trybie doładowania . Biblioteka Range [1] istnieje pojęcie adapterów [2], które można zastosować do dowolnego zakresu i wykonać filtrowanie, transformację itp. Z tą biblioteką wyglądałby oryginalny przykład Haskella (przy użyciu Boost.Lambda [3] do anonimowego filtrowania i przekształcanie funkcji) ( Pełny przykład ):
    counting_range(1,10) | filtered( _1*_1 > 3 ) | transformed(ret<int>( _1*2 ))
    
  • Ta implementacja używa makra i przeciąża operator <<. Ocenia każde wyrażenie poprawne wewnątrz 'if' i można wybrać dowolną nazwę zmiennej. Nie jest to jednak bezpieczne dla wątków . Przykład użycia:
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)
  • Ta implementacja zapewnia krojenie głowy/ogonu przy użyciu klas i przeciążania operatorów, a | operator do filtrowania list (za pomocą funkcji). Przykład użycia:
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) to osadzony DSL w C++, który implementuje zapytania podobne do X-Path przy użyciu przeciążania operatorów. Zapytania są wykonywane na bogato typowanych drzewach xml uzyskanych przy użyciu wiązania xml-to-c++ z XSD. Nie ma absolutnie żadnego kodowania ciągów. Nawet nazwy tagów xml są klasami i dlatego nie ma mowy o literówkach. Jeśli wyrażenie LEESA tworzy niepoprawną ścieżkę, która nie istnieje w modelu danych, kompilator C++ odrzuci kod.
    Rozważ katalog xml.
<catalog>
  <book>
    <title>Hamlet</title>
    <price>9.99</price>
    <author>
      <name>William Shakespeare</name>
      <country>England</country>
    </author>
  </book>
  <book>...</book>
...
</catalog>

LEESA zapewnia >>XPath / separator. Separator // XPath, który „pomija” węzły pośrednie w drzewie, jest zaimplementowany w LEESA przy użyciu tak zwanego programowania strategicznego. W poniższym przykładzie katalog_, książka_, autor_ i nazwa_ są odpowiednio wystąpieniami klas katalog, książka, autor i nazwa.

// 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_);

Zobacz też

  • Instrukcja SELECT wraz z jej klauzulami FROM i WHERE w SQL

Uwagi i referencje

Haskell

OCaml

Pyton

Wspólne seplenienie

Clojure

Aksjomat

Linki zewnętrzne