Jaka jest definicja komórki Lisp Cons?

Question

Czym dokładnie jest definicja wspólnej komórki Lisp? Czym różni się Cell Cons od standardowego elementu listy powiązanej? W końcu zarówno komórka cons, jak i pozycja listy połączonej mają wartość i wskaźnik do następnej komórki lub elementu ... czy to zrozumienie jest złe?

Answer 1

Komórki cons ogólnie mają dwa wskaźniki, które mogą wskazywać na wszystko. Ogólnym zastosowaniem oczywiście jest wskazanie "wartości" lewej i innej komórki Cons (lub zerowej) z "prawą".

Answer 2

Komórka jest bliżej węzła drzewa binarnego niż połączonego węzła listy. car i cdr zwracają dwójkę dzieci, które mogą być zerowe, atomy lub inne komórki cons.

Answer 3

W Lisp komórka po stronie zawiera parę wartości. Jeśli komórka cons jest w zmiennej c, to (car c) zwraca pierwszą wartość, a (cdr c) zwraca drugą.

Zgodnie z przyjętą konwencją lista składa się z komórek cons, gdzie car komórki zawiera wartość węzła, a cdr zawiera odniesienie do następnego węzła lub zera (pusta lista) w celu wskazania końca listy. Kiedy funkcje pierwotne zwracają lub akceptują listy, jest to format, w którym lista jest prezentowana.

Dlatego do listy l, (car l) daje pierwszy element (wartość w pierwszym cons komórki) oraz (cdr l) przywraca końca listy (następny przeciw komórki na liście).

Answer 4

Myślę, że inne odpowiedzi tutaj, choć dokładne, nie mówią jednoznacznie o jednym.

W tradycyjnym C++ połączone realizacji liście, dwa pola (val i next, powiedzmy) są wpisane. next jest zdefiniowany jako wskazujący na inny węzeł na liście, przy czym terminatorem jest null. Nie możesz wskazać niczego, co jest , ale inny węzeł z next.

Lispy są wpisywane dynamicznie, więc każde pole w komórce może być dowolne () (albo atom, albo odniesienie). Możesz zaimplementować połączoną listę z komórkami cons (to wszystko lista Lisp to: łańcuch komórek cons z terminatorem nil), ale możesz także umieścić dowolne wartości w każdym polu, używając komórki cons jako pary współrzędnych, drzewa węzeł itp.

Można nawet połączyć te; na przykład, wykaz xy Współrzędne

;; (cons foo (cons bar nil)) == (list foo bar)  
(cons 
    (cons 5 4) 
    (cons (cons 9 10) nil)) 
=> 
((5 . 4) (9 . 10)) 

wagonika komórka jest zatem ściśle szersze niż połączonego węzła liście; jest bliżej "zastosowanej pary", że tak powiem. Wszystkie standardowe funkcje przetwarzania listy (, dolist, itp.) To po prostu funkcje, które przyjmują wartości car i inną listę w cdr.

Wszystko to oznacza, że ​​- jeśli chce - można zdefiniować listy tyłu z car skierowaną do następnego cons komórki i cdr wskazując na wartości! Aby to zrobić z połączonym węzłem listy, musisz zmienić definicję klasy lub struktury danych, aby zmienić typy.

Answer 5

cons komórek jest jedną trzecią umowy obejmującej cons, car i cdr z wymogiem jest, że zachowują się one jako pary, ponieważ wspomnieli.

Powodem pominięcia w tej definicji słów "odniesienie", "wskaźnik" itd. Jest uznanie, że są to szczegóły dotyczące implementacji. Jeśli chcesz, możesz zbudować cons z powietrza, jak Abelson i Sussman zrobił:

(define (cons a b) (lambda (x) (x a b))) 
(define (car x) (x (lambda (a b) a))) 
(define (cdr x) (x (lambda (a b) b))) 

Definicja ta żyje całkowicie wewnątrz świata Lisp w definicji i funkcji, a nawet nie zatrzymać do rozważenia, czy obiekty są przechowywane jako wartości lub odniesienia; jednak mogą one służyć jako zamienniki zastępcze dla obiektów pierwotnych (nie biorąc pod uwagę zmienności lub innych specjalnych zastosowań).