Mapping là gì:
Ví dụ: Ta có một sequence ban đầu ( 1 2 3) giờ ta muốn tính bình phương trên các phần tử để đạt được một sequence mới. Ta sẽ sử dụng mapping để thực hiện điều này.
(map <square> start-list) ==> (map square (1 2 3) ==> Result: ( 1 4 9)
Mapping lồng nhau
Chúng ta có thể mở rộng mô hình sequence đến nhiều cách tính toán với các mô hình phổ biến sử dụng các vòng lặp lồng nhau. Xem xét vấn đều sau: Cho một số integer dương n , tìm tất cả các cặp integer dương i và j khác nhau thỏa mãn điều kiện, 1 ≤ j < i ≤ n, và i + j là số nguyên tố. Ví dụ, nếu n là 6 thì các cặp tương ứng của nó là ‘:
Cách để tổ chức kết quả này là tạo ra một sequence của tất cả các cặp số integer dương nhỏ hơn hoặc bằng, filter để chọn các cặp có tổng là số nguyên tố, sau đó với mỗi cặp (i, j) nó pass việc kiểm tra, sau đó tạo ra triple (i, j,i + j).
Đây là một cách để tạo ra sequence của các pair. Với mỗi số integer i <= n, liệt kê các số j < i, và tạo ra các cặp (i, j). Trong điều khoản của các toán tử sequence, chúng ta map cùng với sequence (enumerate-interval 1 n). Với mỗi i trong sequence, chúng ta cũng map cùng với sequence (enumerate-interval 1 (- i 1)). Với mỗi j, chúng ta tạo cặp (list i j). Điều này cho chúng ta một sequence của các pair với mỗi i và j.
(accumulate
append nil (map (lambda (i)
(map (lambda (j) (list i j))
(enumerate-interval 1 (- i 1))))
(enumerate-interval 1 n)))Tập hợp của mapping và accumulating với append quá phổ biến trong các chương trình sắp xếp , chúng ta sẽ tách biệt nó như là một procedure.
(define (flatmap proc seq)
(accumulate append nil (map proc seq)))Dự đoán sequence của các pair để tìm các thành phần với sum là số nguyên tố. Đối số của nó là một pair và nó phải truy xuất các số integer từ pair. Việc dự đoán áp dụng đến mỗi cặp trong sequence.
(define (prime-sum? pair)
(prime? (+ (car pair) (cadr pair))))Cuối cùng, tạo ra một sequence kết quả bằng việc mapping trên các cặp đã được chọn sử dụng procedure sau, nó khởi tạo một tripple bao gồm hai thành phần của pair và sum của chúng.
(define (make-pair-sum pair)
(list (car pair) (cadr pair) (+ (car pair) (cadr pair))))Bao gồm tất cả các bước trên để đạt được một procedure hoàn chỉnh
(define (prime-sum-pairs n)
(map make-pair-sum
(filter prime-sum? (flatmap
(lambda (i)
(map (lambda (j) (list i j))
(enumerate-interval 1 (- i 1))))
(enumerate-interval 1 n)))))Kỹ thuật mapping lồng nhau cũng hữu dụng cho các sequence hơn là enumerate-intervals. Chúng ta muốn tạo ra tất cả các hoán vị của một danh sách S, tất cả các cách để sắp xếp các item trong S. Ví dụ, hoán đỏi các vị trị của danh sach {1, 2, 3} là {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, và {3, 2, 1}. Đây là một cách để tạo ra các hoán vị của S: với mỗi item x trong S, đệ quy tạo ra sequence của các hoán vị S-x, và thêm x đến trước mỗi hoán vị. Kết quả đạt được là, với mỗi x trong S, sequence của các hoán vị của S bắt đầu với x. Bao gồm các sequence này với tất cả các x cho tất cả các hoán vị của S.
(define (permutations s)
(if (null? s) ; empty set?
(list nil) ; sequence containing empty set
(flatmap (lambda (x)
(map (lambda (p) (cons x p))
(permutations (remove x s))))
s)))Chú ý rằng chiến lược này giúp giảm vấn đề của việc tạo ra các hoán vị của S đến vấn đề của việc trạo ra các hoán vị của các set với số lượng thành phần ít hơn S. Ở trường hợp cuối, chúng ta sẽ làm giảm phần tử đến danh sách trống. Chúng ta có thể sử dụng (list nil) để tạo list trống, nó là một sequence không có item. Procedure remove được sử dụng trong procedure permutations trả về tất cả các phần tử của S trừ phần tử x. Có thể trình bày trong một filter đơn giản sau.
(define (remove item sequence)
(filter (lambda (x) (not (= x item)))
sequence))Bài viết tiếp theo: Example: A Picture Language
