common-lisp
Rodzaje list

Zwykłe listy

Listy zwykłe są najprostszym typem listy w Common Lisp. Są uporządkowaną sekwencją elementów. Obsługują podstawowe operacje, takie jak uzyskanie pierwszego elementu listy i reszty listy w stałym czasie, obsługują losowy dostęp w czasie liniowym.

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

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

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

Istnieje wiele funkcji, które działają na „zwykłych” listach, o ile dbają tylko o elementy listy. Należą do nich find , mapcar i wiele innych. (Wiele z tych funkcji będzie działać również w Pojęciach sekwencji 17.1 dla niektórych z tych funkcji.

Listy stowarzyszeń

Proste listy są przydatne do reprezentowania sekwencji elementów, ale czasem bardziej pomocne jest reprezentowanie pewnego rodzaju klucza do mapowania wartości. Common Lisp oferuje kilka sposobów na zrobienie tego, w tym autentyczne tabele skrótów (patrz 18.1 Pojęcia dotyczące tabeli skrótów). Istnieją dwa podstawowe sposoby reprezentowania odwzorowań klucz do wartości w Common Lisp: listy właściwości i listy skojarzeń . W tym przykładzie opisano listy skojarzeń.

Lista asocjacyjna lub lista alist to „zwykła” lista, której elementy to kropkowane pary, w których samochód każdej pary jest kluczem, a cdr każdej pary jest powiązaną wartością. Na przykład,

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

można uznać za listę skojarzeń, która odwzorowuje symbole wskazujące nazwisko z liczbą całkowitą wskazującą wiek. Możliwe jest zaimplementowanie niektórych funkcji pobierania za pomocą prostych funkcji listy, takich jak member . Na przykład, aby odzyskać wiek Jana , można napisać

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

Funkcja członka zwraca ogon listy zaczynający się od komórki przeciwnej, której samochód to Mary , czyli ((mary. 23) (tim. 72)) , najpierw zwraca pierwszy element tej listy, czyli (mary. 23) , a cdr zwraca prawą stronę tej pary, czyli 23 . Chociaż jest to jeden ze sposobów uzyskania dostępu do wartości na liście asocjacji, celem konwencji takiej jak listy asocjacji jest oderwanie się od podstawowej reprezentacji (listy) i zapewnienie funkcji wyższego poziomu do pracy ze strukturą danych.

W przypadku list asocjacyjnych funkcją pobierania jest assoc , który pobiera klucz, listę asocjacji i opcjonalne słowa kluczowe testowe (klucz, test, test-not) i zwraca parę dla odpowiedniego klucza:

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

Ponieważ wynikiem zawsze będzie komórka przeciw, jeśli element jest obecny, jeśli assoc zwróci zero , to elementu nie było na liście:

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

Do aktualizacji wartości na liście asocjacji można użyć setf wraz z cdr . Na przykład, gdy nadejdą urodziny Johna i jego wiek wzrośnie, można wykonać jedną z następujących czynności:

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

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

incf działa w tym przypadku, ponieważ jest oparte na setf .

Listy asocjacyjne mogą być również używane jako rodzaj mapy dwukierunkowej, ponieważ mapowania klucza do wartości można pobierać na podstawie wartości za pomocą funkcji odwróconego assoc, rassoc .

W tym przykładzie lista powiązań została utworzona przy użyciu jawnej listy i wad , ale listy powiązań można również utworzyć przy użyciu pairlis , który pobiera listę kluczy i danych i tworzy na ich podstawie listę powiązań:

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

Pojedynczą parę klucz i wartość można dodać do listy skojarzeń za pomocą aconów :

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

Funkcja assoc przeszukuje listę od lewej do prawej, co oznacza, że możliwe jest „maskowanie” wartości na liście powiązań bez usuwania ich z listy lub aktualizowania jakiejkolwiek struktury listy, po prostu poprzez dodanie nowych elementów do początek listy. W tym celu przewidziano funkcję acons :

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

A teraz wyszukiwanie Mary zwróci pierwszy wpis:

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

Listy nieruchomości

Proste listy są przydatne do reprezentowania sekwencji elementów, ale czasem bardziej pomocne jest reprezentowanie pewnego rodzaju klucza do mapowania wartości. Common Lisp oferuje kilka sposobów na zrobienie tego, w tym autentyczne tabele skrótów (patrz 18.1 Pojęcia dotyczące tabeli skrótów). Istnieją dwa podstawowe sposoby reprezentowania odwzorowań klucz do wartości w Common Lisp: listy właściwości i listy skojarzeń . W tym przykładzie opisano listy właściwości.

Lista nieruchomość lub plist, jest to „zwykły” list, w którym na przemian wartości są interpretowane jako kluczy i powiązanych z nimi wartości. Na przykład:

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

można uznać za listę właściwości odwzorowującą symbole wskazujące imię i nazwisko z liczbą całkowitą wskazującą wiek. Możliwe jest zaimplementowanie niektórych funkcji pobierania za pomocą prostych funkcji listy, takich jak member . Na przykład, aby odzyskać wiek Jana , można napisać

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

Funkcja członka zwraca ogon listy zaczynający się od mary , czyli (mary 23 tim 72) , a drugi zwraca drugi element tej listy, czyli 23 . Chociaż jest to jeden ze sposobów dostępu do wartości na liście właściwości, celem konwencji takiej jak listy właściwości jest oderwanie się od podstawowej reprezentacji (listy) i zapewnienie funkcji wyższego poziomu do pracy ze strukturą danych.

W przypadku list właściwości funkcją pobierania jest getf , która pobiera listę właściwości, klucz (częściej nazywany wskaźnikiem ) i opcjonalną wartość domyślną do zwrócenia w przypadku, gdy lista właściwości nie zawiera wartości klucza.

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

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

Do aktualizacji wartości na liście właściwości można użyć setf . Na przykład, gdy nadejdą urodziny Johna i jego wiek wzrośnie, można wykonać jedną z następujących czynności:

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

(incf (getf *ages* 'john))

incf działa w tym przypadku, ponieważ jest oparte na setf .

Aby wyszukać wiele właściwości na liście właściwości jak jeden raz, użyj get-properties .

Funkcja getf przeszukuje listę od lewej do prawej, co oznacza, że możliwe jest „maskowanie” wartości na liście właściwości bez usuwania ich z listy lub aktualizowania dowolnej struktury listy. Na przykład za pomocą listy * :

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

A teraz wyszukiwanie Mary zwróci pierwszy wpis:

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