Với dữ liệu phức hợp, chúng ta thấy nó phức tạp hơn về cách các data abstraction cho phép thiết kế các chương trình không cần cứng nhắc trong việc trình bày chi tiết dữ liệu, và cách các abstraction đóng gói dữ liệu cho chúng ta sử dụng một cách linh hoạt hơn. Trong bài này, chúng ta sẽ tìm hiểu một nguyên tắc thiết kế khác để làm việc với data structure – sử dụng như là các interfaces.
Trong bài này chúng ta đã tìm iểu cách abstraction chương trình thực thi như là các procedure bậc cao, có thể bắt gặp các mô hình phổ biến trong các chương trình làm việc với dữ liệu số. Khả năng công thức hóa các toán tử tương ứng để làm việc với các dữ liệu phức hợp phụ thuộc vào phong cách thiết kế dữ liệu, theo cách thích hợp mà chúng ta có thể thao tác dữ liệu. Xem ví dụ sau, tương ứng với procedure count-leaves ở bài trước, nó nhận một tree là đối số và tính tổng tất cả square của các nút lá là số âm.
(define (sum-odd-squares tree)
(cond ((null? tree) 0)
((not (pair? tree))
(if (odd? tree) (square tree) 0))
(else (+ (sum-odd-squares (car tree))
(sum-odd-squares (cdr tree))))))
Khía cạnh khác, procedure này khác hoàn toàn so với một procedure trước đó, nó khởi tạo một list các số chẵn Fibonaccis Fib(k) , k là một số nhỏ hơn hoặc bằng n.
(define (even-fibs n)
(define (next k)
(if (> k n)
nil
(let ((f (fib k)))
(if (even? f)
(cons f (next (+ k 1)))
(next (+ k 1))))))
(next 0))Mặc dù chúng khác biệt về mặt cấu trúc, nhưng việc diễn tả abstract của hai thủ tục này tiết lộ một điểm chung tuyệt vời. Chương trình đầu tiên
- Liệt kê các nút là của tree
- Filter chúng, chon các nút số lẻ
- Tính bình phương của các nút số lẻ
- Tích lủy kết quả các nút (tính tổng) bắt đầu bằng 0.
Chương trình thứ hai
- Liệt kê các số integer từ 0 đến n.
- Tính số Fibonacci của mỗi integer.
- Filter chúng bằng cách chọn các số chẵn
- Tích lũy chúng (khởi tạo list mới) với list ban đầu trống
Một kỹ sữ sẽ tìm thấy cách tự nhiên đến khái niệm hóa hai tiến trình này trong các điều khoản của dòng chảy tín hiệu, mỗi phần sẽ thực thi một nhiệm vụ cụ thê, như chỉ ra ở hình 2.7. TRONG SUM-ODD-SQUARES, chúng ta bắt đầu với liệt kê các nút của tree (signal). Signal được truyền qua filter, để loại bỏ tất cả trừ các thành phần số lẻ. Kết quả sẽ truyền đến map, nó như bộ chuyển đổi, để tính square cho mỗi thành phần. Đầu ra của map sau đó dẫn đến accumulator, nó tính bao gồm tất cả các thành phần sử dụng +, bắt đầu với 0. Kế hoạc signal flowing ( cascade of stages) tương tự với even-fibs.
Hai procedure gói gọn tính toán trong hai cách khác nhau, liệt kê số lượng phần tử, tính toán các phần tử dựa trên map, filter và accumulation. Vì vậy chúng ta có thể tổ chức chương trình để làm cho cấu trúc signal-flow rõ ràng hơn trong các procedure chúng ta viết sau này, điều này tăng khả năng khai niệm hóa trong các code kết quả.
Sequence Operations – Các phép toán của danh sách liên kết.
Điểm mấu chốt để thực hiện các chương trình giống mô hình cấu trúc signal-flow là khởi tạo “signals” di chuyển từ tiếng trình này đến tiến trình khác. Nếu chúng ta trình bày signal như là các list, thì có thể sử dụng các toán tử của list để thực hiện tính toán ở mỗi quy trình.
Ví dụ, chúng ta có thể thực thi quy trình mapping của signal-flow sử dụng procedure map như sau:
(map square (list 1 2 3 4 5))
(1 4 9 16 25)
Filtering một danh sách và chọn các thành phần thỏa mãn một điều kiện nhất định để đạt được danh sách mới.
(define (filter predicate sequence)
(cond ((null? sequence) nil)
((predicate (car sequence))
(cons (car sequence)
(filter predicate (cdr sequence))))
(else (filter predicate (cdr sequence)))))
Ví dụ: (filter odd? (list 1 2 3 4 5))
(1 3 5)Accumulation có thể được thực thi bởi procedure sau:
(define (accumulate op initial sequence)
(if (null? sequence)
initial
(op (car sequence)
(accumulate op initial (cdr sequence)))))
Ví dụ
(accumulate + 0 (list 1 2 3 4 5))
15
(accumulate * 1 (list 1 2 3 4 5))
120
(accumulate cons nil (list 1 2 3 4 5))
(1 2 3 4 5)
All that remains to implement signal-flow diagrams is to enumerate the
sequence of elements to be processed. For even-fibs, we need to generate the sequence of integers in a given range, which we can do as
follows:
Tất cả những thứ còn lại để thực hiện một mô hình signal-flow là liệt kê các thành phần của danh sách cần được xử lý. Đối với even-fibs, chúng ta cần tạo ra danh sách các integers trong khoảng nhất định, có thể thực hiện như sau:
(define (enumerate-interval low high)
(if (> low high)
nil
(cons low (enumerate-interval (+ low 1) high))))
(enumerate-interval 2 7)
(2 3 4 5 6 7)Để liệt kê các nút lá của một tree, chúng ta sử dụng
(define (enumerate-tree tree)
(cond ((null? tree) nil)
((not (pair? tree)) (list tree))
(else (append (enumerate-tree (car tree))
(enumerate-tree (cdr tree))))))
(enumerate-tree (list 1 (list 2 (list 3 4)) 5))
(1 2 3 4 5)
Bây giờ, bạn cũng có thể công thức hóa sum-odd-squares and even-fibs như mô hình signal-flow. Đối với sum-odd-square, chúng ta liệt kê các nút của tree, filter chúng và lấy danh sách các nút là odd, bình phương từng phần tử, và sum chúng.
(define (sum-odd-squares tree)
(accumulate
0 (map square (filter odd? (enumerate-tree tree)))))Đối với even-fibs, chúng ta liệt kê các số integers from 0 đến n, tạo danh sách các số Fib tương ứng, filter chúng để lấy các số chẵn, và tạo một list mới.
(define (even-fibs n)
(accumulate
cons
nil
(filter even? (map fib (enumerate-interval 0 n)))))Sequences, được thực thi ở bài này như là các list, đóng vai trò như là một giao thức gốc (conventinal interface) cho phép chúng ta sử dụng để đóng gói các module khác nhau. Mỗi module làm một nhiệm vụ khác nhau mà khi signals đi vào module sẽ cho ra giá trị mà chúng ta mong muốn.
Bài tiếp theo: Nested Mappings
