Compreensão da lista - List comprehension

A compreensão de lista é uma construção sintática disponível em algumas linguagens de programação para criar uma lista com base em listas existentes . Ele segue a forma da notação matemática do construtor de conjuntos ( compreensão de conjuntos ), distinta do uso de funções de mapa e filtro .

Visão geral

Considere o seguinte exemplo na notação set-builder .

ou frequentemente

Isso pode ser lido, " é o conjunto de todos os números" 2 vezes "TAL QUE é um ELEMENTO ou MEMBRO do conjunto de números naturais ( ), E ao quadrado é maior que ."

O menor número natural, x = 1, não satisfaz a condição x 2 > 3 (a condição 1 2 > 3 é falsa), então 2 · 1 não está incluído em S. O próximo número natural, 2, satisfaz a condição ( 2 2 > 3) assim como todos os outros números naturais. Assim, x consiste em 2, 3, 4, 5 ... Dado que o conjunto S consiste em todos os números "2 vezes x", é dado por S = {4, 6, 8, 10, ...}. S é, em outras palavras, o conjunto de todos os números pares maiores que 2.

Nesta versão anotada do exemplo:

  • é a variável que representa os membros de um conjunto de entrada.
  • representa o conjunto de entrada, que neste exemplo é o conjunto de números naturais
  • é uma expressão de predicado que atua como um filtro nos membros do conjunto de entrada.
  • é uma expressão de saída que produz membros do novo conjunto a partir de membros do conjunto de entrada que satisfazem a expressão de predicado.
  • colchetes indicam que o resultado é um conjunto
  • a barra vertical é lida como "TAL ISSO". A barra e os dois pontos ":" são usados ​​alternadamente.
  • vírgulas separam os predicados e podem ser lidas como "AND".

Uma compreensão de lista tem os mesmos componentes sintáticos para representar a geração de uma lista em ordem a partir de uma lista de entrada ou iterador :

  • Uma variável que representa os membros de uma lista de entrada.
  • Uma lista de entrada (ou iterador).
  • Uma expressão de predicado opcional.
  • E uma expressão de saída que produz membros da lista de saída a partir de membros do iterável de entrada que satisfazem o predicado.

A ordem de geração de membros da lista de saída é baseada na ordem dos itens na entrada.

Na sintaxe de compreensão de lista de Haskell , esta construção set-builder seria escrita de forma semelhante, como: 

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

Aqui, a lista [0..]representa , representa o predicado e representa a expressão de saída. x^2>32*x

As compreensões de lista fornecem resultados em uma ordem definida (ao contrário dos membros de conjuntos); e as compreensões de lista podem gerar os membros de uma lista em ordem, em vez de produzir a lista inteira, permitindo assim, por exemplo, a definição anterior de Haskell dos membros de uma lista infinita.

História

A existência de construções relacionadas é anterior ao uso do termo "Compreensão de lista". A linguagem de programação SETL (1969) tem uma construção de formação de conjunto que é semelhante às compreensões de lista. Por exemplo, este código imprime todos os números primos de 2 a N : 

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

O sistema de álgebra computacional AXIOM (1973) tem uma construção semelhante que processa fluxos .

O primeiro uso do termo "compreensão" para tais construções foi na descrição de Rod Burstall e John Darlington de sua linguagem de programação funcional NPL de 1977. Em sua retrospectiva "Alguma História das Linguagens de Programação Funcional", David Turner relembra:

O NPL foi implementado no POP2 pela Burstall e usado para o trabalho de Darlington na transformação do programa (Burstall & Darlington 1977). A linguagem era de primeira ordem, fortemente (mas não polimorficamente) tipada, puramente funcional, chamada por valor. Ele também tinha "expressões definidas", por exemplo 

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

Em uma nota de rodapé anexada ao termo "compreensão de lista", Turner também observa

Inicialmente chamei essas expressões ZF , uma referência à teoria dos conjuntos de Zermelo-Frankel - foi Phil Wadler quem cunhou o melhor termo compreensão de lista .

O trabalho de Burstall e Darlington com NPL influenciou muitas linguagens de programação funcionais durante a década de 1980, mas nem todas incluíram compreensões de lista. Uma exceção foi a influente linguagem de programação funcional, pura, preguiçosa e preguiçosa de Turner, Miranda , lançada em 1985. A linguagem funcional puramente preguiçosa padrão subsequentemente desenvolvida, Haskell, inclui muitos dos recursos de Miranda, incluindo compreensões de lista.

As compreensões foram propostas como uma notação de consulta para bancos de dados e foram implementadas na linguagem de consulta de banco de dados Kleisli .

Exemplos em diferentes linguagens de programação

Artigo principal: Comparação de linguagens de programação (compreensão de lista) 
julia: 12x12 multiplication matrix 
[i*j for i=1:12,j=1:12]

Construções semelhantes

Compreensão da mônada

Em Haskell, uma compreensão de mônada é uma generalização da compreensão de lista para outras mônadas na programação funcional .

Definir compreensão

As versões 3.xe 2.7 da linguagem Python introduzem a sintaxe para compreensão de conjuntos . De forma semelhante às compreensões de lista, as compreensões de conjunto geram conjuntos Python em vez de listas. 

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

As compreensões de conjunto de raquete geram conjuntos de raquete em vez de listas. 

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

Compreensão de dicionário

As versões 3.xe 2.7 da linguagem Python introduziram uma nova sintaxe para as compreensões de dicionário , semelhante na forma às compreensões de lista, mas que geram ditos Python em vez de listas. 

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

As compreensões de tabela hash Racket geram tabelas hash Racket (uma implementação do tipo de dicionário Racket). 

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

Compreensão de lista paralela

O Compilador Glasgow Haskell tem uma extensão chamada compreensão de lista paralela (também conhecida como compreensão zip ) que permite vários ramos independentes de qualificadores dentro da sintaxe de compreensão de lista. Enquanto os qualificadores separados por vírgulas são dependentes ("aninhados"), os ramos do qualificador separados por barras verticais são avaliados em paralelo (isso não se refere a qualquer forma de multithreadedness: significa apenas que os ramos são compactados ). 

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

A biblioteca padrão de compreensões do Racket contém versões paralelas e aninhadas de suas compreensões, distinguidas por "para" vs "para *" no nome. Por exemplo, as compreensões de vetor "for / vector" e "for * / vector" criam vetores por iteração paralela versus aninhada sobre sequências. A seguir está o código Racket para os exemplos de compreensão da lista 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))

Em Python, poderíamos fazer o seguinte: 

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

Em Julia, praticamente os mesmos resultados podem ser alcançados da seguinte forma: 

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

com a única diferença de que em vez de listas, em Julia, temos arrays.

XQuery e XPath

Como o uso do NPL original, essas são fundamentalmente linguagens de acesso a banco de dados.

Isso torna o conceito de compreensão mais importante, porque é computacionalmente inviável recuperar a lista inteira e operá-la (a 'lista inteira' inicial pode ser um banco de dados XML inteiro).

No XPath, a expressão: 

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

é avaliada conceitualmente como uma série de "etapas" em que cada etapa produz uma lista e a próxima etapa aplica uma função de filtro a cada elemento na saída da etapa anterior.

Em XQuery, XPath completo está disponível, mas as instruções FLWOR também são usadas, que é uma construção de compreensão mais poderosa. 

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

Aqui, o livro XPath // é avaliado para criar uma sequência (também conhecida como lista); a cláusula where é um "filtro" funcional, a ordem por classifica o resultado e o <shortBook>...</shortBook>fragmento XML é na verdade uma função anônima que constrói / transforma XML para cada elemento na sequência usando a abordagem de 'mapa' encontrada em outras linguagens funcionais.

Portanto, em outra linguagem funcional, a instrução FLWOR acima pode ser implementada assim: 

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

LINQ em C #

C # 3.0 tem um grupo de recursos relacionados chamado LINQ , que define um conjunto de operadores de consulta para manipular enumerações de objetos. 

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

Ele também oferece uma sintaxe de compreensão alternativa, uma reminiscência de SQL: 

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

LINQ fornece um recurso sobre implementações de compreensão de lista típicas. Quando o objeto raiz da compreensão implementa a IQueryableinterface, em vez de apenas executar os métodos encadeados da compreensão, toda a sequência de comandos é convertida em um objeto de árvore de sintaxe abstrata (AST), que é passado ao objeto IQueryable para interpretar e executar .

Isso permite, entre outras coisas, que o IQueryable

  • reescrever uma compreensão incompatível ou ineficiente
  • traduzir o AST para outra linguagem de consulta (por exemplo, SQL) para execução

C ++

C ++ não tem qualquer língua recursos de suporte diretamente compreensões lista, mas sobrecarga de operador (por exemplo, sobrecarga |, >>, >>=) tem sido utilizada com sucesso para fornecer sintaxe expressiva para consulta "embutidos" linguagens específicas de domínio (DSL). Como alternativa, as compreensões de lista podem ser construídas usando o idioma erase-remove para selecionar elementos em um contêiner e o algoritmo STL for_each para transformá-los. 

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

Há algum esforço em fornecer ao C ++ construções / sintaxe de compreensão de lista semelhante à notação do construtor de conjunto.

  • Em Boost . Biblioteca Range [1] há uma noção de adaptadores [2] que podem ser aplicados a qualquer intervalo e fazer filtragem, transformação etc. Com esta biblioteca, o exemplo original de Haskell seria semelhante a (usando Boost.Lambda [3] para filtragem anônima e funções de transformação) ( exemplo completo ):
    counting_range(1,10) | filtered( _1*_1 > 3 ) | transformed(ret<int>( _1*2 ))
  • Esta implementação usa uma macro e sobrecarrega o operador <<. Ele avalia qualquer expressão válida dentro de um 'if', e qualquer nome de variável pode ser escolhido. Não é threadsafe , no entanto. Exemplo de uso:
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)
  • Essa implementação fornece corte de cabeça / cauda usando classes e sobrecarga de operador, e o | operador para filtrar listas (usando funções). Exemplo de uso:
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;
  • Linguagem para Embedded Query and Traversal (LEESA) é um DSL embutido em C ++ que implementa consultas do tipo X-Path usando sobrecarga de operador. As consultas são executadas em árvores xml ricamente tipadas obtidas usando ligação xml-to-c ++ de um XSD. Não há absolutamente nenhuma codificação de string. Mesmo os nomes das tags xml são classes e, portanto, não há como erros de digitação. Se uma expressão LEESA formar um caminho incorreto que não existe no modelo de dados, o compilador C ++ rejeitará o código.
    Considere um xml de catálogo.
<catalog>
  <book>
    <title>Hamlet</title>
    <price>9.99</price>
    <author>
      <name>William Shakespeare</name>
      <country>England</country>
    </author>
  </book>
  <book>...</book>
...
</catalog>

A LEESA fornece >>XPaths / separadores. O // separador do XPath que "pula" os nós intermediários na árvore é implementado no LEESA usando o que é conhecido como Programação Estratégica. No exemplo abaixo, catalog_, book_, author_ e name_ são instâncias de catalog, book, author e name classes, respectivamente. 

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

Veja também

Notas e referências

Haskell

OCaml

Pitão

Lisp Comum

Clojure

Axioma

links externos