Comprensión de listas

Construcción sintáctica para crear una lista basada en listas existentes

Una lista por comprensión es una construcción sintáctica disponible en algunos lenguajes de programación para crear una lista basada en listas existentes . Sigue la forma de la notación matemática del constructor 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 generador 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 los 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 cumple 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... Dado que el conjunto S consta de todos los números "2 veces x", viene 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 comentada 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 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 del 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 lista por comprensión tiene los mismos componentes sintácticos para representar la generación de una lista en orden a partir de una lista de entrada o iterador :

• Una variable que representa 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 de creación 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 listas por comprensión dan resultados en un orden definido (a diferencia de los miembros de conjuntos); y las listas por comprensión pueden generar los miembros de una lista en orden, en lugar de producir la lista completa, permitiendo así, por ejemplo, la definición anterior 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 del 2 al N :

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

El sistema de álgebra informática 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 "Alguna historia de los lenguajes de programación funcionales", ^[1] David Turner recuerda:

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

setofeven (X) <= <:x: x en X & par(x):>}}

En una nota a pie de página adjunta al término "lista de comprensión", 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 mejor comprensión de listas .

El trabajo de Burstall y Darlington con NPL influyó en muchos lenguajes de programación funcionales 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, perezoso y funcional de Turner , lanzado en 1985. El lenguaje funcional estándar puro y perezoso desarrollado posteriormente, Haskell, incluye muchas de las características de Miranda, incluida la comprensión de listas.

Las comprensiones se propusieron como 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, la comprensión de una mónada es una generalización de la comprensión de la lista a otras mónadas en la programación funcional .

Establecer comprensión

Las versiones 3.x y 2.7 del lenguaje Python introducen la sintaxis para la comprensión de conjuntos . De forma similar a las listas por comprensión, 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' } >>>  tipo ( s ) < clase  ' set '> >>>

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

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

Comprensión del diccionario

Las versiones 3.x y 2.7 del lenguaje Python introdujeron una nueva sintaxis para las comprensiones de diccionarios , similar en forma a las comprensiones de listas pero que generan dictados de Python en lugar de listas.

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

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

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

Comprensión de listas paralelas

El compilador Haskell de Glasgow tiene una extensión llamada comprensión de listas paralelas (también conocida como comprensión zip ) 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 tuberías se evalúan en paralelo (esto no se refiere a ninguna forma de subprocesos múltiples: simplemente significa que las ramas están comprimidas ).

-- comprensión de listas regulares 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" frente a "for*" en el nombre. Por ejemplo, las comprensiones de vectores "for/vector" y "for*/vector" crean vectores mediante iteración paralela versus anidada sobre secuencias. El siguiente es el código de Racket para los ejemplos de comprensión de listas de Haskell.

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

En Python, podríamos hacer lo siguiente:

# comprensión de lista normal >>>  a  =  [( x ,  y )  para  x  en  el rango ( 1 ,  6 )  para  y  en  el rango ( 3 ,  6 )] [( 1 ,  3 ),  ( 1 ,  4 ),  ( 1 ,  5 ),  ( 2 ,  3 ),  ( 2 ,  4 ),  ...# comprensión de lista paralela/comprimida >>>  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 matrices regulares >>> a = [( x , y ) para x en 1 : 5 para y en 3 : 5 ]            # comprensión de matriz paralela/comprimida >>> b = [ x para x en zip ( 1 : 3 , 3 : 5 )]        

con la única diferencia de 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 computacionalmente es inviable recuperar la lista completa y operar con ella (la 'lista completa' inicial puede ser una base de datos XML completa).

En XPath, la expresión:

/ biblioteca / libro // párrafo [ @style = 'primero en el capítulo' ]

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 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 return <shortBook> <title> { $ b // título } </title> <firstPara> {( $ book // párrafo )[ 1 ]} </firstPara> </shortBook>           

Aquí se evalúa el XPath //libro 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 construye/transforma XML para cada elemento de la secuencia utilizando el enfoque de "mapa" que se encuentra en otros lenguajes funcionales.

Entonces, en otro lenguaje funcional, la declaración FLWOR anterior se puede implementar así:

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 llamado 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 ). Seleccione ( 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 seleccione x * 2 ;                 

LINQ proporciona una capacidad sobre las implementaciones típicas de comprensión de listas. 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 interpretar y ejecutar. .

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 de lenguaje que admita directamente la comprensión de listas, pero la sobrecarga de operadores (por ejemplo, sobrecarga |, >>, >>=) se ha utilizado con éxito para proporcionar sintaxis expresiva para lenguajes específicos de dominio de consulta (DSL) "integrados". Alternativamente, se pueden construir listas por comprensión 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>   usando el espacio de nombres estándar ;  plantilla < clase C , clase P , clase T > C comprender ( C && fuente , const P & predicado , const T & transformación ) { // inicializar destino C d = adelante <C> ( fuente ) ;                   // elementos filtrantes d . borrar ( eliminar_if ( comenzar ( d ), finalizar ( d ), predicado ), finalizar ( d ));     // aplicar transformación para_cada uno ( comienzo ( d ), fin ( d ), transformación );    regresar d ; } int principal () { lista < int > rango ( 10 ); // rango es una lista de 10 elementos, todos cero iotas ( comienzo ( rango ), fin ( rango ), 1 ); // el rango ahora contiene 1, 2, ..., 10         lista < int > resultado = comprender ( rango , []( int x ) { return x * x <= 3 ; }, []( int & x ) { x *= 2 ; }); // el resultado ahora contiene 4, 6, ..., 20 }                      

Se hace algún esfuerzo para proporcionar a C++ construcciones/sintaxis de comprensión de listas similares a la notación del generador de conjuntos.

• En Impulso . En la biblioteca de rango [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 filtrado anónimo y funciones transformadoras) (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 'si' y se puede elegir cualquier nombre de variable. Sin embargo, no es seguro para subprocesos . Ejemplo de uso:

lista <int> N ;​​ lista <doble> S ;​​  para ( int i = 0 ; i < 10 ; i ++ ) norte . push_back ( yo );         S << lista_comprensión ( 3.1415 * x , x , N , x * x > 3 )           

• Esta implementación ^[7] proporciona corte de cabeza/cola usando clases y sobrecarga de operadores, y el | operador para filtrar listas (usando funciones). Ejemplo de uso:

bool incluso ( int x ) { retorno x % 2 == 0 ; } bool x2 ( int & x ) { x *= 2 ; devolver verdadero ; }                   lista <int> l , t ;​​ intx , y ;​    para ( int i = 0 ; i < 10 ; i ++ ) l . push_back ( yo );         ( x , t ) = l | x2 ; ( t , y ) = t ;        t = l < 9 ; t = t < 7 | incluso | x2 ;            

• El lenguaje para consultas y recorrido integrados (LEESA ^[8] ) 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 con tipos ricos 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 >>XPath/separador. El separador // de XPath que "salta" los nodos intermedios en el árbol se implementa en LEESA utilizando lo que se conoce como Programación Estratégica. En el siguiente ejemplo, catálogo_, libro_, autor_ y nombre_ son instancias de las clases catálogo, libro, autor y nombre, respectivamente.

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

Ver también

• Notación de constructor de conjuntos
• La sentencia SELECT junto con sus cláusulas FROM y WHERE en SQL

notas y referencias

1. Turner, David (2012). "Un poco de historia de los lenguajes de programación funcionales" (PDF) . Simposio internacional sobre tendencias en programación funcional, Springer, Berlín, Heidelberg . págs. 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 para la ubicación". Lenguaje de ruta 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 XQuery FLWOR". Escuelas W3 . 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. "Comprensiones de listas de C++". Archivado desde el original el 7 de julio de 2017 . Consultado el 9 de enero de 2011 .
8. "Lenguaje para consulta y recorrido integrados (LEESA)".

• Comprensión de listas en el Diccionario gratuito de informática en línea, editor Denis Howe.
• Wadler, Philip (1990). "Comprensión de las 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 frases breves de comprensión de listas en el libro de recetas de Python
• Discusión sobre listas por comprensión en Scheme y construcciones relacionadas
• Lista de comprensiones en todos los idiomas

Axioma

• Ejemplos de secuencias de axiomas

Clojure

• Documentación de la API de Clojure - para macro

ceceo común

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

Haskell

• Informe Haskell 98, capítulo 3.11 Listas por comprensión.
• Guía del usuario del Glorious Glasgow Haskell Compilation System, 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

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

Pitón

• El tutorial de Python, listas por comprensión.
• Referencia del lenguaje Python, se muestra la lista.
• Propuesta de mejora de Python PEP 202: Lista por comprensión.
• Referencia del lenguaje Python, expresiones generadoras.
• Propuesta de mejora de Python PEP 289: Expresiones generadoras.