LISP - Bộ

Lisp chung không cung cấp kiểu dữ liệu tập hợp. Tuy nhiên, nó cung cấp một số chức năng cho phép thực hiện các hoạt động tập hợp trên một danh sách.

Bạn có thể thêm, xóa và tìm kiếm các mục trong danh sách, dựa trên các tiêu chí khác nhau. Bạn cũng có thể thực hiện các hoạt động tập hợp khác nhau như: liên hợp, giao điểm và đặt chênh lệch.

Bộ triển khai trong LISP

Các tập hợp, giống như danh sách thường được triển khai theo các ô khuyết điểm. Tuy nhiên, vì lý do này, các hoạt động tập hợp ngày càng kém hiệu quả hơn khi tập hợp càng lớn.

Các adjoinchức năng cho phép bạn thiết lập một tập hợp. Nó lấy một mục và một danh sách đại diện cho một tập hợp và trả về một danh sách đại diện cho tập hợp chứa mục và tất cả các mục trong tập hợp ban đầu.

Các adjoinđầu tiên hàm tìm kiếm mục trong danh sách đã cho, nếu tìm thấy nó, thì nó sẽ trả về danh sách ban đầu; nếu không, nó tạo ra một ô khuyết điểm mới vớicar như mặt hàng và cdr trỏ đến danh sách ban đầu và trả về danh sách mới này.

Các adjoin chức năng cũng mất :key và :testđối số từ khóa. Các đối số này được sử dụng để kiểm tra xem mục có trong danh sách ban đầu hay không.

Vì, hàm adjoin không sửa đổi danh sách ban đầu, để thực hiện thay đổi trong chính danh sách, bạn phải gán giá trị được trả về bởi hàm adjoin vào danh sách ban đầu hoặc bạn có thể sử dụng macro pushnew để thêm một mục vào tập hợp.

Thí dụ

Tạo một tệp mã nguồn mới có tên main.lisp và nhập mã sau vào đó.

; creating myset as an empty list
(defparameter *myset* ())
(adjoin 1 *myset*)
(adjoin 2 *myset*)

; adjoin did not change the original set
;so it remains same
(write *myset*)
(terpri)
(setf *myset* (adjoin 1 *myset*))
(setf *myset* (adjoin 2 *myset*))

;now the original set is changed
(write *myset*)
(terpri)

;adding an existing value
(pushnew 2 *myset*)

;no duplicate allowed
(write *myset*)
(terpri)

;pushing a new value
(pushnew 3 *myset*)
(write *myset*)
(terpri)

Khi bạn thực thi mã, nó trả về kết quả sau:

NIL
(2 1)
(2 1)
(3 2 1)

Kiểm tra tư cách thành viên

Nhóm chức năng thành viên cho phép bạn kiểm tra xem một phần tử có phải là thành viên của một tập hợp hay không.

Sau đây là cú pháp của các hàm này:

member item list &key :test :test-not :key 
member-if predicate list &key :key 
member-if-not predicate list &key :key

Các hàm này tìm kiếm trong danh sách cho một mục nhất định đáp ứng thử nghiệm. Nếu không tìm thấy mục nào như vậy, thì các hàm trả vềnil. Nếu không, phần đuôi của danh sách có phần tử là phần tử đầu tiên được trả về.

Việc tìm kiếm chỉ được thực hiện ở cấp cao nhất.

Các hàm này có thể được sử dụng làm vị từ.

Thí dụ

Tạo một tệp mã nguồn mới có tên main.lisp và nhập mã sau vào đó.

(write (member 'zara '(ayan abdul zara riyan nuha)))
(terpri)
(write (member-if #'evenp '(3 7 2 5/3 'a)))
(terpri)
(write (member-if-not #'numberp '(3 7 2 5/3 'a 'b 'c)))

Khi bạn thực thi mã, nó trả về kết quả sau:

(ZARA RIYAN NUHA)
(2 5/3 'A)
('A 'B 'C)

Đặt Liên minh

Nhóm hàm liên hợp cho phép bạn thực hiện liên hợp thiết lập trên hai danh sách được cung cấp làm đối số cho các hàm này trên cơ sở kiểm tra.

Sau đây là cú pháp của các hàm này:

union list1 list2 &key :test :test-not :key 
nunion list1 list2 &key :test :test-not :key

Các unionhàm nhận hai danh sách và trả về một danh sách mới chứa tất cả các phần tử có trong một trong hai danh sách. Nếu có sự trùng lặp, thì chỉ một bản sao của thành viên được giữ lại trong danh sách trả về.

Các nunion hàm thực hiện cùng một hoạt động nhưng có thể phá hủy danh sách đối số.

Thí dụ

Tạo một tệp mã nguồn mới có tên main.lisp và nhập mã sau vào đó.

(setq set1 (union '(a b c) '(c d e)))
(setq set2 (union '(#(a b) #(5 6 7) #(f h)) 
   '(#(5 6 7) #(a b) #(g h)) :test-not #'mismatch)
)
       
(setq set3 (union '(#(a b) #(5 6 7) #(f h)) 
   '(#(5 6 7) #(a b) #(g h)))
)
(write set1)
(terpri)
(write set2)
(terpri)
(write set3)

Khi bạn thực thi mã, nó trả về kết quả sau:

(A B C D E)
(#(F H) #(5 6 7) #(A B) #(G H))
(#(A B) #(5 6 7) #(F H) #(5 6 7) #(A B) #(G H))

Xin lưu ý

Chức năng liên hiệp không hoạt động như mong đợi nếu không có :test-not #'mismatchđối số cho danh sách ba vectơ. Điều này là do, danh sách được tạo bằng các ô khuyết điểm và mặc dù các giá trị trông giống nhau đối với chúng ta,cdrmột phần của các ô không khớp, vì vậy chúng không hoàn toàn giống với trình thông dịch / trình biên dịch LISP. Đây là lý do; thực hiện các tập hợp lớn không được khuyên sử dụng danh sách. Nó hoạt động tốt cho các bộ nhỏ.

Đặt giao lộ

Nhóm giao nhau của các hàm cho phép bạn thực hiện giao nhau trên hai danh sách được cung cấp làm đối số cho các hàm này trên cơ sở kiểm tra.

Sau đây là cú pháp của các hàm này:

intersection list1 list2 &key :test :test-not :key 
nintersection list1 list2 &key :test :test-not :key

Các hàm này nhận hai danh sách và trả về một danh sách mới chứa tất cả các phần tử có trong cả hai danh sách đối số. Nếu một trong hai danh sách có các mục nhập trùng lặp, các mục nhập thừa có thể xuất hiện hoặc không xuất hiện trong kết quả.

Thí dụ

Tạo một tệp mã nguồn mới có tên main.lisp và nhập mã sau vào đó.

(setq set1 (intersection '(a b c) '(c d e)))
(setq set2 (intersection '(#(a b) #(5 6 7) #(f h)) 
   '(#(5 6 7) #(a b) #(g h)) :test-not #'mismatch)
)
       
(setq set3 (intersection '(#(a b) #(5 6 7) #(f h)) 
   '(#(5 6 7) #(a b) #(g h)))
)
(write set1)
(terpri)
(write set2)
(terpri)
(write set3)

Khi bạn thực thi mã, nó trả về kết quả sau:

(C)
(#(A B) #(5 6 7))
NIL

Hàm giao nhau là phiên bản hủy của giao điểm, tức là, nó có thể hủy danh sách ban đầu.

Đặt sự khác biệt

Nhóm chức năng khác biệt tập hợp cho phép bạn thực hiện chênh lệch tập hợp trên hai danh sách được cung cấp làm đối số cho các hàm này trên cơ sở kiểm tra.

Sau đây là cú pháp của các hàm này:

set-difference list1 list2 &key :test :test-not :key 
nset-difference list1 list2 &key :test :test-not :key

Hàm set-difference trả về danh sách các phần tử của danh sách đầu tiên không xuất hiện trong danh sách thứ hai.

Thí dụ

Tạo một tệp mã nguồn mới có tên main.lisp và nhập mã sau vào đó.

(setq set1 (set-difference '(a b c) '(c d e)))
(setq set2 (set-difference '(#(a b) #(5 6 7) #(f h)) 
   '(#(5 6 7) #(a b) #(g h)) :test-not #'mismatch)
)
(setq set3 (set-difference '(#(a b) #(5 6 7) #(f h)) 
   '(#(5 6 7) #(a b) #(g h)))
)
(write set1)
(terpri)
(write set2)
(terpri)
(write set3)

Khi bạn thực thi mã, nó trả về kết quả sau:

(A B)
(#(F H))
(#(A B) #(5 6 7) #(F H))