common-lisp
Tipi di elenchi

Elenchi semplici

Gli elenchi semplici sono il tipo più semplice di elenco in Common Lisp. Sono una sequenza ordinata di elementi. Supportano le operazioni di base come ottenere il primo elemento di una lista e il resto di un elenco in tempo costante, supportano l'accesso casuale in tempo lineare.

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

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

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

Ci sono molte funzioni che operano su liste "semplici", nella misura in cui si preoccupano solo degli elementi della lista. Questi includono find , mapcar e molti altri. (Molte di queste funzioni funzioneranno anche su 17.1 Sequence Concepts per alcune di queste funzioni.

Liste di associazioni

Gli elenchi semplici sono utili per rappresentare una sequenza di elementi, ma a volte è più utile rappresentare un tipo di chiave per la mappatura dei valori. Common Lisp offre diversi modi per farlo, comprese le autentiche tabelle hash (vedere 18.1 Concetti relativi alla tabella hash ). Esistono due modi principali o rappresentano i mapping chiave-valore in Common Lisp: elenchi di proprietà e elenchi di associazioni . Questo esempio descrive gli elenchi di associazioni.

Una lista di associazioni, o alist è una lista "semplice" i cui elementi sono coppie puntate in cui la macchina di ogni coppia è la chiave e il cdr di ciascuna coppia è il valore associato. Per esempio,

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

può essere considerato come una lista di associazioni che mappa simboli che indicano un nome personale con un intero che indica l'età. È possibile implementare alcune funzioni di recupero utilizzando le funzioni di elenco semplice, come membro . Ad esempio, per recuperare l'età di John , si potrebbe scrivere

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

La funzione membro restituisce la coda della lista cominciando con una cella contro la cui auto è mary , cioè, ((mary. 23) (tim.72)) , per prima cosa restituisce il primo elemento di quella lista, che è (mary. 23) , e cdr restituisce il lato destro di quella coppia, che è 23 . Mentre questo è un modo per accedere ai valori in una lista di associazioni, lo scopo di una convenzione come liste di associazioni è di astrarre dalla rappresentazione sottostante (una lista) e di fornire funzioni di livello superiore per lavorare con la struttura dati.

Per gli elenchi di associazioni, la funzione di recupero è assoc , che accetta una chiave, un elenco di associazioni e parole chiave di test facoltative (chiave, test, test-non) e restituisce la coppia per la chiave corrispondente:

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

Poiché il risultato sarà sempre una cella di controllo se un elemento è presente, se l' associazione restituisce zero , l'elemento non era presente nell'elenco:

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

Per l'aggiornamento dei valori in un elenco di associazioni, setf può essere usato insieme a cdr . Ad esempio, quando arriva il compleanno di John e la sua età aumenta, si può eseguire una delle seguenti azioni:

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

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

incf funziona in questo caso perché è basato su setf .

Gli elenchi di associazioni possono anche essere usati come un tipo di mappa bidirezionale, poiché le mappature da chiave a valore possono essere recuperate in base al valore utilizzando la funzione di associazione invertita, rassoc .

In questo esempio, l'elenco di associazioni è stato creato utilizzando list e cons esplicitamente, ma è possibile creare elenchi di associazioni anche utilizzando pairlis , che prende un elenco di chiavi e dati e crea un elenco di associazioni basato su di essi:

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

Una coppia di chiavi e valori può essere aggiunta a un elenco di associazioni usando gli acons :

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

La funzione assoc cerca nella lista da sinistra a destra, il che significa che è possibile "mascherare" i valori in una lista di associazioni senza rimuoverli da una lista o aggiornare la struttura della lista, semplicemente aggiungendo nuovi elementi alla lista inizio della lista. La funzione acons è fornita per questo:

(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))

E ora, una ricerca per mary restituirà la prima voce:

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

Elenchi di proprietà

Gli elenchi semplici sono utili per rappresentare una sequenza di elementi, ma a volte è più utile rappresentare un tipo di chiave per la mappatura dei valori. Common Lisp offre diversi modi per farlo, comprese le autentiche tabelle hash (vedere 18.1 Concetti relativi alla tabella hash ). Esistono due modi principali o rappresentano i mapping chiave-valore in Common Lisp: elenchi di proprietà e elenchi di associazioni . Questo esempio descrive gli elenchi di proprietà.

Un elenco di proprietà, o plist , è un elenco "semplice" in cui i valori alternati vengono interpretati come chiavi e i relativi valori associati. Per esempio:

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

può essere considerato come un elenco di proprietà che mappa simboli che indicano un nome personale con un intero che indica l'età. È possibile implementare alcune funzioni di recupero utilizzando le funzioni di elenco semplice, come membro . Ad esempio, per recuperare l'età di John , si potrebbe scrivere

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

La funzione membro restituisce la coda della lista che inizia con mary , cioè, (mary 23 tim 72) , e la seconda restituisce il secondo elemento di quella lista, cioè 23 . Mentre questo è un modo per accedere ai valori in una lista di proprietà, lo scopo di una convenzione come liste di proprietà è di astrarre dalla rappresentazione sottostante (una lista) e di fornire funzioni di livello superiore per lavorare con la struttura dati.

Per gli elenchi di proprietà, la funzione di recupero è getf , che prende l'elenco di proprietà, una chiave (più comunemente chiamata un indicatore ) e un valore predefinito facoltativo da restituire nel caso in cui l'elenco di proprietà non contenga un valore per la chiave.

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

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

Per aggiornare i valori in un elenco di proprietà, può essere usato setf . Ad esempio, quando arriva il compleanno di John e la sua età aumenta, si può eseguire una delle seguenti azioni:

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

(incf (getf *ages* 'john))

incf funziona in questo caso perché è basato su setf .

Per cercare più proprietà in un elenco di proprietà come una volta, usa get-properties .

La funzione getf ricerca l'elenco da sinistra a destra, il che significa che è possibile "mascherare" i valori in un elenco di proprietà senza rimuoverli da un elenco o aggiornare una qualsiasi struttura dell'elenco. Ad esempio, 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)

E ora, una ricerca per mary restituirà la prima voce:

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