Time: Tue 10/12/17 2 pm
Similar to the elementary data abstraction, just that we can change values in the encapsulation now somehow.
What is nonlocal? And why is it useful in this case? Can we just bind some variable in the parent frame to some new values without using this keyword? Do we need to have something in a nonlocal frame with the name beforehand?
Here's something really bad to do as an example:
def make_bike():
# The color of the bike
color = "red"
def get_color():
return color
def change_color(new_color):
# Change the color of the bike
color = new_color
# However now you thought you forgot to use nonlocal
# But note that it doesn't hoist
nonlocal color # Invalid syntax
# Python will just give up with your code :(
# ... and literally halt here
return [get_color, change_color]
[get_color, change_color] = make_bike() # Make a bike
change_color("blue") # Make it blue, don't like it being redAnd a slightly better example (in which there is no syntax error, but logically incorrect):
def make_factory():
# The color of the bike by default
factory_color = "green"
def make_bike():
# Use the factory color as default
color = factory_color
def get_color():
return color
def change_color(new_color):
# Someone hacked into the script and changed the following lines
nonlocal factory_color
factory_color = new_color
return [get_color, change_color]
return make_bike
make_bike = make_factory()
# Make a new bike
[get_0_color, change_0_color] = make_bike()
# Inspect its color
get_0_color() # green
# And now we want to repaint the bike
change_0_color("blue")
# And when we try to inspect the bike again...
get_0_color() # green
# Uhm it is still green :/
# Make another bike
[get_1_color, change_1_color] = make_bike()
# Try to inspect its color... which should be green
get_1_color() # blue
# Oh well, the factory settings are modified... uh ohCan we still implement something with a same interface that does exactly the same without nonlocal, using list, dict etc.?
Primitively, they are just syntactical sugars for data abstraction. What are methods, bound methods and static methods?
A quick example of each:
class balloon():
@staticmethod
def describe():
print("Balloon!")
def grow(self):
print("The balloon grew larger...")
b = balloon()
balloon # <class '__main__.balloon'>
b # <__main__.balloon object at ...>
# Static method
balloon.describe # <function balloon.describe at ...>
balloon.describe() # Balloon!
b.describe # <function balloon.describe at ...>
b.describe() # Balloon!
# Unbound method
balloon.grow # <function balloon.grow at ...>
balloon.grow(b) # The balloon grew larger...
# Bound method
b.grow # <bound method balloon.grow of <__main__.balloon object at ...>>
b.grow() # The balloon grew larger...Class variables and instance variables are different. Class variables are shared between instances; however, instance variables are just different from instance to instance.
class sandbag():
weight = 10
# Someone goes to buy a sandbag
s = sandbag()
# He weighs the sandbag...
s.weight # 10
# And finds that it is of 10 kilos
# And another person comes into the story and does something terrible
sandbag.weight = 5
# The next day, whoever that bought the sandbag tries to re-weigh it
s.weight # 5
# And somehow... It became lighter :(How do you make custom constructors for a class?
There are some goodies and complications that come with objects too. Multiple inheritance is a beast--check out the diamond problem--and it can bring ambiguities in programming. There are ways to probe into the method resolution order.
What's super, and why do we use it?
Fill in the blanks of the implementation of sixty_ones below, a function that takes a Link instance representing a sequence of integers and returns the number of times that 6 and 1 appear consecutively.
def sixty_ones(s):
"""
Return the number of times that 1 directly follows 6 in linked list s.
>>> once = Link(4, Link(6, Link(1, Link(6, Link(0, Link(1))))))
>>> twice = Link(1, Link(6, Link(1, once)))
>>> thrice = Link(6, twice)
>>> apply_to_all(sixty_ones, [Link.empty, once, twice, thrice])
[0, 1, 2, 3]
"""
if :
return 0
elif :
return 1 +
else:
return Fill in the blanks of the implementation of no_eleven below, a function that returns a list of all distinct length-n lists of ones and sixes in which 1 and 1 do not appear consecutively.
def no_eleven(n):
"""
Return a list of lists of 1’s and 6’s that do not contain 1 after 1.
>>> no_eleven(2)
[[6, 6], [6, 1], [1, 6]]
>>> no_eleven(3)
[[6, 6, 6], [6, 6, 1], [6, 1, 6], [1, 6, 6], [1, 6, 1]]
>>> no_eleven(4)[:4] # first half
[[6, 6, 6, 6], [6, 6, 6, 1], [6, 6, 1, 6], [6, 1, 6, 6]]
>>> no_eleven(4)[4:] # second half
[[6, 1, 6, 1], [1, 6, 6, 6], [1, 6, 6, 1], [1, 6, 1, 6]]
"""
if n == 0:
return
elif n == 1:
return
else:
a, b = no_eleven(), no_eleven()
return [ for s in a] + [ for s in b]This question uses the following tree data abstraction.
def tree(entry, children=[]):
return [entry, children]
def entry(tree):
return tree[0]
def children(tree):
return tree[1]Define the function track_lineage that takes in a tree of strings family_tree and a string name. Assume that there is a unique node with entry name. track_lineage returns a list with the entries of the parent and grandparent of that node. If the node with entry name does not have a parent or grandparent, return None for that element in the list. See the doctests for details. Do not violate abstraction barriers. You may only use the lines provided. You may not need to fill all the lines.
def track_lineage(family_tree, name):
"""
Return the entries of the parent and grandparent of the node with entry name in family_tree.
>>> t = tree('Tytos', [
... tree('Tywin', [
... tree('Cersei'), tree('Jaime'), tree('Tyrion')
... ]),
... tree('Kevan', [
... tree('Lancel'), tree('Martyn'), tree('Willem')
... ])])
>>> track_lineage(t, 'Tywin')
['Tytos', None]
>>> track_lineage(t, 'Tytos')
[None, None]
"""
def tracker(t, p, gp):
if
for c in children(t):
return tracker(, , )Assuming that track_lineage works correctly, define the function are cousins that takes in a tree of strings family_tree and two strings name1 and name2 and returns True if the node with entry name1 and the node with entry name2 are cousins in family_tree. Assume that there are unique nodes with entries name1 and name2 in family_tree. See the doctests for details. Two nodes are cousins if they have the same grandparent but different parents.
You may only use the lines provided. You may not need to fill all the lines.
def are_cousins(family_tree, name1, name2):
"""Return True if a node with entry name1 is a cousin of a node with entry name2 in family_tree.
>>> are_cousins(t, ‘Kevan’, ‘Tytos’) # same tree as before False
>>> are_cousins(t, ‘Cersei’, ‘Lancel’)
True
>>> are_cousins(t, ‘Jaime’, ‘Lancel’)
True
>>> are_cousins(t, ‘Jaime’, ‘Tyrion’)
False
"""
A GrootTree g is a binary tree that has an attribute parent. Its parent is the GrootTree in which g is a branch. If a GrootTree instance is not a branch of any other GrootTree instance, then its parent is BinaryTree.empty.
BinaryTree.empty should not have a parent attribute. Assume that every GrootTree instance is a branch of at most one other GrootTree instance and not a branch of any other kind of tree.
Fill in the blanks below so that the parent attribute is set correctly. You may not need to use all of the lines. Indentation is allowed. You should not include any assert statements. Using your solution, the doctests for fib_groot should pass.
class GrootTree(BinaryTree):
"""A binary tree with a parent."""
def __init__(self, entry, left=BinaryTree.empty, right=BinaryTree.empty):
BinaryTree.__init__(self, entry, left, right)
def fib_groot(n):
"""
Return a Fibonacci GrootTree.
>>> t = fib_groot(3)
>>> t.entry
2
>>> t.parent.is_empty
True
>>> t.left.parent.entry
2
>>> t.right.left.parent.right.parent.entry
1
"""
if n == 0 or n == 1:
return GrootTree(n)
else:
left, right = fib_groot(n - 2), fib_groot(n - 1)
return GrootTree(left.entry + right.entry, left, right)Fill in the blanks of the implementation of paths, a function that takes two arguments: a GrootTree instance g and a list s. It returns the number of paths through g whose entries are the elements of s. A path through a GrootTree can extend either to a branch or its parent.
You may assume that the GrootTree class is implemented correctly and that the list s is non-empty.
There are two paths for [2, 1, 2, 1, 0], one path for [2, 1, 0, 1, 0] in the tree below:
2 +-------+ 1 1 +---+ 0 1
def paths(g, s):
"""
The number of paths through g with entries s.
>>> t = fib_groot(3)
>>> paths(t, [1])
0
>>> paths(t, [2])
1
>>> paths(t, [2, 1, 2, 1, 0])
2
>>> paths(t, [2, 1, 0, 1, 0])
1
>>> paths(t, [2, 1, 2, 1, 2, 1])
8
"""
if g is BinaryTree.empty :
return 0
elif :
return 1
else:
xs = []
return sum([ for x in xs])