elisp: Sets And Lists
5.7 Using Lists as Sets
=======================
A list can represent an unordered mathematical set—simply consider a
value an element of a set if it appears in the list, and ignore the
order of the list. To form the union of two sets, use ‘append’ (as long
as you don’t mind having duplicate elements). You can remove ‘equal’
duplicates using ‘delete-dups’. Other useful functions for sets include
‘memq’ and ‘delq’, and their ‘equal’ versions, ‘member’ and ‘delete’.
Common Lisp note: Common Lisp has functions ‘union’ (which avoids
duplicate elements) and ‘intersection’ for set operations.
Although standard GNU Emacs Lisp does not have them, the ‘cl-lib’
library provides versions. (cl)Lists as Sets.
-- Function: memq object list
This function tests to see whether OBJECT is a member of LIST. If
it is, ‘memq’ returns a list starting with the first occurrence of
OBJECT. Otherwise, it returns ‘nil’. The letter ‘q’ in ‘memq’
says that it uses ‘eq’ to compare OBJECT against the elements of
the list. For example:
(memq 'b '(a b c b a))
⇒ (b c b a)
(memq '(2) '((1) (2))) ; ‘(2)’ and ‘(2)’ are not ‘eq’.
⇒ nil
-- Function: delq object list
This function destructively removes all elements ‘eq’ to OBJECT
from LIST, and returns the resulting list. The letter ‘q’ in
‘delq’ says that it uses ‘eq’ to compare OBJECT against the
elements of the list, like ‘memq’ and ‘remq’.
Typically, when you invoke ‘delq’, you should use the return value
by assigning it to the variable which held the original list. The
reason for this is explained below.
The ‘delq’ function deletes elements from the front of the list by
simply advancing down the list, and returning a sublist that starts
after those elements. For example:
(delq 'a '(a b c)) ≡ (cdr '(a b c))
When an element to be deleted appears in the middle of the list,
removing it involves changing the CDRs (Setcdr).
(setq sample-list '(a b c (4)))
⇒ (a b c (4))
(delq 'a sample-list)
⇒ (b c (4))
sample-list
⇒ (a b c (4))
(delq 'c sample-list)
⇒ (a b (4))
sample-list
⇒ (a b (4))
Note that ‘(delq 'c sample-list)’ modifies ‘sample-list’ to splice
out the third element, but ‘(delq 'a sample-list)’ does not splice
anything—it just returns a shorter list. Don’t assume that a variable
which formerly held the argument LIST now has fewer elements, or that it
still holds the original list! Instead, save the result of ‘delq’ and
use that. Most often we store the result back into the variable that
held the original list:
(setq flowers (delq 'rose flowers))
In the following example, the ‘(4)’ that ‘delq’ attempts to match and
the ‘(4)’ in the ‘sample-list’ are not ‘eq’:
(delq '(4) sample-list)
⇒ (a c (4))
If you want to delete elements that are ‘equal’ to a given value, use
‘delete’ (see below).
-- Function: remq object list
This function returns a copy of LIST, with all elements removed
which are ‘eq’ to OBJECT. The letter ‘q’ in ‘remq’ says that it
uses ‘eq’ to compare OBJECT against the elements of ‘list’.
(setq sample-list '(a b c a b c))
⇒ (a b c a b c)
(remq 'a sample-list)
⇒ (b c b c)
sample-list
⇒ (a b c a b c)
-- Function: memql object list
The function ‘memql’ tests to see whether OBJECT is a member of
LIST, comparing members with OBJECT using ‘eql’, so floating-point
elements are compared by value. If OBJECT is a member, ‘memql’
returns a list starting with its first occurrence in LIST.
Otherwise, it returns ‘nil’.
Compare this with ‘memq’:
(memql 1.2 '(1.1 1.2 1.3)) ; ‘1.2’ and ‘1.2’ are ‘eql’.
⇒ (1.2 1.3)
(memq 1.2 '(1.1 1.2 1.3)) ; ‘1.2’ and ‘1.2’ are not ‘eq’.
⇒ nil
The following three functions are like ‘memq’, ‘delq’ and ‘remq’, but
use ‘equal’ rather than ‘eq’ to compare elements. Equality
Predicates.
-- Function: member object list
The function ‘member’ tests to see whether OBJECT is a member of
LIST, comparing members with OBJECT using ‘equal’. If OBJECT is a
member, ‘member’ returns a list starting with its first occurrence
in LIST. Otherwise, it returns ‘nil’.
Compare this with ‘memq’:
(member '(2) '((1) (2))) ; ‘(2)’ and ‘(2)’ are ‘equal’.
⇒ ((2))
(memq '(2) '((1) (2))) ; ‘(2)’ and ‘(2)’ are not ‘eq’.
⇒ nil
;; Two strings with the same contents are ‘equal’.
(member "foo" '("foo" "bar"))
⇒ ("foo" "bar")
-- Function: delete object sequence
This function removes all elements ‘equal’ to OBJECT from SEQUENCE,
and returns the resulting sequence.
If SEQUENCE is a list, ‘delete’ is to ‘delq’ as ‘member’ is to
‘memq’: it uses ‘equal’ to compare elements with OBJECT, like
‘member’; when it finds an element that matches, it cuts the
element out just as ‘delq’ would. As with ‘delq’, you should
typically use the return value by assigning it to the variable
which held the original list.
If ‘sequence’ is a vector or string, ‘delete’ returns a copy of
‘sequence’ with all elements ‘equal’ to ‘object’ removed.
For example:
(setq l '((2) (1) (2)))
(delete '(2) l)
⇒ ((1))
l
⇒ ((2) (1))
;; If you want to change ‘l’ reliably,
;; write ‘(setq l (delete '(2) l))’.
(setq l '((2) (1) (2)))
(delete '(1) l)
⇒ ((2) (2))
l
⇒ ((2) (2))
;; In this case, it makes no difference whether you set ‘l’,
;; but you should do so for the sake of the other case.
(delete '(2) [(2) (1) (2)])
⇒ [(1)]
-- Function: remove object sequence
This function is the non-destructive counterpart of ‘delete’. It
returns a copy of ‘sequence’, a list, vector, or string, with
elements ‘equal’ to ‘object’ removed. For example:
(remove '(2) '((2) (1) (2)))
⇒ ((1))
(remove '(2) [(2) (1) (2)])
⇒ [(1)]
Common Lisp note: The functions ‘member’, ‘delete’ and ‘remove’ in
GNU Emacs Lisp are derived from Maclisp, not Common Lisp. The
Common Lisp versions do not use ‘equal’ to compare elements.
-- Function: member-ignore-case object list
This function is like ‘member’, except that OBJECT should be a
string and that it ignores differences in letter-case and text
representation: upper-case and lower-case letters are treated as
equal, and unibyte strings are converted to multibyte prior to
comparison.
-- Function: delete-dups list
This function destructively removes all ‘equal’ duplicates from
LIST, stores the result in LIST and returns it. Of several ‘equal’
occurrences of an element in LIST, ‘delete-dups’ keeps the first
one.
See also the function ‘add-to-list’, in List Variables, for a
way to add an element to a list stored in a variable and used as a set.