common-lisp
Tipos de listas

Listas simples

Las listas simples son el tipo de lista más simple en Common Lisp. Son una secuencia ordenada de elementos. Admiten operaciones básicas como obtener el primer elemento de una lista y el resto de una lista en tiempo constante, admiten acceso aleatorio en tiempo lineal.

(list 1 2 3)
;=> (1 2 3)

(first (list 1 2 3))
;=> 1

(rest (list 1 2 3))
;=> (2 3)

Hay muchas funciones que operan en listas "simples", en la medida en que solo se preocupan por los elementos de la lista. Estos incluyen encontrar , mapcar , y muchos otros. (Muchas de esas funciones también funcionarán en 17.1 Conceptos de secuencia para algunas de estas funciones.

Listas de asociaciones

Las listas simples son útiles para representar una secuencia de elementos, pero a veces es más útil representar un tipo de clave para la asignación de valores. Common Lisp proporciona varias formas de hacer esto, incluyendo tablas hash genuinas (ver 18.1 Hash Table Concepts ). Hay dos formas principales o que representan la clave para las asignaciones de valor en Common Lisp: listas de propiedades y listas de asociación . Este ejemplo describe las listas de asociaciones.

Una lista de asociaciones, o alista, es una lista "simple" cuyos elementos son pares de puntos en los que el carro de cada par es la clave y el valor asociado es la CDR de cada par. Por ejemplo,

(defparameter *ages* (list (cons 'john 34) (cons 'mary 23) (cons 'tim 72)))

se puede considerar como una lista de asociaciones que asigna símbolos que indican un nombre personal con un número entero que indica la edad. Es posible implementar algunas funciones de recuperación utilizando funciones de lista simple, como miembro . Por ejemplo, para recuperar la edad de John , uno podría escribir

(cdr (first (member 'mary *age* :key 'car)))
;=> 23

La función miembro devuelve la cola de la lista que comienza con una celda de contras cuyo auto es mary , es decir, ((mary. 23) (tim. 72)) , primero devuelve el primer elemento de esa lista, que es (mary. 23) , y cdr devuelve el lado derecho de ese par, que es 23 . Si bien esta es una forma de acceder a los valores en una lista de asociación, el propósito de una convención como las listas de asociación es abstraerse de la representación subyacente (una lista) y proporcionar funciones de nivel superior para trabajar con la estructura de datos.

Para las listas de asociación, la función de recuperación es assoc , que toma una clave, una lista de asociación y palabras clave de prueba opcionales (clave, prueba, prueba-no) y devuelve el par para la clave correspondiente:

(assoc 'tim *ages*)
;=> (tim . 72)

Dado que el resultado siempre será una celda de contras si un elemento está presente, si assoc devuelve nil , entonces el elemento no estaba en la lista:

(assoc 'bob *ages*)
;=> nil

Para actualizar los valores en una lista de asociaciones, setf puede usarse junto con cdr . Por ejemplo, cuando llega el cumpleaños de John y aumenta su edad, se puede realizar una de las siguientes acciones:

(setf (cdr (assoc 'john *ages*) 35)

(incf (cdr (assoc 'john *ages*)))

incf funciona en este caso porque se basa en setf .

Las listas de asociación también se pueden usar como un tipo de mapa bidireccional, ya que las asignaciones de clave a valor se recuperan según el valor mediante la función assoc invertida, rassoc .

En este ejemplo, la lista de asociaciones se creó mediante el uso de listas y contras explícitamente, pero las listas de asociaciones también se pueden crear utilizando pairlis , que toma una lista de claves y datos y crea una lista de asociaciones basada en ellas:

(pairlis '(john mary tim) '(23 67 82))
;=> ((john . 23) (mary . 67) (tim . 82))

Se puede agregar un solo par de clave y valor a una lista de asociación usando un acons :

(acons 'john 23 '((mary . 67) (tim . 82)))
;=> ((john . 23) (mary . 67) (tim . 82))

La función assoc busca en la lista de izquierda a derecha, lo que significa que es posible "enmascarar" los valores en una lista de asociación sin eliminarlos de una lista o actualizar la estructura de la lista, simplemente agregando nuevos elementos a la lista. comienzo de la lista. La función de acons se proporciona para esto:

(defvar *ages* (pairlis '(john mary tim) '(34 23 72)))

(defvar *new-ages* (acons 'mary 29 *ages*))

*new-ages*
;=> ((mary . 29) (john . 34) (mary . 23) (tim . 72))

Y ahora, una búsqueda de Mary devolverá la primera entrada:

(assoc 'mary *new-ages*)
;=> 29

Listas de propiedades

Las listas simples son útiles para representar una secuencia de elementos, pero a veces es más útil representar un tipo de clave para la asignación de valores. Common Lisp proporciona varias formas de hacer esto, incluyendo tablas hash genuinas (ver 18.1 Hash Table Concepts ). Hay dos formas principales o que representan la clave para las asignaciones de valor en Common Lisp: listas de propiedades y listas de asociación . Este ejemplo describe las listas de propiedades.

Una lista de propiedades, o plist , es una lista "simple" en la que los valores alternos se interpretan como claves y sus valores asociados. Por ejemplo:

(defparameter *ages* (list 'john 34 'mary 23 'tim 72))

se puede considerar como una lista de propiedades que asigna símbolos que indican un nombre personal con un número entero que indica la edad. Es posible implementar algunas funciones de recuperación utilizando funciones de lista simple, como miembro . Por ejemplo, para recuperar la edad de John , uno podría escribir

(second (member 'mary *age*))
;=> 23

La función miembro devuelve la cola de la lista que comienza con mary , es decir, (mary 23 tim 72) , y la segunda devuelve el segundo elemento de esa lista, que es 23 . Si bien esta es una forma de acceder a los valores en una lista de propiedades, el propósito de una convención como las listas de propiedades es abstraerse de la representación subyacente (una lista) y proporcionar funciones de nivel superior para trabajar con la estructura de datos.

Para las listas de propiedades, la función de recuperación es getf , que toma la lista de propiedades, una clave (más comúnmente llamada indicador ) y un valor predeterminado opcional para devolver en caso de que la lista de propiedades no contenga un valor para la clave.

(getf *ages* 'tim)
;=> 72

(getf *ages* 'bob -1)
;=> -1

Para actualizar los valores en una lista de propiedades, se puede usar setf . Por ejemplo, cuando llega el cumpleaños de John y aumenta su edad, se puede realizar una de las siguientes acciones:

(setf (getf *ages* 'john) 35)

(incf (getf *ages* 'john))

incf funciona en este caso porque se basa en setf .

Para buscar varias propiedades en una lista de propiedades una vez, use get-properties .

La función getf busca en la lista de izquierda a derecha, lo que significa que es posible "enmascarar" los valores en una lista de propiedades sin eliminarlos de una lista o actualizar la estructura de la lista. Por ejemplo, usando la lista * :

(defvar *ages* '(john 34 mary 23 tim 72))

(defvar *new-ages* (list* 'mary 29 *ages*))

*new-ages*
;=> (mary 29 john 34 mary 23 tim 72)

Y ahora, una búsqueda de Mary devolverá la primera entrada:

(getf *new-ages* 'mary)
;=> 29