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
Set
s 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 tthe 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 tWe could even write this as
t = 0 s.forAll( add_to_t ) print tto 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 rtnNow 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 qThey 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
.