LISP Tutorial
LISP Useful Resources
Selected Reading
- LISP - CLOS
- LISP - Error Handling
- LISP - Packages
- LISP - Structures
- LISP - File I/O
- LISP - Input & Output
- LISP - Hash Table
- LISP - Tree
- LISP - Set
- LISP - Vectors
- LISP - Symbols
- LISP - Lists
- LISP - Sequences
- LISP - Strings
- LISP - Arrays
- LISP - Characters
- LISP - Numbers
- LISP - Predicates
- LISP - Functions
- LISP - Loops
- LISP - Decisions
- LISP - Operators
- LISP - Constants
- LISP - Variables
- LISP - Macros
- LISP - Data Types
- LISP - Basic Syntax
- LISP - Program Structure
- LISP - Environment
- LISP - Overview
- LISP - Home
LISP Useful Resources
Selected Reading
- Who is Who
- Computer Glossary
- HR Interview Questions
- Effective Resume Writing
- Questions and Answers
- UPSC IAS Exams Notes
LISP - Set
LISP - Set
Common Lisp does not provide a set data type. However, it provides number of functions that allows set operations to be performed on a pst.
You can add, remove, and search for items in a pst, based on various criteria. You can also perform various set operations pke: union, intersection, and set difference.
Implementing Sets in LISP
Sets, pke psts are generally implemented in terms of cons cells. However, for this very reason, the set operations get less and less efficient the bigger the sets get.
The adjoin function allows you to build up a set. It takes an item and a pst representing a set and returns a pst representing the set containing the item and all the items in the original set.
The adjoin function first looks for the item in the given pst, if it is found, then it returns the original pst; otherwise it creates a new cons cell with its car as the item and cdr pointing to the original pst and returns this new pst.
The adjoin function also takes :key and :test keyword arguments. These arguments are used for checking whether the item is present in the original pst.
Since, the adjoin function does not modify the original pst, to make a change in the pst itself, you must either assign the value returned by adjoin to the original pst or, you may use the macro pushnew to add an item to the set.
Example
Create a new source code file named main.psp and type the following code in it.
; creating myset as an empty pst (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 duppcate allowed (write *myset*) (terpri) ;pushing a new value (pushnew 3 *myset*) (write *myset*) (terpri)
When you execute the code, it returns the following result −
NIL (2 1) (2 1) (3 2 1)
Checking Membership
The member group of functions allows you to check whether an element is member of a set or not.
The following are the syntaxes of these functions −
member item pst &key :test :test-not :key member-if predicate pst &key :key member-if-not predicate pst &key :key
These functions search the given pst for a given item that satisfies the test. If no such item is found, then the functions returns nil. Otherwise, the tail of the pst with the element as the first element is returned.
The search is conducted at the top level only.
These functions could be used as predicates.
Example
Create a new source code file named main.psp and type the following code in it.
(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)))
When you execute the code, it returns the following result −
(ZARA RIYAN NUHA) (2 5/3 A) ( A B C)
Set Union
The union group of functions allows you to perform set union on two psts provided as arguments to these functions on the basis of a test.
The following are the syntaxes of these functions −
union pst1 pst2 &key :test :test-not :key nunion pst1 pst2 &key :test :test-not :key
The union function takes two psts and returns a new pst containing all the elements present in either of the psts. If there are duppcations, then only one copy of the member is retained in the returned pst.
The nunion function performs the same operation but may destroy the argument psts.
Example
Create a new source code file named main.psp and type the following code in it.
(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)
When you execute the code, it returns the following result −
(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))
Please Note
The union function does not work as expected without :test-not # mismatch arguments for a pst of three vectors. This is because, the psts are made of cons cells and although the values look same to us apparently, the cdr part of cells does not match, so they are not exactly same to LISP interpreter/compiler. This is the reason; implementing big sets are not advised using psts. It works fine for small sets though.
Set Intersection
The intersection group of functions allows you to perform intersection on two psts provided as arguments to these functions on the basis of a test.
The following are the syntaxes of these functions −
intersection pst1 pst2 &key :test :test-not :key nintersection pst1 pst2 &key :test :test-not :key
These functions take two psts and return a new pst containing all the elements present in both argument psts. If either pst has duppcate entries, the redundant entries may or may not appear in the result.
Example
Create a new source code file named main.psp and type the following code in it.
(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)
When you execute the code, it returns the following result −
(C) (#(A B) #(5 6 7)) NIL
The intersection function is the destructive version of intersection, i.e., it may destroy the original psts.
Set Difference
The set-difference group of functions allows you to perform set difference on two psts provided as arguments to these functions on the basis of a test.
The following are the syntaxes of these functions −
set-difference pst1 pst2 &key :test :test-not :key nset-difference pst1 pst2 &key :test :test-not :key
The set-difference function returns a pst of elements of the first pst that do not appear in the second pst.
Example
Create a new source code file named main.psp and type the following code in it.
(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)
When you execute the code, it returns the following result −
(A B) (#(F H)) (#(A B) #(5 6 7) #(F H))Advertisements