Dữ liệu cấp bậc – Hierarchical Data và Tính bao đóng – Closure Property

Như chúng ta đã nhìn thấy các lợi ích trước đó của pair, pair như là một chất keo gắng kết hai hoặc nhiều data objects lại với nhau. Hình 2.2, đưa ra cách sơ khai để trình bày một pair – trong trường hợp này, pair được hình thành từ (cons 1 2). Nó được gọi là box-and-pointer, mỗi object được đưa ra như là một pointer đến một box. Một box chứa đựng các object nguyên thủy. Ví dụ, box đại diện cho số bao hàm chữ số. Box đại diện cho một pair thật ra nó chỉ là hai box nối lại, box bên trái bao gồm car của pair và phần bên phải bao gồm cdr.

Chúng ta đã nhìn thấy rằng, cons không chỉ được sử dụng để bao hàm các số mà còn có các pair. Vậy nên, pair tạo nên một sự đa dạng của building-block mà từ đó chúng ta có thể khới tạo việc sắp xếp tất các các cấu trúc dữ liệu. Hình 2.3 minh họa hai cách sử dụng pair để bao hàm các số 1 2 3 và 4.

Khả năng tạo ra các pair mà thành phần của nó lại là các pair là một sự hữu dụng cần thiết của cấu trúc danh sách được xem như là một sự trình bày hiệu quả nhất. Chúng ta có thể liên tưởng đến khả năng này như là điểm mạnh của cons. Nhìn chung, một toán tử bao hàm các data object thõa mãn tính “closure property” nếu kết quả của sự bao hàm những thứ với toán tử đó có thể chính nó cũng được bao hàm sử dụng cùng toán tử. Tính bao đóng – closure là điểm chính yếu mạnh mẽ nhất của bất kỳ sự bao hàm nào vì nó cho phép chúng ta tạo ra các cấu trúc dữ diệu thứ cấp(hierarchical structures) – cấu trúc đó được tạo nên từ các phần, mà chính phần đó cũng được tạo nên từ các phần khác…

Chúng ta đã nhìn thấy sự hữu dụng của tính bao đóng trong việc giải quyết các procedure, vì mỗi chương trình đơn giản nhất đều dựa vào thực tế rằng các thành phần của một sự kết hợp có thể chính các thành phần đó cũng tạo nên từ một sự kết hợp của các thành phần khác. Trong chương này, chúng ta sẽ thấy được sự tiện lợi của việc sử dụng tính bao đóng cho các compound data. Chúng ta sẽ diễn tả một vài kĩ thuật tiện ích trong việc sử dụng các pair để trình bày danh sách và tree, cũng như sự trình bày sinh động của ngôn ngữ đồ họa để chứng minh tính bao đóng trong một cách thật sự sinh động.

Bài viết tiếp theo: Representing Sequences