câu hỏi cơ bản về danh sách liên kết trong Lisp

Question

tôi đang đọc "Đất đai của Lisp" (đó là bằng cách này, một trong những cuốn sách kỹ thuật tốt nhất mà tôi đã từng đọc) và tôi đi qua danh sách hiệp hội

(defparameter *edges* 
    '((living-room (garden west door) 
        (attic upstairs ladder)) 
     (garden (living-room east door)) 
     (attic (living-room downstairs ladder)))) 

Đầu tiên, danh sách liên kết trong Lisp có cùng khái niệm về Bản đồ của Java (ràng buộc khóa-giá trị) không?
Đối với khóa phòng khách, làm cách nào để có thể có nhiều giá trị? tại sao không gửi kèm các giá trị với một danh sách:

(living-room ((garden west door) (attic upstairs ladder))) 

Answer 1

1. Vâng, danh sách liên kết là một cách để thể hiện các hiệp hội khóa giá trị. Các cấu trúc khác Common Lisp cung cấp cho kết thúc đó là các danh sách thuộc tính và các bảng băm.

2. Giá trị thực sự đã được chứa trong danh sách. Một nắm tay về cơ bản là một danh sách các cặp, trong đó chiếc xe của mỗi cặp là chìa khóa, và cdr là giá trị liên kết với khóa đó. Nếu bạn nhìn lên phòng khách chính với ASSOC và áp dụng CDR đến kết quả:

CL-USER> (cdr (assoc 'living-room *edges*)) 
((GARDEN WEST DOOR) (ATTIC UPSTAIRS LADDER)) 

Sự kỳ diệu đằng sau này nằm trong thực tế là một cặp mà xe là living-room và có cdr là danh sách các hai phần tử (garden west door) và (attic upstairs ladder) cũng có thể được xem dưới dạng danh sách ba phần tử (living-room (garden west door) (attic upstairs ladder)), do danh sách cách được xây dựng theo cặp.

Thông thường khi đại diện alists như các đối tượng được trích dẫn, bạn sẽ thấy các yếu tố miêu tả một cách rõ ràng với các cặp chấm, chứ không phải là punning với ký hiệu danh sách, như vậy:

 
(defparameter *edges* 
    '((living-room . ((garden west door) 
        (attic upstairs ladder))) 
    (garden . ((living-room east door))) 
    (attic . ((living-room downstairs ladder))))) 

Answer 2

Thứ nhất, là danh sách liên kết trong Lisp giống nhau khái niệm về Bản đồ của Java (ràng buộc khóa-giá trị)?

Bản đồ của Java là giao diện. Một alist là một cách cụ thể của việc sử dụng một danh sách (liên kết) để lưu trữ các cặp khóa-giá trị. Tôi không nghĩ Java có bất kỳ Bản đồ tích hợp nào có các thuộc tính giống như một nắm tay, nhưng sẽ không khó để viết một. Vì alist là một danh sách, tất cả các hàm và thuộc tính của danh sách vẫn giữ.

Đối với khóa phòng khách, làm cách nào để có thể có nhiều giá trị? tại sao không để kèm theo giá trị với danh sách:

An alist không phải là một phần của cú pháp Lisp. Nó chỉ là một danh sách, vì vậy bạn có thể đặt bất cứ điều gì bạn muốn trong CDR của mỗi phần tử. Trong trường hợp này, đó là một ô KHÁC. ASSOC chỉ xem CAR của từng phần tử.

(assoc 'living-room *edges*) 
(LIVING-ROOM (GARDEN WEST DOOR) (ATTIC UPSTAIRS LADDER)) 

Answer 3

Một danh sách hiệp hội cũng tương tự như trong khái niệm để bản đồ, trong chừng mực cả hai phím kết hợp với các giá trị.

Không cần phải kèm theo nhiều giá trị trong danh sách khác, vì điều đó thay đổi ý nghĩa của giá trị.Tôi không quen thuộc với cuốn sách này, nhưng có vẻ như cách mà *EDGES* được định nghĩa, tác giả muốn

(cdr (assoc 'Foobar *edges*)) 

trở thành một danh sách những nơi mà bạn có thể nhận được từ Foobar. Theo định nghĩa, điều này đúng nếu có một hoặc nhiều giá trị.

Nếu, khi có nhiều giá trị, bạn lồng nhau các giá trị đó trong danh sách khác, thì bạn chỉ cần chọn chúng ra khỏi danh sách đó khi bạn muốn sử dụng chúng. Nó sẽ không cung cấp cho bạn bất cứ điều gì, và nó sẽ làm cho nó khác với trường hợp giá trị duy nhất.

Answer 4

ASSOC trả về ô khuyết điểm và do đó bao gồm cả khóa và giá trị.

Lý do là điều này giúp dễ dàng cập nhật giá trị (hoặc khóa) một cách triệt để.

Đây là bản cập nhật được ẩn đằng sau SETF:

CL-USER 11 > (defparameter *edges* 
       (copy-tree 
       '((living-room (garden west door) 
           (attic upstairs ladder)) 
        (garden (living-room east door)) 
        (attic (living-room downstairs ladder))))) 
*EDGES* 

CL-USER 12 > (assoc 'living-room *edges*) 
(LIVING-ROOM (GARDEN WEST DOOR) (ATTIC UPSTAIRS LADDER)) 

CL-USER 13 > (cdr (assoc 'living-room *edges*)) 
((GARDEN WEST DOOR) (ATTIC UPSTAIRS LADDER)) 

CL-USER 14 > (setf (cdr (assoc 'living-room *edges*)) '((garden east door))) 
((GARDEN EAST DOOR)) 

CL-USER 15 > (cdr (assoc 'living-room *edges*)) 
((GARDEN EAST DOOR))