Trình bày các sequence – danh sách liên kết.

Một trong những cấu trúc hữu dụng chúng ta có thể tạo nên với pair là một sự liên tiếp (sequence) – một bộ sưu tập của các data object đã được sắp xếp. Vì vậy, có nhiều các để trình bày các sequence trong các điều khoản của pair. Một cách trình bày đơn giản được biểu thị ở hình 2.4, danh sách 1 2 3 và 4 được trình bày như là một chuỗi các pairs. Car của mỗi pair tương ứng với item trong chuỗi, và cdr của pair là pair tiếp theo của chuỗi.

Cdr của pair cuối (kết thúc danh sách) trỏ đến một giá trị không xác định nó không phải là một pair, việc trình bày minh họa box-and-pointer với một dòng tương ứng và trong các chương trình gí trị của biến đó là nil (null) . Toàn bộ danh sách được khởi tạo bởi việc lồng các toán tử cons:

(cons 1
       (cons 2
             (cons 3
                   (cons 4 nil))))

Như là một sequence của các pair, được hình thành từ việc lồng các cons (constructor), được gọi là list, và Lisp cung cấp một khai báo nguyên thủy được gọi là list để giúp bạn khởi tạo list. Sequence ở trên có thể được tạo ra bởi (list 1 2 3 4).

(list ⟨a1⟩ ⟨a2⟩ . . . ⟨an⟩)

Bằng với việc tạo list sử dụng cons

(cons ⟨a1⟩
      (cons ⟨a2⟩
            (cons . . .
                    (cons ⟨an⟩
                          nil). . .)))

Việc in các list ta chỉ việc in tuần tự các thành phần của nó, bao đóng trong dấu ngoặc đơn (). Các data object ở hình được in ra như là (1 2 3 4)

(define one-through-four (list 1 2 3 4))
one-through-four
(1 2 3 4)

Chúng ta có thể nghĩ car là chọn phần tử đầu tiên trong list, và cdr là chọn phần còn lại của list ngoại trừ phần tử đầu tiên. Các ứng dụng lồng nhau có thể sử dụng car và cdr để truy xuất giá trị thứ hai, ba và các item còn lại trong list.

(car one-through-four)
1
(cdr one-through-four)
(2 3 4)
(car (cdr one-through-four))
2
(cons 10 one-through-four)
(10 1 2 3 4)
(cons 5 one-through-four)
(5 1 2 3 4)

Giá trị của nil, được sử dụng để kết thúc chuỗi pair, xem như là một liên kết không phần tử, list trông. Từ nil là kí tự Latin nihil, có nghĩa là “nothing” – “không gì cả”.

Danh sách toán tử của list

Việc sử dụng pair để trình bày liên kết của các thành phần như list đạt được bởi các kỹ thuật lập trình cơ bản cho việc thao tác list liên tục “cdr lấy số lượng phần tử giảm dần”. Ví dụ, procedure list-ref với các đối số là một list, một số n và trả về item ở vị trí thứ n trong list. Số lượng phần tử của list bắt đầu với 0. Phương thức tính toán list-ref như sau:

• Với n là 0, list-ref nên trả về car của list.
• Ngược lại, list-ref nên trả về item thứ (n-1) của cdr của list.

(define (list-ref items n)
        (if (= n 0)
            (car items)
            (list-ref (cdr items) (- n 1))))
(define squares (list 1 4 9 16 25))
(list-ref squares 3)
16

Oen we cdr down the whole list. To aid in this, Scheme includes a
primitive predicate null?, which tests whether its argument is the empty
list. e procedure length, which returns the number of items in a list,
illustrates this typical paern of use:

Thông thường chúng ta sử dụng cdr để giảm kích thước của toàn bộ list. Để hỗ trợ việc này, Lisp bao gồm một predict nguyên thủy null?, nó kiểm tra xem liệu rằng đối số đó là một list trống hay không. Procedure length, nó return số lượng phần tử của list, biễu diễn dưới dạng như sau:

(define (length items)
        (if (null? items)
               0
            (+ 1 (length (cdr items)))))
(define odds (list 1 3 5 7))
(length odds)
4

Procedure length thực thi một quy trình đệ quy đơn giản. Các bươc tính toán giảm xuống đến khi list null.

• Độ dài của list là môt + với độ dài cdr phần còn lại của list.
  is is applied successively until we reach the base case:
• Áp dụng liên tục cho tới trường hợp cơ bàn là độ dài của một list trông là 0.

Chúng ta cũng có thẻ tính độ dài của list sử dụng vòng lặp như sau:

(define (length items)
    (define (length-iter a count)
              (if (null? a)
                    count
              (length-iter (cdr a) (+ 1 count))))
    (length-iter items 0))

Một kĩ thuật lập trình hiệu quả khác là “cons” dùng để tăng list ban đầu, trong khi “cdr” làm giảm kích thước list ban đầu. Để thực thi tăng list, ta sử dụng thủ tục append, ý tưởng như sau. Procedure cần hai list và bao gồm các thành phần của nó đẻ tạo ra một list mới.

(append squares odds)
(1 4 9 16 25 1 3 5 7)
(append odds squares)
(1 3 5 7 1 4 9 16 25)

Thủ tục append cũng thực thi dựa trên tiến trình đệ quy. Đê append list 1 và 2 ta làm như sau

• Nếu list 1 trống, thì kết quả là list 2.
• Ngược lại, append “cdr” của list 1 và list 2, và cons của car list 1 vào kết quả

(define (append list1 list2)
        (if (null? list1)
             list2
             (cons (car list1) (append (cdr list1) list2))))

Bài viết tiếp theo: Hierarchical Structures