Tại sao bạn phải chống lại với một giá trị rỗng để có danh sách phù hợp trong lược đồ?

Question

Tôi nhận ra đây là một câu hỏi đầy đủ về n00b, nhưng tôi tò mò và tôi nghĩ tôi có thể giải thích rõ hơn ở bất cứ nơi nào khác. Dưới đây là một danh sách (Tôi đang sử dụng TS Scheme)

> (list 1 2 3) 
(1 2 3) 

Mà tôi nghĩ là chỉ đường cho việc này:

> (cons 1 (cons 2 (cons 3 null))) 
(1 2 3) 

này, mặt khác, làm điều gì đó khác:

> (cons 1 (cons 2 3)) 
(1 2 . 3) 

Câu hỏi của tôi là, tại sao lại khác? Điểm yêu cầu null ở cuối danh sách là gì?

Answer 1

Định nghĩa của danh sách là đệ quy.

1. The null list (empty list) is a list 
2. A list is made up of an item cons a list 

Vì vậy, đây là những danh sách:

1. null =>() --read as empty list 
2. cons 3 null => (3) 
3. cons2 (cons 3 null) => (2, 3) 

Ví dụ cuối cùng bạn đã khuyết điểm 2 3 không phù hợp với định nghĩa danh sách này vì vậy nó không phải là một danh sách. Đó là khuyết điểm chấp nhận một mục và một danh sách. 3 không phải là một danh sách.

Answer 2

cons thêm một yếu tố mới để bắt đầu một danh sách, vì vậy những gì bạn đang làm khi bạn viết:

(cons 1 (cons 2 (cons 3 null))) 

được đệ quy thêm các mục vào một danh sách ngày càng tăng, bắt đầu với null, đó là được định nghĩa là danh sách trống(). Khi bạn gọi (cons 2 3) bạn không bắt đầu với danh sách trống để bắt đầu, do đó, không xây dựng danh sách bằng cách thêm 2 vào đầu của danh sách.

Answer 3

Một tuyên bố khuyết điểm được sử dụng để phân bổ một cặp mà xe là obj1 và có cdr là obj2

(cons obj1 obj2) 

Vì vậy, nó là cần thiết để chấm dứt một tuyên bố phản đối với một null để chúng tôi biết chúng tôi là cuối cùng của danh sách.

> (cons 1 (cons 2 3)) 
(1 2 . 3) 

Trong ví dụ đó, cdr sẽ là một cặp < 2,3> trong đó 2 là ô tô và 3 là cdr. Không giống như:

(list 1 2 3) 

Answer 4

Lisps, trong đó có Đề án, được tự động gõ, và 'cách lisp' là phải có nhiều chức năng trong một cấu trúc dữ liệu duy nhất chứ không phải là cấu trúc dữ liệu khác nhau cho các nhiệm vụ khác nhau.

Vì vậy, câu hỏi "Điểm yêu cầu null ở cuối danh sách là gì?" không phải là người thích hợp để hỏi.

Chức năng cons không yêu cầu bạn cung cấp đối tượng cons hoặc nil làm đối số thứ hai. Nếu đối số thứ hai không phải là đối tượng cons hoặc nil, thì bạn sẽ nhận được một cặp thay vì danh sách và thời gian chạy không in ra bằng ký hiệu danh sách nhưng có dấu chấm.

Vì vậy, nếu bạn muốn xây dựng thứ gì đó có hình dạng giống như danh sách, hãy cung cấp cons danh sách làm đối số thứ hai.Nếu bạn muốn xây dựng một cái gì đó khác, sau đó cung cấp cho cons một cái gì đó khác như đối số thứ hai của nó.

Cặp hữu ích nếu bạn muốn cấu trúc dữ liệu có chính xác hai giá trị trong đó. Với một cặp, bạn không cần nil ở cuối để đánh dấu chiều dài của nó, vì vậy nó có hiệu quả hơn một chút. Một danh sách các cặp là việc thực hiện đơn giản một bản đồ của khóa để định giá; lisp thông thường có chức năng hỗ trợ danh sách thuộc tính như là một phần của thư viện chuẩn của nó. Vì vậy, câu hỏi thực sự là "tại sao bạn có thể xây dựng cả hai cặp và danh sách với cùng một hàm cons?" Và câu trả lời là "tại sao có hai cấu trúc dữ liệu khi bạn chỉ cần một?"