Listas
En la sección anterior vimos cómo usar la programación invariante para crear bucles que realizaran cálculos con enteros. Los enteros, sin embargo, son un tipo de dato bastante simple. En muchos casos vamos a querer realizar cálculos con grandes cantidades de datos, con grandes cantidades de enteros, por ejemplo. Y en esos casos vamos a necesitar algo que llamamos tipos de datos compuestos. Entre los tipos de datos compuestos más simples se encuentran las listas. Las listas son básicamente secuencias ordenadas de elementos. Fueron inventadas en el lenguaje de programación LISP en los años 50, y desde entonces, son una parte esencial de la programación simbólica, de modo que la mayoría de los lenguajes simbólicos las soportan. En definitiva, claramente no es suficiente con saber implementar las técnicas como la programación invariante a tipos de datos simples como los enteros. En esta sección, por lo tanto, nos dedicaremos a ampliar nuestra capacidad de trabajo hacia tipos de datos compuestos comenzando con uno de los más simples y comunes: las listas. Aunque no creas que por ser una de las estructuras de datos más sencillas, sean estrictamente simples. Se ven simples, pero de hecho, tienen algunas sutilezas. Las listas, en realidad, son una estructura de datos recursiva. Y si escribes programas que usen listas, tienes que respetar su estructura recursiva. Así que, de nuevo, no son tan simples como las hacen ver la definición acotada y clásica que dimos más arriba. De modo que hay una definición más precisa de qué son las listas, y de cómo, por ejemplo, podemos recorrerlas si queremos escribir programas que calculen con ellas. Revisemos estas definiciones.
Nota: LISP, de hecho, es una abreviación de List Processor (procesador de listas).
Nota2: Un lenguaje simbólico es un lenguaje que tiene soporte especial para realizar cálculos con datos que no sean números, por ejemplo, con datos como listas, árboles, grafos, y otros datos no numéricos.
Definiendo las listas con el uso de reglas gramáticales
Una lista es un tipo de dato recursivo. Esto significa que su definición está dada en términos de sí misma. La recursión, de hecho, no es algo exclusivo de las computaciones, sino que también puede ser una propiedad de los datos. Lo anterior es importante tenerlo en cuenta cuando escribimos funciones dirigidas a trabajar con listas, ya que estas funciones también serán recursivas y, de hecho, van a seguir la estructura recursiva dada por su definición, de modo que se ajustan perfectamente. Dicho esto, ¿Cómo es que definimos a una lista?, del siguiente modo:
Una lista es ya sea una lista vacía o un par compuesto de un elemento seguido de otra lista
Como habíamos adelantado, su definición es recursiva. Una lista se define en términos de listas, y no hay regresión infinita pues la usaremos de forma constructiva, para construir listas más grandes a partir de otras más pequeñas, comenzando con una vacía. Bueno, siendo más precisos, eso es una lista. Ahora, en términos formales, con esa sóla definición no basta. Aún nos queda definir su sintaxis y su semántica. Estas dos definiciones son un aspecto muy relevante en la definición formal de cualquier estructura de dato. Bien, definamos primero su sintaxis, es decir, su representación textual. Para ello vamos a usar lo que se conoce como una regla gramátical EBNF. EBNF son las siglas para Extended Backus-Naur Form, o en español, para Notación de Backus-Naur extendida. Esta es una forma muy popular para definir sintaxis inventada por John Backus y Peter Naur hace 50 años atrás. Usando esta regla escribimos:
Se puede ver algo complicado, pero es cosa de entender el significado de cada
uno de los elementos que componen la expresión. En esta regla, List T representa a una lista
de elementos de tipo T. El ::= es una notación para representar la expresión «se define como».
Luego, nil es la forma en que se representan a las listas vacías. La barra vertical |
significa el conector lógico «o». La T, un elemento de tipo T. Y finalmente, una
barra vertical entre comillas representa a |, pero con el significado de la sintaxis que estamos
definiendo (que va depender del lenguaje). En este caso, representa a un operador
que define a un par compuesto de las dos partes que aparecen a sus lados. Resumiendo
todo lo anterior, podemos leer la expresión anterior como: «una lista de elementos de tipo T
se define como una lista vacía o un par compuesto de un elemento de tipo T y otra
lista de elementos de tipo T». Exactamente la misma definición que dimos antes.
Nota: nil y el | entre comillas no son parte de la notación ENBF, sino elementos que
definimos en la sintaxis de nuestro lenguaje. En este ejemplo se usa la sintaxis
del lenguaje Oz para representar a una lista vacía, y a un elemento seguido de otro.
La misma definición anterior se puede llevar a otro lenguaje, y en ese caso habría
que reemplazar nil y el | entre comillas, por la sintaxis para representar
a una lista vacía, y a un elemento seguido de otro, en ese lenguaje en especifico.
Nota2: Comprendida la nota anterior, no hay que confundir entre el | sin comillas
y el que está entre comillas. El sin comillas es parte de la notación ENBF («o» lógico),
mientras el otro no, sino que se refiere al significado de | en la sintaxis que
definimos (en este caso, lenguaje Oz). Las comillas justamente están para distinguir
entre notaciones del ENBF y las definidas por un lenguaje en especifico cuando se
representan del mismo modo.
Siguiendo la definición dada anteriormente podríamos definir las siguientes listas
(considerando que T fuera un entero):
nil
10 | nil
10 | 11 | nil
10 | 11 | 12 | nil
Nota: Recuerda que | representa a un elemento seguido de otro en Oz. Usamos aquí esta notación por cuestiones de simplificación.
Notación de tipo
En la definición dada anteriormente, mencionamos que List T significaba una lista
de elementos de tipo T, pero no mencionamos nada sobre los corchetes angulares (< >) que
le rodeaban. Estos "corchetes" de hecho le dan un giro bastante relevante a su significado.
La idea detrás de esta notación está en representar al conjunto de las todas representaciones sintácticas de
un tipo en particular. De modo que lo que en realidad significaba <List T> era el conjunto de todas
las representaciones sintácticas de una lista de elementos de tipo T. Esto, de hecho,
es lo que representa para cualquier otro tipo de dato que rodee. Si tenemos <Int>, más que
representar a un entero, sería más preciso decir que identifica al conjunto de todas las representaciones
sintácticas de los enteros. Y si el caso fuera <List <Int>>, entonces estaríamos ante
el conjunto de todas las representaciones sintácticas de listas de enteros, y así en más.
En adición a lo anterior, la T más que representar a un elemento de tipo T en la notación
ENBF, representa más bien al conjunto de todas las representación de valores de tipo T.
En este caso, además, decimos que T es una variable de tipo, un símbolo para
representar a un tipo cualquiera en particular.
Nota: Las variables de tipo sólo existen en las reglas gramáticales. No se deben confundir con las variables de la memoria, o con los identificadores a los que asociamos esas variables.
No confundir una cosa y su representación
Para finalizar esta sección dedicada a la definición de las listas, vale la pena tomar en cuenta una lección muy importante que nos ha dado el pintor surrealista Rene Magritte. A continuación se muestra una pintura muy famosa cuyo título es Ceci n`est une pipe - o en español, esto no es una pipa.
Y de hecho, definitivamente esta pintura no es una pipa. Alguien le preguntó a Magritte ¿Si no es una pipa, qué es entonces?¿En qué sentido no es una pipa? Y Magritte le dijo, trata de rellenarla con tabaco, y verás que no es una pipa. De modo que lo que aquí se muestra es una fotografía digital de una pintura de una pipa, a menos que la imprimas, en cuyo caso sería una versión impresa de una ...,y etcétera, etcétera. De forma análoga esto no es un entero:
Es tan sólo una representación visual de un entero usando símbolos numéricos en base 10.
A tener en cuenta
Utilizando la definición dada más arriba ¿Es posible construir una lista circular?
Representaciones para las listas
La definición dada anteriormente (usando EBNF) nos entrega una representación textual para
las listas. Esta es una representación formal que nos muestra cómo mediante su
propia definición podemos ir construyendo listas cada vez más grandes, a partir
de otra más pequeña. Podemos tomar, por lo tanto, el lado izquierdo de esa
definición (<List T>) y ir reemplazándolo de manera repetida según la definición para ir construyendo listas
de más y más elementos hasta finalizar con una lista vacía:
<List T> =>
10 | <List T> =>
10 | 11 | <List T> =>
10 | 11 | 12 | <List T> =>
10 | 11 | 12 | nil
Sin embargo, los lenguajes que soportan listas generalmente no incluyen (o no incluyen únicamente) una sintaxis para construir listas de acuerdo a su definición teórica. En su lugar, es común la inclusión de otras representaciones sintácticas, como el uso de corchetes (ej. [1, 2, 3] que sería idéntica a nuestra representación formal 1|2|3|nil). El motivo es simplemente facilitar la vida al programador, de modo que pueda contar con una sintaxis para representar listas posiblemente más legible o más intuitiva. Pero cómo se ha mencionado no hay que confundir entre la definición (formal) y su representación. Representaciones pueden haber muchas. Un lenguaje puede ofrecer distintas formas de expresar la misma cosa. Y a las diferentes representaciones sintácticas (fuera de la formal) que tienen como objetivo la comodidad del programador, se les conoce como azúcar sintáctica. El nombre se puede atribuir en cierto modo, a que es sintaxis que busca endulzar el trabajo del desarrollador. Y similar a como no es bueno comer demasiada azúcar, demasiada azúcar sintáctica no ayuda a la claridad, y puede hacer perder de vista la esencia de los conceptos.
Otra forma de representar las listas es de forma gráfica. Esta forma, por supuesto, tiene como fin ayudar al programador a razonar sobre las listas de forma abstracta fuera del programa (los humanos tenemos habilidades de razonamiento visual muy poderosas). En esta representación la lista se puede dibujar como un grafo con vértices y aristas como el que se muestra a continuación para la lista de nuestro ejemplo más arriba:
La forma de construir el grafo es la siguiente: Comenzamos nuevamente desde
la representación más a la izquierda, en este caso, 10 | , y dibujamos
tres nodos. Un nodo con una barra vertical, otro con el número diez, y otro que
representa a la otra lista
, que posteriormente se reemplaza repetidamente
por otros tres nodos hasta construir el diagrama completo de la imagen. Nota que
el grafo es dirigido. Se indica una dirección especifica hacia los nodos que
representa como la lista se ha construido paso a paso. Además, nota que, en este caso,
el grafo que nos resulta es un caso especial para la estructura de un grafo que se conoce
como un árbol. Los árboles de hecho son, a continuación de las listas, la estructura
de dato más importante en las ciencias de la computación.