common-lisp
Typer av listor
Sök…
Vanliga listor
Vanliga listor är den enklaste listan i Common Lisp. De är en ordnad sekvens av element. De stöder grundläggande operationer som att få det första elementet i en lista och resten av en lista i konstant tid, stöder slumpmässig åtkomst i linjär tid.
(list 1 2 3)
;=> (1 2 3)
(first (list 1 2 3))
;=> 1
(rest (list 1 2 3))
;=> (2 3)
Det finns många funktioner som fungerar på "vanliga" listor, i den mån de bara bryr sig om listans element. Dessa inkluderar fynd , kartbil och många andra. (Många av dessa funktioner fungerar också på 17.1 Sekvensbegrepp för några av dessa funktioner.
Föreningslistor
Vanliga listor är användbara för att representera en sekvens av element, men ibland är det mer användbart att representera en typ av nyckel till värdekartläggning. Common Lisp tillhandahåller flera sätt att göra detta, inklusive äkta hash-tabeller (se 18.1 Hash-tabellkoncept ). Det finns två huvudsakliga sätt eller representerar nycklar till värdekartläggningar i Common Lisp: fastighetslistor och associeringslistor . Detta exempel beskriver associeringslistor.
En associeringslista, eller alist, är en "vanlig" lista vars element är prickade par där bilen för varje par är nyckeln och cdr för varje par är det tillhörande värdet. Till exempel,
(defparameter *ages* (list (cons 'john 34) (cons 'mary 23) (cons 'tim 72)))
kan betraktas som en associeringslista som kartlägger symboler som indikerar ett personligt namn med ett heltal som indikerar ålder. Det är möjligt att implementera vissa hämtningsfunktioner med hjälp av vanliga listfunktioner, som medlem . Till exempel, för att hämta john- åldern, kan man skriva
(cdr (first (member 'mary *age* :key 'car)))
;=> 23
Delfunktionen returnerar svansen på listan som börjar med med en cons cell vars bil är mary, det vill säga ((mary. 23) (tim. 72)), första returnerar det första elementet i den listan, som är (mary. 23) , och cdr returnerar höger sida av paret, som är 23 . Även om detta är ett sätt att få tillgång till värden i en associeringslista, är syftet med en konvention som associeringslistor att abstrahera bort från den underliggande representationen (en lista) och att tillhandahålla funktioner på högre nivå för att arbeta med datastrukturen.
För associeringslistor är hämtningsfunktionen associerad , som tar en nyckel, en associeringslista och valbara testnyckelord (nyckel, test, test-inte) och returnerar paret för motsvarande nyckel:
(assoc 'tim *ages*)
;=> (tim . 72)
Eftersom resultatet alltid kommer att vara en nackcell om ett objekt finns, om assoc returnerar noll , så var inte objektet i listan:
(assoc 'bob *ages*)
;=> nil
För att uppdatera värden i en associeringslista kan setf användas tillsammans med cdr . Till exempel, när johns födelsedag anländer och hans ålder ökar, kan något av följande utföras:
(setf (cdr (assoc 'john *ages*) 35)
(incf (cdr (assoc 'john *ages*)))
incf fungerar i det här fallet eftersom det är baserat på setf .
Associeringslistor kan också användas som en typ av dubbelriktad karta, eftersom nyckeln till värdekartläggningar hämtas baserat på värdet med hjälp av den omvända associeringsfunktionen, rassoc .
I det här exemplet skapades associeringslistan genom att använda lista och nackdelar uttryckligen, men associeringslistor kan också skapas med hjälp av parlis , som tar en lista med nycklar och data och skapar en associeringslista baserad på dem:
(pairlis '(john mary tim) '(23 67 82))
;=> ((john . 23) (mary . 67) (tim . 82))
En enda nyckel- och värdepar kan läggas till i en associeringslista med hjälp av acons :
(acons 'john 23 '((mary . 67) (tim . 82)))
;=> ((john . 23) (mary . 67) (tim . 82))
Associeringsfunktionen söker igenom listan från vänster till höger, vilket innebär att det är möjligt att "maskera" värden i en associeringslista utan att ta bort dem från en lista eller uppdatera någon av listans struktur, bara genom att lägga till nya element i början av listan. Acons- funktionen tillhandahålls för detta:
(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))
Och nu kommer en uppslagning efter Mary att returnera det första inlägget:
(assoc 'mary *new-ages*)
;=> 29
Fastighetslistor
Vanliga listor är användbara för att representera en sekvens av element, men ibland är det mer användbart att representera en typ av nyckel till värdekartläggning. Common Lisp tillhandahåller flera sätt att göra detta, inklusive äkta hash-tabeller (se 18.1 Hash-tabellkoncept ). Det finns två huvudsakliga sätt eller representerar nycklar till värdekartläggningar i Common Lisp: fastighetslistor och associeringslistor . Detta exempel beskriver egendomslistor.
En egenskapslista, eller plist , är en "vanlig" lista där alternerande värden tolkas som nycklar och deras tillhörande värden. Till exempel:
(defparameter *ages* (list 'john 34 'mary 23 'tim 72))
kan betraktas som en egenskapslista som kartlägger symboler som anger ett personligt namn med ett heltal som indikerar ålder. Det är möjligt att implementera vissa hämtningsfunktioner med hjälp av vanliga listfunktioner, som medlem . Till exempel, för att hämta john- åldern, kan man skriva
(second (member 'mary *age*))
;=> 23
Medlemsfunktionen returnerar svansen på listan som börjar med mary , det vill säga (mary 23 tim 72) , och den andra returnerar det andra elementet i listan, det vill säga 23 . Även om detta är ett sätt att få tillgång till värden i en fastighetslista, är syftet med en konvention som egendomslistor att abstrahera bort från den underliggande representationen (en lista) och att tillhandahålla funktioner på högre nivå för att arbeta med datastrukturen.
För egenskapslistor är återvinningsfunktionen getf , som tar egendomslistan, en nyckel (oftare kallas en indikator ) och ett valfritt standardvärde för att returnera i fall fastighetslistan inte innehåller ett värde för nyckeln.
(getf *ages* 'tim)
;=> 72
(getf *ages* 'bob -1)
;=> -1
För att uppdatera värden i en fastighetslista kan setf användas. Till exempel, när johns födelsedag anländer och hans ålder ökar, kan något av följande utföras:
(setf (getf *ages* 'john) 35)
(incf (getf *ages* 'john))
incf fungerar i det här fallet eftersom det är baserat på setf .
För att slå upp flera egenskaper i en fastighetslista som en gång använder du get-egenskaper .
Getf- funktionen söker igenom listan från vänster till höger, vilket innebär att det är möjligt att "maskera" värden i en fastighetslista utan att ta bort dem från en lista eller uppdatera någon av listans struktur. Använd till exempel 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)
Och nu kommer en uppslagning efter Mary att returnera det första inlägget:
(getf *new-ages* 'mary)
;=> 29