common-lisp
Wady komórek i list

Listy jako konwencja

Niektóre języki zawierają strukturę danych listy. Wspólne Lisp i inne języki w rodzinie Lisp często korzystają z list (a nazwa Lisp jest oparta na idei procesora LISt). Jednak Common Lisp tak naprawdę nie zawiera pierwotnego typu danych listy. Zamiast tego listy istnieją zgodnie z konwencją. Konwencja zależy od dwóch zasad:

1. Symbol zero to pusta lista.
2. Niepusta lista to komórka przeciw, której samochód jest pierwszym elementem listy, a której cdr jest resztą listy.

To wszystko, co jest na listach. Jeśli znasz przykład o nazwie Co to jest komórka przeciw? , to wiesz, że komórkę przeciw, której samochód to X, a której cdr to Y, można zapisać jako (X. Y) . Oznacza to, że możemy napisać kilka list w oparciu o powyższe zasady. Lista elementów 1, 2 i 3 jest po prostu:

(1 . (2 . (3 . nil)))

Ponieważ jednak listy są tak powszechne w rodzinie języków Lisp, istnieją specjalne konwencje drukowania poza prostą notacją par kropkowanych dla komórek przeciw.

1. Symbol zero można również zapisać jako () .
2. Gdy cdr jednej komórki przeciwnej jest inną listą (albo () albo komórką przeciwną), zamiast pisać jedną komórkę przeciwną notacją z kropkami, stosuje się „notację listy”.

Notację listy najlepiej pokazuje kilka przykładów:

(x . (y . z))   === (x y . z)
(x . NIL)       === (x)
(1 . (2 . NIL)) === (1 2)
(1 . ())        === (1)

Chodzi o to, że elementy listy są zapisywane w kolejności w nawiasach, aż do osiągnięcia końcowego cdr na liście. Jeśli końcowy cdr wynosi zero (pusta lista), zapisywany jest ostatni nawias. Jeśli końcowy cdr nie jest równy zero (w takim przypadku lista nazywana jest listą niewłaściwą ), wówczas zapisywana jest kropka, a następnie zapisywane jest końcowe cdr.

Co to jest komórka przeciw

Komórka przeciw, znana również jako kropkowana para (ze względu na jej drukowaną reprezentację), jest po prostu parą dwóch obiektów. Komórka Cons jest tworzona przez funkcję cons , a elementy w parze są wyodrębniane za pomocą funkcji car i cdr .

(cons "a" 4)

Na przykład zwraca parę, której pierwszym elementem (który można wyodrębnić za pomocą car ) jest "a" , a drugim elementem (który można wyodrębnić za pomocą cdr ), jest 4 .

(car (cons "a" 4))
;;=> "a"

(cdr (cons "a" 4))
;;=> 3

Wady można wydrukować w notacji z kropkami :

(cons 1 2)
;;=> (1 . 2)

Wady komórek można również odczytać w notacji pary kropkowanej, dzięki czemu

(car '(x . 5))
;;=> x

(cdr '(x . 5))
;;=> 5

(Drukowana forma komórek przeciw może być również nieco bardziej skomplikowana. Aby uzyskać więcej informacji, zobacz przykład dotyczący komórek przeciw jako list.)

Otóż to; komórki Cons to tylko pary elementów utworzonych przez funkcję cons , a elementy można wyodrębnić za pomocą car i cdr . Ze względu na swoją prostotę, wady komórki mogą być użytecznym elementem składowym dla bardziej złożonych struktur danych.

Szkicowanie minusów

Aby lepiej zrozumieć semantykę stożków i list, często stosuje się graficzną reprezentację tego rodzaju struktur. Komórka przeciwna jest zwykle reprezentowana przez dwa pola w kontakcie, które zawierają albo dwie strzałki wskazujące na car i wartości cdr , albo bezpośrednio wartości. Na przykład wynik:

(cons 1 2)   
;; -> (1 . 2)

można przedstawić za pomocą jednego z tych rysunków:

Należy zauważyć, że te reprezentacje są czysto koncepcyjne i nie oznaczają faktu, że wartości są zawarte w komórce lub są wskazane z komórki: ogólnie zależy to od implementacji, rodzaju wartości, poziomu optymalizacji itp. W pozostałej części przykładu użyjemy pierwszego rodzaju rysunku, który jest najczęściej używany.

Na przykład:

(cons 1 (cons 2 (cons 3 4)))   ; improper “dotted” list
;; -> (1 2 3 . 4)

jest reprezentowany jako:

podczas:

(cons 1 (cons 2 (cons 3 (cons 4 nil))))  ;; proper list, equivalent to: (list 1 2 3 4)
;; -> (1 2 3 4)

jest reprezentowany jako:

Oto struktura przypominająca drzewo:

(cons (cons 1 2) (cons 3 4))
;; -> ((1 . 2) 3 . 4)         ; note the printing as an improper list

Ostatni przykład pokazuje, w jaki sposób ta notacja może pomóc nam zrozumieć ważne aspekty semantyki języka. Najpierw piszemy wyrażenie podobne do poprzedniego:

(cons (cons 1 2) (cons 1 2))
;; -> ((1 . 2) 1 . 2)

które można przedstawić w zwykły sposób jako:

Następnie piszemy inne wyrażenie, które najwyraźniej jest równoważne z poprzednim, i wydaje się to potwierdzone wydrukowaną reprezentacją wyniku:

(let ((cell-a (cons 1 2)))
  (cons cell-a cell-a))
;; -> ((1 . 2) 1 . 2)

Ale jeśli narysujemy schemat, możemy zobaczyć, że semantyka wyrażenia jest inna, ponieważ ta sama komórka jest wartością zarówno części car i części cdr zewnętrznych cons (to znaczy, cell-a jest wspólna ) :

a fakt, że semantyka dwóch wyników jest różna na poziomie języka, można zweryfikować za pomocą następujących testów:

(let ((c1 (cons (cons 1 2) (cons 1 2)))
      (c2 (let ((cell-a (cons 1 2)))
            (cons cell-a cell-a))))
  (list (eq (car c1) (cdr c1))
        (eq (car c2) (cdr c2)))
;; -> (NIL T)

Pierwszy eq jest fałszywy, ponieważ car i cdr c1 są strukturalnie równe (to jest prawda przez equal ), ale nie są „identyczne” (tj. „Ta sama wspólna struktura”), podczas gdy w drugim teście wynik jest prawdziwy, ponieważ car i cdr z c2 są identyczne , to znaczy mają taką samą strukturę .