Comprensión de listas

Construcción sintáctica para crear una lista a partir de listas existentes

Una comprensión de listas es una construcción sintáctica disponible en algunos lenguajes de programación para crear una lista a partir de listas existentes . Sigue la forma de la notación matemática de creación de conjuntos ( comprensión de conjuntos ), a diferencia del uso de funciones de mapa y filtro .

Descripción general

Considere el siguiente ejemplo en notación matemática de construcción de conjuntos .

${\displaystyle S=\{2\cdot x\mid x\in \mathbb {N} ,\ x^{2}>3\}}$

o a menudo

${\displaystyle S=\{2\cdot x:x\in \mathbb {N} ,\ x^{2}>3\}}$

Esto se puede leer, " es el conjunto de todos los números "2 veces " TAL QUE es un ELEMENTO o MIEMBRO del conjunto de números naturales ( ), Y al cuadrado es mayor que ." ${\displaystyle S}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle \mathbb {N} }$ ${\displaystyle x}$ ${\displaystyle 3}$

El número natural más pequeño, x = 1, no satisface la condición x ² > 3 (la condición 1 ² > 3 es falsa), por lo que 2 · 1 no está incluido en S. El siguiente número natural, 2, sí satisface la condición (2 ² > 3), al igual que cualquier otro número natural. Por lo tanto, x consta de 2, 3, 4, 5... Como el conjunto S consta de todos los números "2 por x", está dado por S = {4, 6, 8, 10,...}. S es, en otras palabras, el conjunto de todos los números pares mayores que 2.

En esta versión anotada del ejemplo:

${\displaystyle 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}}}\}}$

• ${\displaystyle x}$es la variable que representa a los miembros de un conjunto de entrada.
• ${\displaystyle \mathbb {N} }$representa el conjunto de entrada, que en este ejemplo es el conjunto de números naturales
• ${\displaystyle x^{2}>3}$es una expresión de predicado que actúa como un filtro en los miembros del conjunto de entrada.
• ${\displaystyle 2\cdot x}$es una expresión de salida que produce miembros del nuevo conjunto a partir de miembros del conjunto de entrada que satisfacen la expresión de predicado.
• ${\displaystyle \{\}}$Las llaves indican que el resultado es un conjunto.
• ${\displaystyle \mid }$ ${\displaystyle ,}$La barra vertical se lee como "TAL QUE". La barra y los dos puntos : " se utilizan indistintamente.
• Las comas separan los predicados y pueden leerse como "Y".

Una comprensión de lista tiene los mismos componentes sintácticos para representar la generación de una lista en orden a partir de una lista de entrada o un iterador :

• Una variable que representa a los miembros de una lista de entrada.
• Una lista de entrada (o iterador).
• Una expresión de predicado opcional.
• Y una expresión de salida que produce miembros de la lista de salida a partir de miembros del iterable de entrada que satisfacen el predicado.

El orden de generación de los miembros de la lista de salida se basa en el orden de los elementos de la entrada.

En la sintaxis de comprensión de listas de Haskell , esta construcción generadora de conjuntos se escribiría de manera similar, como:

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

Aquí, la lista [0..]representa , representa el predicado y representa la expresión de salida. ${\displaystyle \mathbb {N} }$x^2>32*x

Las comprensiones de listas dan resultados en un orden definido (a diferencia de los miembros de los conjuntos); y las comprensiones de listas pueden generar los miembros de una lista en orden, en lugar de producir la totalidad de la lista, permitiendo así, por ejemplo, la definición previa de Haskell de los miembros de una lista infinita.

Historia

La existencia de construcciones relacionadas es anterior al uso del término "comprensión de listas". El lenguaje de programación SETL (1969) tiene una construcción de formación de conjuntos que es similar a las listas por comprensión. Por ejemplo, este código imprime todos los números primos de 2 a N :

imprimir([n en [2..N] | para todo m en {2..n - 1} | n mod m > 0]);

El sistema de álgebra computacional AXIOM (1973) tiene una construcción similar que procesa flujos .

El primer uso del término "comprensión" para tales construcciones fue en la descripción de Rod Burstall y John Darlington de su lenguaje de programación funcional NPL de 1977. En su retrospectiva "Some History of Functional Programming Languages", ^[1] David Turner recuerda:

Burstall implementó NPL en POP2 y lo utilizó para el trabajo de Darlington sobre transformación de programas (Burstall y Darlington 1977). El lenguaje era de primer orden, fuertemente tipado (pero no polimórficamente), puramente funcional, de llamada por valor. También tenía "expresiones de conjunto", por ejemplo

setofeven(X) <= <:x : x en X y even(x):>}}

En una nota al pie adjunta al término "comprensión de lista", Turner también señala

Inicialmente llamé a estas expresiones ZF , una referencia a la teoría de conjuntos de Zermelo-Fraenkel ; fue Phil Wadler quien acuñó el término más adecuado, comprensión de listas .

El trabajo de Burstall y Darlington con NPL influyó en muchos lenguajes de programación funcional durante la década de 1980, pero no todos incluían listas por comprensión. Una excepción fue Miranda , el influyente lenguaje de programación funcional puro y perezoso de Turner , publicado en 1985. El lenguaje funcional puro y perezoso desarrollado posteriormente, Haskell, incluye muchas de las características de Miranda, incluidas las listas por comprensión.

Las comprensiones se propusieron como una notación de consulta para bases de datos ^[2] y se implementaron en el lenguaje de consulta de bases de datos Kleisli . ^[3]

Ejemplos en diferentes lenguajes de programación

Construcciones similares

Comprensión de mónadas

En Haskell, una comprensión de mónada es una generalización de la comprensión de lista a otras mónadas en programación funcional .

Comprensión de conjuntos

El lenguaje Python introduce una sintaxis para las comprensiones de conjuntos a partir de la versión 2.7. De forma similar a las comprensiones de listas, las comprensiones de conjuntos generan conjuntos de Python en lugar de listas.

>>> s  =  { v  para  v  en  'ABCDABCD'  si  v  no está  en  'CB' } >>> print ( s ) {'A', 'D'} >>> type ( s ) <class 'set'> >>>

Las comprensiones de conjuntos de raquetas generan conjuntos de raquetas en lugar de listas.

( para/establecer ([ v "ABCDABCD" ] #:a menos que ( miembro v ( cadena->lista "CB" ))) v ))        

Comprensión del diccionario

El lenguaje Python introdujo una nueva sintaxis para comprensiones de diccionario en la versión 2.7, similar en forma a las comprensiones de lista pero que generan diccionarios de Python en lugar de listas.

>>> s  =  { clave :  val  para  clave ,  val  en  enumerate ( 'ABCD' )  si  val  no está  en  'CB' } >>> s {0: 'A', 3: 'D'} >>>

Las comprensiones de tabla hash de Racket generan tablas hash de Racket (una implementación del tipo de diccionario Racket).

( para/hash ([( val clave ) ( indexado en "ABCD" )] #:a menos que ( miembro val ( cadena->lista "CB" ))) ( valores clave val ))            

Comprensión de listas paralelas

El compilador Glasgow Haskell tiene una extensión llamada comprensión de listas paralelas (también conocida como zip-comprehension ) que permite múltiples ramas independientes de calificadores dentro de la sintaxis de comprensión de listas. Mientras que los calificadores separados por comas son dependientes ("anidados"), las ramas de calificadores separadas por barras verticales se evalúan en paralelo (esto no se refiere a ninguna forma de multiproceso: simplemente significa que las ramas están comprimidas ).

-- comprensión de listas regular a = [( x , y ) | x <- [ 1 .. 5 ], y <- [ 3 .. 5 ]] -- [(1,3),(1,4),(1,5),(2,3),(2,4) ...         -- comprensión de lista comprimida b = [( x , y ) | ( x , y ) <- zip [ 1 .. 5 ] [ 3 .. 5 ]] -- [(1,3),(2,4),(3,5)]        -- comprensión de listas paralelas c = [( x , y ) | x <- [ 1 .. 5 ] | y <- [ 3 .. 5 ]] -- [(1,3),(2,4),(3,5)]          

La biblioteca estándar de comprensiones de Racket contiene versiones paralelas y anidadas de sus comprensiones, que se distinguen por "for" y "for*" en el nombre. Por ejemplo, las comprensiones de vectores "for/vector" y "for*/vector" crean vectores mediante iteración paralela y anidada sobre secuencias. El siguiente es el código de Racket para los ejemplos de comprensión de listas de Haskell.

> ( para*/lista ([ x ( en el rango 1 6 )] [ y ( en el rango 3 6 )]) ( lista 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 )) > ( para/lista ([ x ( en el rango 1 6 )] [ y ( en el rango 3 6 )]) ( lista x y )) ' (( 1 3 ) ( 2 4 ) ( 3 5 ))                                                          

En Python, podríamos hacer lo siguiente:

>>> # comprensión de listas regular >>> a  =  [( x ,  y )  para  x  en  rango ( 1 ,  6 )  para  y  en  rango ( 3 ,  6 )] [(1, 3), (1, 4), (1, 5), (2, 3), (2, 4), ... >>> >>> # comprensión de listas paralelas/comprimidas >>> b  =  [ x  para  x  en  zip ( rango ( 1 ,  6 ),  rango ( 3 ,  6 ))] [(1, 3), (2, 4), (3, 5)]

En Julia se pueden conseguir prácticamente los mismos resultados de la siguiente manera:

# comprensión de matriz regular >>> a = [( x , y ) para x en 1 : 5 para y en 3 : 5 ]            # comprensión de matriz paralela/comprimida >>> b = [ x for x in zip ( 1 : 3 , 3 : 5 )]        

con la única diferencia que en lugar de listas, en Julia tenemos arrays.

XQuery y XPath

Al igual que el uso original de NPL, estos son fundamentalmente lenguajes de acceso a bases de datos.

Esto hace que el concepto de comprensión sea más importante, porque es computacionalmente inviable recuperar la lista completa y operar sobre ella (la "lista completa" inicial puede ser una base de datos XML completa).

En XPath, la expresión:

/ biblioteca / libro // párrafo [ @style = 'first-in-chapter' ]

se evalúa conceptualmente como una serie de "pasos" donde cada paso produce una lista y el siguiente paso aplica una función de filtro a cada elemento en la salida del paso anterior. ^[4]

En XQuery, está disponible el XPath completo, pero también se utilizan declaraciones FLWOR , que es una construcción de comprensión más poderosa. ^[5]

para $ b en // libro donde $ b [ @pages < 400 ] ordenar por $ b // título devolver <shortBook> <title> { $ b // título } </title> <firstPara> {( $ libro // párrafo )[ 1 ]} </firstPara> </shortBook>           

Aquí se evalúa el XPath //book para crear una secuencia (también conocida como lista); la cláusula where es un "filtro" funcional, el orden por ordena el resultado y el <shortBook>...</shortBook>fragmento XML es en realidad una función anónima que crea/transforma XML para cada elemento en la secuencia utilizando el enfoque "mapa" que se encuentra en otros lenguajes funcionales.

Entonces, en otro lenguaje funcional, la declaración FLWOR anterior se puede implementar de la siguiente manera:

mapa ( newXML ( shortBook , newXML ( título , $ 1. título ), newXML ( firstPara , $ 1...)) filtro ( lt ( $ 1. páginas , 400 ), xpath (// libro ) ) )          

LINQ en C#

C# 3.0 tiene un grupo de características relacionadas llamadas LINQ , que define un conjunto de operadores de consulta para manipular enumeraciones de objetos.

var s = Enumerable . Rango ( 0 , 100 ). Donde ( x => x * x > 3 ). Seleccionar ( x => x * 2 );              

También ofrece una sintaxis de comprensión alternativa, que recuerda a SQL:

var s = de x en Enumerable . Rango ( 0 , 100 ) donde x * x > 3 seleccionar x * 2 ;                 

LINQ ofrece una capacidad superior a las implementaciones de comprensión de listas típicas. Cuando el objeto raíz de la comprensión implementa la IQueryableinterfaz, en lugar de simplemente ejecutar los métodos encadenados de la comprensión, toda la secuencia de comandos se convierte en un objeto de árbol de sintaxis abstracta (AST), que se pasa al objeto IQueryable para que lo interprete y ejecute.

Esto permite, entre otras cosas, que IQueryable

• reescribir una comprensión incompatible o ineficiente
• traducir el AST a otro lenguaje de consulta (por ejemplo, SQL) para su ejecución

C++

C++ no tiene ninguna característica del lenguaje que admita directamente las listas por comprensión, pero la sobrecarga de operadores (por ejemplo, la sobrecarga de |, >>, >>=) se ha utilizado con éxito para proporcionar una sintaxis expresiva para lenguajes específicos del dominio (DSL) de consultas "integradas". Como alternativa, las listas por comprensión se pueden construir utilizando el modismo borrar-eliminar para seleccionar elementos en un contenedor y el algoritmo STL for_each para transformarlos.

#include <algoritmo> #include <lista> #include <numérico>   utilizando el espacio de nombres std ;  plantilla < clase C , clase P , clase T > C comprender ( C && fuente , const P & predicado , const T & transformación ) { // inicializar destino C d = forward < C > ( fuente );                   // filtrar elementos d . erase ( remove_if ( begin ( d ), end ( d ), predicate ), end ( d ));     // aplicar transformación for_each ( begin ( d ), end ( d ), transformación );    devolver d ; } int main () { list < int > range ( 10 ); // range es una lista de 10 elementos, todos con iota cero ( begin ( range ), end ( range ), 1 ); // range ahora contiene 1, 2, ..., 10         lista < int > resultado = comprender ( rango , []( int x ) { devolver x * x <= 3 ; }, []( int & x ) { x *= 2 ; }); // el resultado ahora contiene 4, 6, ..., 20 }                      

Se ha hecho un esfuerzo para proporcionar a C++ construcciones/sintaxis de comprensión de listas similares a la notación del generador de conjuntos.

• En la biblioteca Boost.Range [1] existe una noción de adaptadores [2] que se pueden aplicar a cualquier rango y realizar filtrado, transformación, etc. Con esta biblioteca, el ejemplo original de Haskell se vería así (usando Boost.Lambda [3] para funciones de filtrado y transformación anónimas) (Ejemplo completo):

  rango_conteo ( 1 , 10 ) | filtrado ( _1 * _1 > 3 ) | transformado ( ret < int > ( _1 * 2 ))          

• Esta implementación ^[6] utiliza una macro y sobrecarga el operador <<. Evalúa cualquier expresión válida dentro de un 'if' y se puede elegir cualquier nombre de variable. Sin embargo, no es segura para subprocesos . Ejemplo de uso:

lista < int > N ; lista < double > S ;  para ( int i = 0 ; i < 10 ; i ++ ) N . push_back ( i );         S << comprensión_de_listas ( 3.1415 * x , x , N , x * x > 3 )           

• Esta implementación ^{[7] proporciona segmentación de cabecera y cola mediante clases y sobrecarga de operadores, y el operador | para filtrar listas (mediante funciones). Ejemplo de uso:}

bool even ( int x ) { devuelve x % 2 == 0 ; } bool x2 ( int & x ) { x *= 2 ; devuelve verdadero ; }                   lista < int > l , t ; int x , y ;    para ( int i = 0 ; i < 10 ; i ++ ) l .push_back ( i ) ;         ( x , t ) = l | x2 ; ( t , y ) = t ;        t = l < 9 ; t = t < 7 | par | x2 ;            

• ^{LEESA [8]} (Lenguaje para consultas y recorridos integrados ) es un DSL integrado en C++ que implementa consultas similares a X-Path mediante la sobrecarga de operadores. Las consultas se ejecutan en árboles XML de tipado enriquecido obtenidos mediante el enlace XML a C++ desde un XSD. No hay absolutamente ninguna codificación de cadenas. Incluso los nombres de las etiquetas XML son clases y, por lo tanto, no hay posibilidad de errores tipográficos. Si una expresión LEESA forma una ruta incorrecta que no existe en el modelo de datos, el compilador de C++ rechazará el código.
  Considere un catálogo XML.

<catálogo> <libro> <título> Hamlet </título> <precio> 9,99 </precio> <autor> <nombre> William Shakespeare </nombre> < país> Inglaterra </país> </autor> </libro> <libro> ... </libro>          ...</catálogo>

LEESA proporciona >>el separador / de XPath. El separador // de XPath que "omite" los nodos intermedios en el árbol se implementa en LEESA utilizando lo que se conoce como Programación Estratégica. En el ejemplo siguiente, catalog_, book_, author_ y name_ son instancias de las clases catalog, book, author y name, respectivamente.

// X-Path equivalente: "catálogo/libro/autor/nombre" std :: vector < nombre > nombres_autores = evaluar ( raíz , catálogo_ >> libro_ >> autor_ >> nombre_ );          // Ruta X equivalente: "catálogo//nombre" std :: vector < nombre > nombres_autores = evaluar ( raíz , catálogo_ >> DescendantsOf ( catálogo_ , nombre_ ));       // Ruta X equivalente: "catálogo//autor[país=="Inglaterra"]" std :: vector < nombre > nombres_autores = evaluar ( raíz , catálogo_ >> DescendantsOf ( catálogo_ , autor_ ) >> Select ( autor_ , []( const autor & a ) { return a.país () == " Inglaterra " ; }) >> nombre_ );                     

Véase también

• Notación del generador de conjuntos
• La instrucción SELECT junto con sus cláusulas FROM y WHERE en SQL

Notas y referencias

1. Turner, David (2012). "Algo de historia de los lenguajes de programación funcional" (PDF) . Simposio internacional sobre tendencias en programación funcional, Springer, Berlín, Heidelberg . pp. 1–20.
2. Comprensiones, una notación de consulta para DBPL
3. Las entrañas funcionales del sistema de consulta Kleisli
4. "2.1 Pasos de localización". Lenguaje de rutas XML (XPath) . W3C . 16 de noviembre de 1999. Archivado desde el original el 9 de diciembre de 2012. Consultado el 24 de diciembre de 2008 .
5. "Expresiones FLWOR de XQuery". W3Schools . Archivado desde el original el 8 de octubre de 2011.
6. "Comprensión de listas de una sola variable en C++ mediante macros de preprocesador". Archivado desde el original el 21 de agosto de 2011. Consultado el 9 de enero de 2011 .
7. "Listas por comprensión en C++". Archivado desde el original el 7 de julio de 2017. Consultado el 9 de enero de 2011 .
8. "Lenguaje para consultas y recorridos integrados (LEESA)".

• Comprensión de listas en el Diccionario gratuito en línea de informática, editor Denis Howe.
• Wadler, Philip (1990). "Comprensión de mónadas". Actas de la Conferencia ACM de 1990 sobre LISP y programación funcional, Niza .

Enlaces externos

• Operaciones de conjuntos similares a SQL con listas de comprensión de una sola línea en el libro de recetas de Python
• Discusión sobre las listas por comprensión en Scheme y construcciones relacionadas
• Comprensión de listas en distintos idiomas

Axioma

• Ejemplos de flujos de axiomas

Clojure

• Documentación de la API de Clojure: para macros

Ceceo común

• Implementación de una macro de comprensión de Lisp por Guy Lapalme

Haskell

• El informe Haskell 98, capítulo 3.11 Listas por comprensión.
• Guía del usuario del glorioso sistema de compilación Glasgow Haskell, capítulo 7.3.4 Comprensiones de listas paralelas.
• Guía del usuario de Hugs 98, capítulo 5.1.2 Comprensiones de listas paralelas (también conocidas como comprensiones zip).

OCaml

• Pilas OCaml incluidas
• Extensiones de lenguaje introducidas en OCaml Baterías incluidas

Pitón

• El tutorial de Python, Comprensión de listas.
• Referencia del lenguaje Python, Pantallas de lista.
• Propuesta de mejora de Python PEP 202: Comprensión de listas.
• Referencia del lenguaje Python, Expresiones generadoras.
• Propuesta de mejora de Python PEP 289: Expresiones generadoras.