# Trees as nested tuples t = ((1, 2), (3, 4), 5) def count_leaves(tree): """Return the number of leaves in a tree. >>> count_leaves(t) 5 """ if type(tree) != tuple: return 1 return sum(map(count_leaves, tree)) def map_tree(tree, fn): """Return a tree with fn mapped to the leaves of tree. >>> map_tree(t, lambda x: x*x) ((1, 4), (9, 16), 25) """ if type(tree) != tuple: return fn(tree) return tuple(map_tree(branch, fn) for branch in tree) # Tree class (binary trees with internal values) class Tree(object): """A tree with internal values.""" def __init__(self, entry, left=None, right=None): self.entry = entry self.left = left self.right = right def __repr__(self): args = repr(self.entry) if self.left or self.right: args += ', {0}, {1}'.format(repr(self.left), repr(self.right)) return 'Tree({0})'.format(args) def fib_tree(n): """Return a Tree that represents a recursive Fibonacci calculation. >>> fib_tree(3) Tree(1, Tree(0), Tree(1)) """ if n == 1: return Tree(0) if n == 2: return Tree(1) left = fib_tree(n - 2) right = fib_tree(n - 1) return Tree(left.entry + right.entry, left, right) def count_entries(tree): """Return the number of entries in a Tree. >>> count_entries(fib_tree(6)) 15 """ if tree is None: return 0 return 1 + count_entries(tree.left) + count_entries(tree.right) def big_tree(left, right): """Return a tree of elements between left and right. >>> big_tree(0, 12) Tree(6, Tree(2, Tree(0), Tree(4)), Tree(10, Tree(8), Tree(12))) """ if left > right: return None split = left + (right - left)//2 return Tree(split, big_tree(left, split-2), big_tree(split+2, right)) # Memoization def memo(f): cache = {} def memoized(n): if n not in cache: cache[n] = f(n) return cache[n] return memoized def fib(n): """Compute the nth Fibonacci number. >>> fib(35) 5702887 """ if n == 1: return 0 if n == 2: return 1 return fib(n - 2) + fib(n - 1) @memo def fib_memo(n): """Compute the nth Fibonacci number. >>> fib_memo(35) 5702887 >>> fib_memo(100) 218922995834555169026 """ if n == 1: return 0 if n == 2: return 1 return fib_memo(n - 2) + fib_memo(n - 1) # From lecture 23/24: Recursive lists class Rlist(object): """A recursive list consisting of a first element and the rest. >>> s = Rlist(1, Rlist(2, Rlist(3))) >>> len(s) 3 >>> s[0] 1 >>> s[1] 2 >>> s[2] 3 """ class EmptyList(object): def __len__(self): return 0 empty = EmptyList() def __init__(self, first, rest=empty): self.first = first self.rest = rest def __repr__(self): f = repr(self.first) if self.rest is Rlist.empty: return 'Rlist({0})'.format(f) else: return 'Rlist({0}, {1})'.format(f, repr(self.rest)) def __len__(self): return 1 + len(self.rest) def __getitem__(self, i): if i == 0: return self.first return self.rest[i - 1] def extend_rlist(s1, s2): """Return a list containing the elements of s1 followed by those of s2. >>> s = Rlist(1, Rlist(2, Rlist(3))) >>> extend_rlist(s.rest, s) Rlist(2, Rlist(3, Rlist(1, Rlist(2, Rlist(3))))) """ if s1 is Rlist.empty: return s2 return Rlist(s1.first, extend_rlist(s1.rest, s2)) def map_rlist(s, fn): """Return an Rlist resulting from mapping fn over the elements of s. >>> s = Rlist(1, Rlist(2, Rlist(3))) >>> map_rlist(s, lambda x: x * x) Rlist(1, Rlist(4, Rlist(9))) """ if s is Rlist.empty: return s return Rlist(fn(s.first), map_rlist(s.rest, fn)) def filter_rlist(s, fn): """Filter the elements of s by predicate fn. >>> s = Rlist(1, Rlist(2, Rlist(3))) >>> filter_rlist(s, lambda x: x % 2 == 1) Rlist(1, Rlist(3)) """ if s is Rlist.empty: return s rest = filter_rlist(s.rest, fn) if fn(s.first): return Rlist(s.first, rest) return rest # Take 1: Sets as unordered sequences s = Rlist(1, Rlist(2, Rlist(3))) # A set is an Rlist with no duplicates def empty(s): return s is Rlist.empty def set_contains(s, v): """Return true if set s contains value v as an element. >>> set_contains(s, 2) True >>> set_contains(s, 5) False """ if empty(s): return False if s.first == v: return True return set_contains(s.rest, v) def adjoin_set(s, v): """Return a set containing all elements of s and element v. >>> t = adjoin_set(s, 4) >>> t Rlist(4, Rlist(1, Rlist(2, Rlist(3)))) """ if set_contains(s, v): return s return Rlist(v, s) def intersect_set(set1, set2): """Return a set containing all elements common to set1 and set2. >>> t = adjoin_set(s, 4) >>> intersect_set(t, map_rlist(s, lambda x: x*x)) Rlist(4, Rlist(1)) """ return filter_rlist(set1, lambda v: set_contains(set2, v)) def union_set(set1, set2): """Return a set containing all elements either in set1 or set2. >>> t = adjoin_set(s, 4) >>> union_set(t, s) Rlist(4, Rlist(1, Rlist(2, Rlist(3)))) """ set1_not_set2 = filter_rlist(set1, lambda v: not set_contains(set2, v)) return extend_rlist(set1_not_set2, set2)