common-lisp
Soorten lijsten

Overzichtelijke lijsten

Normale lijsten zijn het eenvoudigste type lijst in Common Lisp. Ze zijn een geordende reeks elementen. Ze ondersteunen basisbewerkingen zoals het verkrijgen van het eerste element van een lijst en de rest van een lijst in constante tijd, ondersteunen willekeurige toegang in lineaire tijd.

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

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

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

Er zijn veel functies die werken op "gewone" lijsten, voor zover ze alleen om de elementen van de lijst geven. Deze omvatten zoeken , mapcar en vele anderen. (Veel van die functies werken ook voor 17.1 Sequentieconcepten voor sommige van deze functies.

Associatielijsten

Gewone lijsten zijn handig voor het weergeven van een reeks elementen, maar soms is het nuttiger om een soort sleutel voor waardetoewijzing weer te geven. Common Lisp biedt verschillende manieren om dit te doen, waaronder echte hashtabellen (zie 18.1 Hash- tafelconcepten). Er zijn twee primaire manieren of de sleutel voor waardetoewijzingen in Common Lisp: eigenschappenlijsten en associatielijsten . Dit voorbeeld beschrijft associatielijsten.

Een associatielijst of alist is een "gewone" lijst waarvan de elementen gestippelde paren zijn waarin de auto van elk paar de sleutel is en de cdr van elk paar de bijbehorende waarde is. Bijvoorbeeld,

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

kan worden beschouwd als een associatielijst die symbolen toewijst die een persoonlijke naam aangeven met een geheel getal dat de leeftijd aangeeft. Het is mogelijk om enkele ophaalfuncties te implementeren met behulp van gewone lijstfuncties, zoals lid . Om bijvoorbeeld de leeftijd van john te achterhalen, zou men kunnen schrijven

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

Het lid functie retourneert de staart van de lijst begin met een contra cel waarvan auto mary, dat wil zeggen ((mary. 23) (tim. 72)) eerst terug het eerste element van deze lijst, wat (Mary. 23) , en cdr geeft de rechterkant van dat paar terug, dat is 23 . Hoewel dit een manier is om toegang te krijgen tot waarden in een associatielijst, is het doel van een conventie-achtige associatielijsten om de onderliggende weergave (een lijst) samen te vatten en functies op een hoger niveau te bieden voor het werken met de gegevensstructuur.

Voor associatielijsten is de ophaalfunctie assoc , waarvoor een sleutel, een associatielijst en optionele testzoekwoorden (key, test, test-not) nodig zijn en het paar voor de bijbehorende sleutel wordt geretourneerd:

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

Aangezien het resultaat altijd een nadelencel is als een item aanwezig is, als assoc nul retourneert, stond het item niet in de lijst:

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

Voor het bijwerken van waarden in een associatielijst kan setf samen met cdr worden gebruikt. Wanneer John bijvoorbeeld jarig is en zijn leeftijd toeneemt, kan een van de volgende handelingen worden uitgevoerd:

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

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

incf werkt in dit geval omdat het gebaseerd is op setf .

Associatielijsten kunnen ook worden gebruikt als een type bidirectionele kaart, omdat sleutel tot waardetoewijzingen worden opgehaald op basis van de waarde met behulp van de omgekeerde associatiefunctie , rassoc .

In dit voorbeeld is de associatielijst expliciet gemaakt met behulp van lijst en nadelen , maar associatielijsten kunnen ook worden gemaakt met behulp van pairlis , die een lijst met sleutels en gegevens neemt en op basis daarvan een associatielijst maakt:

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

Een enkel sleutel- en waardepaar kan aan een associatielijst worden toegevoegd met behulp van acons :

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

De assoc- functie doorzoekt de lijst van links naar rechts, wat betekent dat het mogelijk is om waarden in een associatielijst te "maskeren" zonder ze uit een lijst te verwijderen of de structuur van de lijst bij te werken, gewoon door nieuwe elementen toe te voegen aan de begin van de lijst. De acons- functie is hiervoor voorzien:

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

En nu zal een zoekopdracht voor Mary het eerste item retourneren:

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

Onroerendgoedlijsten

Gewone lijsten zijn handig voor het weergeven van een reeks elementen, maar soms is het nuttiger om een soort sleutel voor waardetoewijzing weer te geven. Common Lisp biedt verschillende manieren om dit te doen, waaronder echte hashtabellen (zie 18.1 Hash- tafelconcepten). Er zijn twee primaire manieren of de sleutel voor waardetoewijzingen in Common Lisp: eigenschappenlijsten en associatielijsten . Dit voorbeeld beschrijft eigenschappenlijsten.

Een eigenschappenlijst, of plist , is een "gewone" lijst waarin afwisselende waarden worden geïnterpreteerd als sleutels en de bijbehorende waarden. Bijvoorbeeld:

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

kan worden beschouwd als een eigenschappenlijst die symbolen toewijst die een persoonlijke naam aangeven met een geheel getal dat de leeftijd aangeeft. Het is mogelijk om enkele ophaalfuncties te implementeren met behulp van gewone lijstfuncties, zoals lid . Om bijvoorbeeld de leeftijd van john te achterhalen, zou men kunnen schrijven

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

Het lid functie retourneert de staart van de lijst begin met mary, d.w.z. (Mary 23 tim 72) en tweede terugkeer het tweede element van deze lijst, die is 23. Hoewel dit een manier is om toegang te krijgen tot waarden in een eigenschappenlijst, is het doel van een conventie zoals eigenschappenlijsten om de onderliggende weergave (een lijst) samen te vatten en functies op een hoger niveau te bieden voor het werken met de gegevensstructuur.

Voor eigenschappenlijsten is de ophaalfunctie getf , die de eigenschappenlijst, een sleutel (meestal een indicator genoemd ) en een optionele standaardwaarde gebruikt om terug te keren als de eigenschappenlijst geen waarde voor de sleutel bevat.

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

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

Voor het bijwerken van waarden in een eigenschappenlijst kan setf worden gebruikt. Wanneer John bijvoorbeeld jarig is en zijn leeftijd toeneemt, kan een van de volgende handelingen worden uitgevoerd:

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

(incf (getf *ages* 'john))

incf werkt in dit geval omdat het gebaseerd is op setf .

Gebruik get-properties om meerdere eigenschappen in een eigenschappenlijst in één keer op te zoeken.

De functie getf doorzoekt de lijst van links naar rechts, wat betekent dat het mogelijk is om waarden in een eigenschappenlijst te "maskeren" zonder ze uit een lijst te verwijderen of de structuur van de lijst bij te werken. Bijvoorbeeld met behulp van lijst * :

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

En nu zal een zoekopdracht voor Mary het eerste item retourneren:

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