# Recursive lists in OOP 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 # 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)) # 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) # Fibonacci def fib(n): if n == 1: return 0 if n == 2: return 1 return fib(n - 2) + fib(n - 1) def fib_iter(n): prev, curr = 1, 0 for _ in range(n-1): prev, curr = curr, prev + curr return curr # Counting factors from math import sqrt def count_factors(n): """Count the positive integers that evenly divide n. >>> count_factors(576) 21 """ factors = 0 for k in range(1, n + 1): if n % k == 0: print(k) factors += 1 return factors def count_factors_fast(n): """Count the positive integers that evenly divide n. >>> count_factors_fast(576) 21 """ sqrt_n = sqrt(n) k, factors = 1, 0 while k < sqrt_n: if n % k == 0: factors += 2 k += 1 if k * k == n: factors += 1 return factors # Exponentiation def exp(b, n): """Return b to the n. >>> exp(2, 10) 1024 """ if n == 0: return 1 return b * exp(b, n - 1) def square(x): return x * x def fast_exp(b, n): """Return b to the n. >>> fast_exp(2, 10) 1024 """ if n == 0: return 1 if n % 2 == 0: return square(fast_exp(b, n // 2)) else: return b * fast_exp(b, n - 1)