In class we have discussed several ways to implement a set abstraction, including characteristic arrays, arrays-based or singly-linked lists (ordered or unordered), search trees or skip lists, and hash tables. So far, however, we have not paid much attention to how convenient (or inconvenient) these are to use in Python.
In mathematics, we don’t say C = A.union(B),
we say C = A ∪ B.
Python lists support a + operator, but since this
represents concatenation, with no regard to duplicates, it isn’t directly
useful for set addition. Given that an element e is in
A ∪ B if it is in A or in B, one
might propose using the Python “or” operator, |,
for union. In a similar vein, & might be used for
intersection, and - for difference.
And instead of A.add(e) and A.remove(e), we
might say A += e and A -= e.
We can achieve all of this by defining the appropriate
“double-underscore” methods, which Python calls when it
encounters built-in operators:
class Set:
def __init__(self, el = None):
self.contents = list()
if el != None:
for e in el:
self += e
def __iadd__(self, item): # (+=) add element to set
if item not in self.contents:
self.contents.append(item)
return self
def __isub__(self, item): # (-=) remove element from set
if item in self.contents:
self.contents.remove(item)
return self
def __or__(self, other): # (|) set union
rtn = Set(self.contents)
for e in other:
rtn += e
return rtn
def __and__(self, other): # (&) set intersection
rtn = Set()
for e in self:
if e in other:
rtn += e
return rtn
def __sub__(self, other): # (-) set difference
rtn = Set()
for e in self:
if e not in other:
rtn += e
return rtn
def __str__(self): # string to represent set
rtn = str(self.contents)
return "{" + rtn[1:len(rtn)-1] + "}"
Note that we’ve defined the constructor (initializer) to take an optional
Python list, which we use as initial contents of the set.
In the last method we’ve defined a convert-to-string routine that
will be called implicitly by the print statement.
Using the Set class above, we can interact with the
interpreter as follows:
>>> s1 = Set([1, 2, 3])
>>> print s1
{1, 2, 3}
>>> s2 = Set([3, 4, 5])
>>> print s2
{3, 4, 5}
>>> s1 += 4 # add element to set
>>> print s1
{1, 2, 3, 4}
>>> s2 -= 4 # remove element from set
>>> print s2
{3, 5}
>>> u = s1 | s2 # union
>>> print u
{1, 2, 3, 4, 5}
>>> i = s1 & s2 # intersection
>>> print i
{3}
>>> d = s1 - s2 # difference
>>> print d
{1, 2, 4}
>>>
But there’s more.
The built-in sequence types of Python (list, tuple, dictionary)
support iteration and membership tests using for
loops and the in operator. We can provide these for
Sets by defining the __iter__ method:
def __iter__(self):
i = 0
limit = len(self.contents)
while i < limit:
yield self.contents[i]
i += 1
This code illustrates a feature of Python that we have not seen before:
the yield statement. We can think of an iterator (a
method containing yield) as returning (yielding) a sequence of
objects over which a for loop iterates. Instead of returning
the sequence all at once however (before the loop starts running),
Python’s yield arranges to return them a bit at a time, as
required. If we type
s = Set([1, 2, 3])
t = 0
for e in s:
t += e
print t
the Python interpreter calls s.__iter__() when it first
encounters the for loop. The iterator yields one element of
s (say, 1), and the interpreter executes the first
iteration of the
loop. It then resumes execution of the iterator where it last left
off (right after the yield statement). The iterator yields
a value for the second iteration of the loop (say, 2), and so on. When
the iterator finally returns (or falls off the end of its code), the
for loop terminates. In our example, the print
will then print 6.
The in comparison test uses __iter__ as well.
The statement
if e in s:
...
is essentially equivalent to
t = False
for x in s:
if e == x:
t = True
break # exit loop
if t:
...
for some hidden temporary variable t.
In a nutshell, Python for loops exist for the purpose of
executing certain code (the body of the loop) for every element of a
sequence. Interestingly, there’s another way to implement this functionality:
def forAll(self, f):
for e in self:
f(e)
Given this definition, we can type
def add_to_t(e):
global t
t += e
...
t = 0
s.forAll(add_to_t)
print t
We could even write this as
t = 0
s.forAll(
add_to_t
)
print t
to emphasize its similarity to the for loop.
Finally, if we want to make sets convenient, it turns out to be very handy
to have a method, usually called map, that creates a new set
by applying a specified function to every element of some existing set:
def map(self, f):
rtn = Set()
for e in self:
rtn += f(e)
return rtn
Now given
def square(n):
return n*n
def add_square_to_q(e):
global q
q += square(e)
s = Set([1, 2, 3])
the following are all equivalent:
q = Set()
for e in s:
q += square(e)
print q
q = Set()
s.forAll(add_square_to_q)
print q
q = s.map(square)
print q
They all print {1, 4, 9}.
The examples above flesh out convenience routines for sets based on Python lists. You can find the code all together in one file HERE. Your task in this brief (1-week) project is to flesh out similar routines for sets based on sorted, singly-linked lists. You’ll probably want to build on your code from Lab 6.
Please read the grading
standards web page carefully and follow its instructions.
In particular, note that you will need to create a README.txt
or README.pdf file, and you will need to turn your code in
using Blackboard.
For extra credit (counted at the end of the semester; may raise your final grade), you might consider the following possibilities.
__iadd__ (+=) method defined above
allows you to add a single element to a set. Modify this method so
that its parameter may also be a Python list or another
Set object. You’ll need to use the type
function to tell which kind of parameter you’ve been given.
Note that A += B is very different from
C = A | B. The former adds the
elements of
B to A. The latter creates a
new set
containing the elements of both A and B; it
does not modify either A or B.
