2.1.2. Listas


Por la importancia dentro de LISP del tipo de datos LISTA, citamos in extenso el apartado 2.4 de CLTL2,

Un CONS es una estructura de información que contiene dos componentes llamados el CAR y el CDR. La utilización fundamental de los CONSES es como representación de LISTAS.

Una LISTA se define recursivamente ya sea como la lista vacía o como un CONS cuyo componente CDR es una lista. Una lista es, por consiguiente, una cadena de CONSES enlazados por sus componentes CDR y terminada por un NIL, la lista vacía. Los componentes CAR de los conses son conocidos como los elementos de la lista. Para cada elemento de la lista hay un CONS. La lista vacía no tiene ningún elemento.

Para comprender mejor lo anterior, adelantaremos la mención de la función básica de construcción de listas, que es la función CONS (que se explica en el apartado FUNCIONES DE CONSTRUCCIÓN DE LISTAS). Expresado en términos de esta función, la anterior definición de una lista como una cadena de CONSES sería:


Una LISTA se expresa mediante la escritura de los elementos de la lista ordenados, separados por espacios en blanco (caracteres de espacio, tabulador o retorno) y rodeados por paréntesis. Por ejemplo:

(a b c) ;Una lista de tres símbolos
(2.0 (a 1) "*") ;Una lista de tres cosas diferentes: un número real
;otra lista y un carácter asterisco
Nota: El código del ejemplo anterior ha sido modificado para adaptarlo a las convenciones de AutoLISP/Visual LISP

La lista vacía puede por lo tanto ser expresada como (), ya que se trata de una lista sin elementos.

Una lista punteada (dotted list) es una cuyo último cons no tiene NIL como su CDR, sino otro objeto de información (que tampoco será un CONS, ya que entonces el CONS anteriormente mencionado no hubiera sido el último CONS de la lista).

Tal tipo de lista se conoce como "punteada" debido a la notación especial que se emplea en ella: los elementos de la lista se escriben, al igual que antes, entre paréntesis, pero ... antes del paréntesis derecho se escriben un punto (rodeado por espacios en blanco) y entonces el CDR del último CONS. Como caso especial, un CONS aislado se expresa escribiendo el CAR y el CDR entre paréntesis y separados por un punto rodeado de espacios (par punteado). Por ejemplo:

(a . 4) ;Un cons cuyo car es el símbolo a
;y cuyo cdr es un entero
(a b c . d) ;Una lista punteada con tres elementos cuyo cons final
;tiene el símbolo d en su cdr

Con frecuencia se utiliza el término lista para hacer referencia tanto a verdaderas listas como a listas punteadas. Cuando resulta importante la distinción, se utilizará el término "verdadera lista" para referirnos a una lista terminada por NIL. La mayoría de las funciones que se dice operan sobre listas esperan recibir verdaderas listas como argumento.

Por ejemplo, si en el ejemplo de concatenación de CONSES anterior el elemento de la derecha del último CONS no hubiera sido NIL (lo que hubiera incluido un par punteado en la lista), el pasar esta lista como argumento a una función de tratamiento de listas hubiera producido en determinados casos un error:


A veces se utiliza el término árbol para referirse a algunos CONS y todos los demás CONSES accesibles a él de manera transitiva a través de enlaces de CAR y CDR hasta alcanzar objetos NO-CONS; éstos NO-CONSES son conocidos como las hojas del árbol.

Representación de LISTAS como árboles.
Tomado de: Cortés y Sierra, LISP. Editorial Marcombo, Barcelona. 1987.

Las listas, las listas punteadas y los árboles no son tipos de datos mutuamente excluyentes; no son más que puntos de vista útiles en torno a las estructuras de CONSES. Hay aún otros términos tales como LISTA DE ASOCIACIÓN. Ninguno de éstos son verdaderos tipos de datos LISP.
Los CONSES constituyen un tipo de dato, y NIL es el único objeto de tipo NULL. El tipo de dato LISTA significa en LISP la unión de los tipos de datos CONS y NULL, y por ello engloba tanto las listas verdaderas como las listas punteadas.

FORMATOS DE LISTAS:

Además de lo apuntado más arriba, es conveniente distinguir entre los siguientes tres formatos de listas:

  • LISTAS DE UN NIVEL

    Contienen sólo átomos.
  • LISTAS ANIDADAS

    Contienen a su vez otras listas que se dicen ‘anidadas’. Estas listas anidadas suelen ser conocidas como sub-listas. El número de niveles de anidación no está restringido ni en su profundidad ni en su complejidad. El nivel más externo lo llamamos nivel superior o primer nivel. A los elementos que conforman este nivel los llamamos elementos de primer nivel.
  • LISTAS DE ASOCIACIÓN (A-LIST)

    Son listas anidadas que se utilizan con frecuencia como estructura de datos en LISP. Una A-LIST es una lista de pares (CONSES) en que cada par constituye una asociación. El CAR de uno de estos pares se conoce como la CLAVE y el CDR constituye el DATO. Una ventaja de la representación como A-LIST es la posibilidad de incrementarla añadiéndole nuevas entradas al principio de la lista. Más aún, como la función de búsqueda ASSOC recorre la A-LIST de manera ordenada, las nuevas entradas pueden "enmascarar" las más antiguas de manera que la información puede ser modificada de forma no destructiva.
  • LA LISTA VACÍA (NIL)

    Como se dijo antes, es la que no contiene ningún elemento. Se indica como () y recibe un nombre particular, el de NIL.
    La lista vacía tiene un status peculiar en LISP. Es a la vez un átomo y una lista. Como símbolo representa el valor lógico de FALSO:
_$ ()
nil
_$ (atom nil)
T
_$ (listp nil)
T
  • CIERTO Y FALSO

    Su negación (not nil) sería el símbolo T que representa la condición lógica de CIERTO.
    El símbolo T es también una constante en el sentido de que sólo se representa a sí mismo.
    En Visual LISP, nil y T así como otros elementos que incluyen los operadores aritméticos (+, -. etc.) son símbolos protegidos. Cualquier intento de asignarle otro valor producirá un mensaje de advertencia:

    Este mensaje aparece como la opción por defecto y pide si se desea entrar en un bucle de interrupción (break loop). Si se escoge No, el valor del símbolo es modificado. Si se selecciona Sí, se interrumpe el procesamiento y se entra en un ciclo de interrupción de Visual LISP, lo que se conoce por el aspecto del símbolo del evaluador, por ejemplo: _1_$.

    El control se ha trasladado a la consola de Visual LISP. Para asignar valor al símbolo y continuar el procesamiento se deberá pular el botón Continuar  en la barra de herramientas de Visual LISP. Para abortar el procesamiento se pulsará Reset  .

Inicio | Índice | Continuar...