15 de diciembre de 2015

Listas por comprensión

Las listas por comprensión (list comprehensions en inglés) son una característica interesante pero sobre todo muy útil que fue incorporada al lenguaje Python en su versión 2.0 en el año 2000 (ver: PEP 202). Las listas por comprensión debutaron por vez primera en un lenguaje de programación en 1977, cuando Rod Burstall y John Darlington diseñaron el lenguaje funcional NPL. Hoy en día un número importante de lenguajes de programación soportan listas por comprensión, incluyendo: Haskell, JavaScript 1.7, CoffeeScript, Erlang, F#, Scala, Clojure y Racket.

Conjuntos

Para entender qué son las listas por comprensión tomémonos primero un momento para responder a las siguientes dos preguntas:
¿Qué es un conjunto?
¿Cómo se define un conjunto?
En matemáticas, un conjunto es simplemente una colección de elementos bien definidos. Los elementos pueden ser cualquier cosa: números, letras, nombres, figuras, etc.

Un conjunto de figuras geométricas.

Hay dos manera de definir los elementos que pertenecen a un conjunto: por extensión o por comprensión. Cuando se define un conjunto por extensión cada elemento se enumera de manera explícita. Tomando un ejemplo inspirado en el Señor de los Anillos de J. R. R. Tolkien:
A = { Frodo, Sam, Pippin, Merry, Legolas,
          Gimli, Aragorn, Boromir, Gandalf }
La expresión anterior se lee así: A es el conjunto formado por los elementos: Frodo, Sam, Pippin, Merry, LegolasGimli, Aragorn, Boromir y Gandalf.

Por otro lado, cuando un conjunto se define por comprensión no se mencionan los elementos uno por uno sino que se indica una propiedad que todos éstos cumplen, por ejemplo:
B = { x | x ∈ Comunidad del Anillo }
La expresión de arriba se lee así: B es el conjunto de elementos x tales que x  pertenece a la Comunidad del Anillo.

Los miembros de la Comunidad del Anillo.
Imagen de haleyhss
.

En los ejemplos anteriores podemos decir que el conjunto A es igual al conjunto B debido a que ambos tienen exactamente los mismos elementos. Esto es cierto aún a pesar de que el conjunto A se definió por extensión y B se definió por comprensión.

Listas en Python

En Python se utilizan listas para representar colecciones de elementos (a decir verdad, Python cuenta también con conjuntos [sets] y otros tipos de datos, pero con el fin de simplificar la discusión usaremos aquí solo listas). Ahora bien, así como matemáticamente se pueden definir los conjuntos por extensión y por comprensión, en Python se pueden definir las listas también por extensión y por comprensión.

Supongamos, como ejemplo, que deseamos tener una lista con las primeras diez potencias de dos. Una potencia de dos es cualquiera de los números obtenidos al elevar el número dos a una potencia entera no negativa. El siguiente código de Python cumple con este cometido usando una lista por extensión (enumerando todos los elementos de manera explícita):
c = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512]
Matemáticamente, un conjunto equivalente a la lista anterior se puede definir por comprensión así:
C = { 2x | x ∈ ℤ ∧ 0 ≤ x < 10 }
Esta expresión se lee así: C es el conjunto formado por los elementos “dos elevado a la x”, tales que x pertenece al conjunto de los números enteros y además x es mayor o igual a 0 pero menor que 10. Dicha expresión se puede traducir a Python directamente usando la notación de listas por comprensión:
c = [2 ** x for x in range(10)]
La sintaxis de listas por comprensión consiste en colocar entre corchetes una expresión (2 ** x) seguida de una cláusula for. Dicha cláusula es muy similar en intención a un ciclo for convencional. En este caso estamos indicando que la variable x tomará los valores devueltos por la función range(10) (los enteros del 0 al 9). A partir de cada valor que toma x se calcula el resultado de la expresión 2 ** x y con eso se determinan los valores finales de la lista resultante. Esencialmente es como si ejecutáramos el siguiente código:
c = []
for x in range(10):
    c.append(2 ** x)
El método append() se encarga de ir añadiendo un nuevo elemento (2 ** x) al final de la lista c (inicialmente vacía) en cada iteración del ciclo for.

Las listas por comprensión también pueden incluir una expresión condicional que nos permite quedarnos con ciertos elementos y eliminar los restantes. Para ello se debe utilizar una cláusula if después de la cláusula for. Por ejemplo, si queremos una lista con todos los números entre 1 y 100 que sean múltiplos de 7 o que terminen con el dígito 7, podemos escribir la siguiente lista por comprensión:
[n for n in range(1, 101) if n % 7 == 0 or n % 10 == 7]
El resultado es exactamente lo esperado:
[ 7, 14, 17, 21, 27, 28, 35, 37, 42, 47, 
 49, 56, 57, 63, 67, 70, 77, 84, 87, 91,
 97, 98]
Puede haber más de una cláusula for en una lista por comprensión (también puede haber cero o más cláusulas if). Como ejemplo, supongamos que tengo cuatro camisas (de color rojo, amarillo, azul y verde) y dos pantalones (de color negro y blanco). Quiero saber de qué manera puedo combinar mi ropa. Hay ocho formas distintas (4 camisas × 2 pantalones) de hacerlo:
  • Camisa roja y pantalón negro.
  • Camisa roja y pantalón blanco.
  • Camisa amarilla y pantalón negro.
  • Camisa amarilla y pantalón blanco.
  • Camisa azul y pantalón negro.
  • Camisa azul y pantalón blanco.
  • Camisa verde y pantalón negro.
  • Camisa verde y pantalón blanco.
Podemos dejar que Python calcule lo anterior usando una lista por comprensión con dos cláusulas for:
[(camisa, pantalon) 
    for camisa in ['rojo', 'amarillo', 'azul', 'verde']
    for pantalon in ['negro', 'blanco']]
El resultado es:
[('rojo', 'negro'), ('rojo', 'blanco'),
 ('amarillo', 'negro'), ('amarillo', 'blanco'),
 ('azul', 'negro'), ('azul', 'blanco'),
 ('verde', 'negro'), ('verde', 'blanco')]
Como se puede observar, el ejemplo anterior calcula efectivamente el producto cartesiano de dos conjuntos (los colores de las camisas por los colores de los pantalones).

A continuación presento un par de ejemplos que demuestran el uso de listas por comprensión en contextos más complejos.

Ternas pitagóricas

Una terna pitagórica es un conjunto de tres números naturales (a, b, c) que cumplen con la siguiente ecuación:
 a2 + b2 = c2
El nombre deriva del teorema de Pitágoras, el cual establece que el cuadrado de la hipotenusa de un triángulo rectángulo es igual a la suma de los cuadrados de sus catetos.

Por ejemplo, si a = 3, b = 4 y c = 5, tenemos:
32 + 42 = 52
9 + 16 = 25
Queremos calcular todos los valores posibles de a, b y c que sean menores a 20. Traduciendo directamente los requisitos planteados a una lista por comprensión, tenemos:
[(a, b, c)
    for a in range(1, 20)
    for b in range(1, 20)
    for c in range(1, 20)
    if a ** 2 + b ** 2 == c ** 2]
El resultado correspondiente es:
[(3, 4, 5), (4, 3, 5), (5, 12, 13), (6, 8, 10),
 (8, 6, 10), (8, 15, 17), (9, 12, 15), (12, 5, 13),
 (12, 9, 15), (15, 8, 17)]
Si observamos con atención, hay el doble de ternas deseables en esta solución, ya que se incluyen todas las permutaciones de los valores de a y b. Para corregir esta situación podemos cambiar el valor de inicio de los rangos de las variables b y c para que inicien en un valor posterior al contenido en la variable que está a su izquierda inmediata y con ello garantizamos que: a < b < c. El código quedaría así:
[(a, b, c)
    for a in range(1, 20)
    for b in range(a + 1, 20)
    for c in range(b + 1, 20)
    if a ** 2 + b ** 2 == c ** 2]
El resultado final es el buscado:
[(3, 4, 5), (5, 12, 13), (6, 8, 10), (8, 15, 17),
 (9, 12, 15)]
La lista por comprensión anterior es equivalente al resultado que queda en la variable r del siguiente código:
r = []
for a in range(1, 20):
    for b in range(a + 1, 20):
        for c in range(b + 1, 20):
            if a ** 2 + b ** 2 == c ** 2:
                r.append((a, b, c))
Vale la pena notar que se preserva el orden de los fors y el if en ambos códigos.

Creando una matriz identidad

Una matriz identidad de tamaño n es una matriz cuadrada de n renglones por n columnas en donde cada elemento de la diagonal principal es 1 y los elementos restantes son 0. Por ejemplo, la siguiente es una matriz identidad de tamaño n = 4:


En álgebra lineal una matriz identidad sirve como elemento neutro en la multiplicación de matrices. Esto quiere decir que si I es la matriz identidad y A es otra matriz de dimensiones compatibles, entonces A I = A.

La siguiente función de Python crea un matriz identidad de tamaño n usando listas por comprensión:
def matriz_identidad(n):
    """Devuelve una lista de listas que representa una
       matriz identidad de tamaño n."""
    return [[(1 if ren == col else 0) for col in range(n)]
            for ren in range(n)]
En el código anterior hay una lista por comprensión anidada dentro de otra lista por comprensión. La comprensión externa controla que los n renglones sean generados. La comprensión interna crea un renglón particular conformado por n columnas. Cada elemento individual de la matriz es 1 si su número de renglón es igual a su número de columna, de otra forma es 0.

Probando el código:
>>> matriz_identidad(5)
[[1, 0, 0, 0, 0], 
 [0, 1, 0, 0, 0], 
 [0, 0, 1, 0, 0], 
 [0, 0, 0, 1, 0], 
 [0, 0, 0, 0, 1]]
>>> matriz_identidad(1)
[[1]]

Conclusión

Las listas por comprensión en Python se basan en la notación matemática de conjuntos por comprensión. La notación no es muy compleja, y una vez que la entendemos podemos escribir programas más compactos y expresivos.

6 comentarios:

  1. Ya extrañaba este tipo de aportes para refrescar la memoria profesor, le mando un fuerte abrazo!

    ResponderEliminar
  2. 2018 Y sigue siendo realmente útil, gracias por el aporte.

    ResponderEliminar
  3. Muchas gracias por tu aporte, seguirá alcanzando estudiantes curiosos por mucho tiempo.

    ResponderEliminar