Representation: Repr, Str
Q1: WWPD: Repr-esentation
class A: def __init__(self, x): self.x = x def __repr__(self): return self.x def __str__(self): return self.x * 2 class B: def __init__(self): print('boo!') self.a =  def add_a(self, a): self.a.append(a) def __repr__(self): print(len(self.a)) ret = '' for a in self.a: ret += str(a) return ret
Given the above class definitions, what will the following lines output?
>>> b = B()
>>> b.add_a(A('a')) >>> b.add_a(A('b')) >>> b
There are many different implementations of sequences in Python. Today, we'll explore the linked list implementation.
A linked list is either an empty linked list, or a Link object containing a
first value and the
rest of the linked list.
To check if a linked list is an empty linked list, compare it against the class
if link is Link.empty: print('This linked list is empty!') else: print('This linked list is not empty!')
You can find an implementation of the
Link class below:
class Link: """A linked list.""" empty = () def __init__(self, first, rest=empty): assert rest is Link.empty or isinstance(rest, Link) self.first = first self.rest = rest def __repr__(self): if self.rest: rest_repr = ', ' + repr(self.rest) else: rest_repr = '' return 'Link(' + repr(self.first) + rest_repr + ')' def __str__(self): string = '<' while self.rest is not Link.empty: string += str(self.first) + ' ' self = self.rest return string + str(self.first) + '>'
Q2: The Hy-rules of Linked Lists
In this question, we are given the following Linked List:
ganondorf = Link('zelda', Link('link', Link('sheik', Link.empty)))
What expression would give us the value
'sheik' from this Linked List?
What is the value of
What would be the value of
What expression would mutate this linked list to
<zelda ganondorf sheik>?
Q3: Sum Nums
Write a function that takes in a linked list and returns the sum of all
its elements. You may assume all elements in
s are integers. Try to implement this recursively!
Q4: Multiply Links
Write a function that takes in a Python list of linked lists and multiplies them element-wise. It should return a new linked list.
If not all of the
Link objects are of equal length, return a
linked list whose length is that of the shortest linked list given. You
may assume the
Link objects are shallow linked lists, and that
lst_of_lnks contains at least one linked list.
Q5: Flip Two
Write a recursive function
flip_two that takes as input a
s and mutates
s so that every pair
We define a tree to be a recursive data abstraction that has a label (the value stored in the root of the tree) and branches (a list of trees directly underneath the root). Previously, we implemented the tree abstraction using Python lists. Let's look at another implementation using objects instead:
class Tree: def __init__(self, label, branches=): for b in branches: assert isinstance(b, Tree) self.label = label self.branches = branches def is_leaf(self): return not self.branches
With this implementation, we can mutate a tree using attribute assignment, which wasn't possible in the previous implementation using lists. That's why we sometimes call these objects "mutable trees."
>>> t = Tree(3, [Tree(4), Tree(5)]) >>> t.label = 5 >>> t.label 5
Q6: Make Even
Define a function
make_even which takes in a tree
t whose values are integers, and mutates the tree such that all the
odd integers are increased by 1 and all the even integers remain the same.
Write a function
leaves that returns a list of all the label values of the
leaf nodes of a
Q8: Find Paths
Hint: This question is similar to
find_path on Discussion 05.
Define the procedure
find_paths that, given a Tree
t and an
entry, returns a list of lists containing the nodes along each path from the root of
entry. You may return the paths in any order.
For instance, for the following tree
find_paths should behave as specified in the function doctests.