evaluate to equal values
Identical objects are always equal values
All other values are true values.
Effect
>>> bool(‘0’) True
>>> bool([]) False
>>> bool([[]]) True
>>> bool({}) False
>>> bool(())
False
>>> bool(lambda x: 0) True
>>> 2 in digits
True
>>> 1828 not in digits
True Slicing creates a new object
Identity:
[1, 8]
>>> digits[1:] [8, 2, 8]
iter(iterable): Return an iterator over the elements of an iterable value
next(iterator):
Return the next element
>>> s = [3, 4, 5] >>> t = iter(s) >>> next(t)
3
>>> next(t) 4
>>> d = {‘one’: 1, ‘two’: 2, ‘three’: 3}
•No nonlocal statement •”x” is not bound locally
•No nonlocal statement •”x” is bound locally •nonlocal x
•”x” is bound in a
non-local frame •nonlocal x
•”x” is not bound in a non-local frame
•nonlocal x
•”x” is bound in a
non-local frame
•”x” also bound locally
Create a new binding from name “x” to number 2 in the first frame of the current environment
Re-bind name “x” to object 2 in the first frame of the current environment
Re-bind “x” to 2 in the first non-local frame of the current environment in which “x” is bound
SyntaxError: no binding for nonlocal ‘x’ found SyntaxError: name ‘x’ is parameter and nonlocal
>>> k = iter(d) >>> next(k) ‘one’
>>> next(k) ‘two’
>>> v = iter(d.values()) >>> next(v)
1
>>> next(v)
2
Status
x = 2
A generator function is a function that yields values instead of returning them.
>>> def plus_minus(x):
… yield x
… yield -x
>>> t = plus_minus(3) >>> next(t)
3
>>> next(t)
-3
def a_then_b(a, b): yield from a yield from b
>>> list(a_then_b([3, 4], [5, 6])) [3, 4, 5, 6]
CS 61A Midterm 2 Study Guide — Page 2
Recursive description:Root or Root Node
Path
Nodes Python object system:
Idea: All bank accounts have a balance and an account holder;
•A tree has a root label and a list of branches
•Each branch is a tree
•A tree with zero branches
is called a leaf Relative description: •Each location is a node •Each node has a label •One node can be the
parent/child of another
def tree(label, branches=[]): for branch in branches:
Labels the Account class should add those attributes to each of its instances
Root label Branch
1
1
Verifies the tree definition
Creates a list from a sequence of branches
3
0
Leaf
1
1
An account instance
2
0
A new instance is created by calling a class
>>> a = Account(‘Jim’) >>> a.holder
‘Jim’
>>> a.balance
0
def fib_tree(n):
if n == 0 or n == 1:
return Tree(n) else:
left = fib_Tree(n-2)
right = fib_Tree(n-1)
fib_n = left.label+right.label return Tree(fib_n,[left, right])
1
When a class is called:
1.A new instance of that class is created:
2.The __init__ method of the class is called with the new object as its first
argument (named self), along with any additional arguments provided in the call expression.
class Account:
assert is_tree(branch) return [label] + list(branches)
def __init__(self, account_holder): self.balance = 0
self.holder = account_holder def deposit(self, amount):
self.balance = self.balance + amount
return self.balance bound to an instance of def withdraw(self, amount):
def label(tree): return tree[0]
__init__ is called a constructor
def branches(tree):
return tree[1:] Verifies that tree is
bound to a list
def is_tree(tree):
if type(tree) != list or len(tree) < 1: 1
return False
for branch in branches(tree):
if not is_tree(branch): return False
return True def is_leaf(tree):
3
self should always be
return not branches(tree) def fib_tree(n):
1 ... tree(1)])])
[3, [1], [2, [1], [1]]]
1 >>> tree(3, [tree(1),
>>> type(Account.deposit)
>>> type(a.deposit)
>>> Account.deposit(a, 5) 10
>>> a.deposit(2)
12
Dot expression
2
the Account class or a subclass of Account
if amount > self.balance: return ‘Insufficient funds’
self.balance = self.balance – amount return self.balance
… tree(2, [tree(1),
Function call: all arguments within parentheses
Method invocation: One object before the dot and other arguments within parentheses
The can
The must be a
Evaluates to the value of the attribute looked up by in the object that is the value of the .
To evaluate a dot expression:
1. Evaluate the to the left of the dot, which yields
the object of the dot expression
2. is matched against the instance attributes of that object;
if an attribute with that name exists, its value is returned 3. If not, is looked up in the class, which yields a class
attribute value
4. That value is returned unless it is a function, in which case a
bound method is returned instead
Assignment statements with a dot expression on their left-hand side affect attributes for the object of that dot expression
• If the object is an instance, then assignment sets an instance attribute • If the object is a class, then assignment sets a class attribute
def leaves(t):
“””The leaf values in t. >>> leaves(fib_tree(5)) [1, 0, 1, 0, 1, 1, 0, 1] “””
if is_leaf(t):
return [label(t)] else:
if n == 0 or n == 1: return tree(n)
else:
left = fib_tree(n-2),
right = fib_tree(n-1)
fib_n = label(left) + label(right) return tree(fib_n, [left, right])
Call expression
return sum([leaves(b) for b in branches(t)], []) class Tree:
.
be any valid Python expression. simple name.
def __init__(self, label, branches=[]): self.label = label
for branch in branches:
assert isinstance(branch, Tree) self.branches = list(branches)
def is_leaf(self):
return not self.branches
def leaves(tree):
“The leaf values in a tree.” if tree.is_leaf():
return [tree.label] else:
return sum([leaves(b) for b in tree.branches], []) class Link: Some zero
empty=() lengthsequence
def __init__(self, first, rest=empty):
assert rest is Link.empty or isinstance(rest, Link)
Built-in isinstance function: returns True if branch has a class that is or inherits from Tree
balance: 0 holder: ‘Jim’ interest: 0.08
interest: 0.02 0.04 0.05 (withdraw, deposit, __init__)
balance: 0 holder: ‘Jim’
balance: 0 holder: ‘Tom’
self.first = first self.rest = rest
def __repr__(self): if self.rest:
rest = ‘, ‘ + repr(self.rest) else:
rest = ”
return ‘Link(‘+repr(self.first)+rest+’)’
def __str__(self): string = ‘<'
while self.rest is not Link.empty: string += str(self.first) + ' ' self = self.rest
return string + str(self.first) + '>‘
Link instance
Link instance
Account class attributes
Instance attributes of jim_account
>>> jim_account = Account(‘Jim’) >>> tom_account = Account(‘Tom’) >>> tom_account.interest
0.02
>>> jim_account.interest 0.02
>>> Account.interest = 0.04 >>> tom_account.interest 0.04
>>> jim_account.interest 0.04
Instance attributes of tom_account
>>> jim_account.interest = 0.08 >>> jim_account.interest
0.08
>>> tom_account.interest
0.04
>>> Account.interest = 0.05 >>> tom_account.interest 0.05
>>> jim_account.interest 0.08
first:
4
rest:
first:
rest:
5
>>> s = Link(4, Link(5)) >>> s
Link(4, Link(5))
>>> s.first
4
>>> s.rest Link(5)
>>> print(s) <4 5>
>>> print(s.rest) <5>
>>> s.rest.rest is Link.empty True
class CheckingAccount(Account):
“””A bank account that charges for withdrawals.””” withdraw_fee = 1
interest = 0.01
def withdraw(self, amount):
return Account.withdraw(self, amount + self.withdraw_fee) or
Anatomy of a recursive function:
• The def statement header is like any function
• Conditional statements check for base cases
• Base cases are evaluated without recursive calls
• Recursive cases are evaluated with recursive calls
def sum_digits(n):
“Sum the digits of positive integer n.” if n < 10:
return n else:
all_but_last, last = n // 10, n % 10 return sum_digits(all_but_last) + last
• Recursive decomposition: finding def count_partitions(n, m):
amount + self.withdraw_fee)
1. If it names an attribute in the class, return the attribute value.
simpler instances of a problem. • E.g., count_partitions(6, 4)
• Explore two possibilities:
• Use at least one 4
•Don't use any 4
• Solve two simpler problems:
• count_partitions(2, 4)
• count_partitions(6, 3)
• Tree recursion often involves
exploring different choices.
if n == 0: return 1
elif n < 0: return 0 elif m == 0: return 0
else:
with_m = count_partitions(n-m, m) without_m = count_partitions(n, m-1) return with_m + without_m
2. Otherwise, look up the name in the base class, if there is one. >>> ch = CheckingAccount(‘Tom’) # Calls Account.__init__
>>> ch.interest # Found in CheckingAccount 0.01
>>> ch.deposit(20) # Found in Account
20
>>> ch.withdraw(5) # Found in CheckingAccount 14
return super().withdraw( To look up a name in a class: