CSE 399-004, Spring 2006Python ProgrammingHandout 3 (lectures 4 & 5)www.seas.upenn.edu/~cse39905This Week•Today•Functional Programming•A little bit of Pythonic styles•Memoization•Sets•Wednesday -- Review•HW 2 Solutions•Come with questions!•Friday -- Quiz in this room•closed book, but you can bring one page of notes2Functional Programmingmap and filter•intuition: function as data•we have already seen functional programming a lot!•list comprehension, custom comparison function4map(f, a)filter(p, a)[ f(x) for x in a ][ x for x in a if p(x) ]>>> map(int, ['1','2'])[1, 2]>>> " ".join(map(str, [1,2]))1 2>>> def iseven(x):... return x % 2 == 0... >>> filter(iseven, [-1, 0])[0][ f(x) for x in a if p(x) ]map(f, filter(p, a))lambda•map/filter in one line for custom functions?•“anonymous inline function”•borrowed from LISP, Scheme, ML, OCaml5>>> f = lambda x: x*2 >>> f(1)2>>> map (lambda x: x**2, [1, 2])[1, 4]>>> filter (lambda x: x > 0, [-1, 1])[1]>>> g = lambda x,y : x+y>>> g(5,6)11>>> map (lambda (x,y): x+y, [(1,2), (3,4)])[3, 7]more on lambda6>>> f = lambda : "good!">>> f<function <lambda> at 0x381730>>>> f()'good!'>>> a = [5, 1, 2, 6, 4]>>> a.sort(lambda x,y : y - x)>>> a[6, 5, 4, 2, 1]lazy evaluationcustom comparisonreduce•apply binary operator recursively•((((1+2)+3)+4)+5)•initial value7>>> def sum(seq):... return reduce(lambda x, y: x+y, seq, 0)... >>> sum(range(1, 11))55>>> sum([])0sum() is built-in>>> reduce(lambda x,y : x*y, [1,2,3,4,5]) 120>>> reduce(lambda x,y : x+y, [[1],[2],[3]],[])[1, 2, 3]>>> reduce(lambda x,y : x+y, [1])1implementing reduce()8>>> def myreduce(f, seq, initial = None):... if seq == []:... return initial... if len(seq) == 1:... return seq[0]... return f( myreduce(f,seq[:-1],initial), seq[-1] )... >>> myreduce(lambda x,y: x+y, [1,2,3])6>>> def smaller(a,b):... if a < b:... return a... return b... >>> f = lambda seq: reduce (smaller, seq)>>> f([1,0,2,5,-1])-1>>> min([1,0,2,5,-1])-1min(), max() are builtinFunctional Style•higher-order functions (taking functions as arguments)•almost no assignments (no side conditions)•often recursive, and sometimes lazy9def perm(n, m, current = []): if len(current) == m:for elem in current:print elem,printreturn 1sum = 0for i in range(1,n+1):if i not in current:sum += perm( n, m, current + [i] )return sumFunctional Style•higher-order functions (taking functions as arguments)•almost no assignments (no side conditions)•often recursive, and sometimes lazy10def perm(n, m, current = []): if len(current) == m:print " ".join( map(str, current) )return 1return sum([ perm(n, m, current + [i]) \for i in range(1, n+1) if i not in current ])print perm (3, 2)Pythonic Styles•do not write ... when you can write ...11for key in d.keys(): for key in d:if d.has_key(key): if key in d:i = 0 for x in a: ... i += 1for i, x in enumerate(a):a[0:len(a) - i] a[:-i]for line in \ sys.stdin.readlines():for line in sys.stdin:for x in a: print x,printprint " ".join(map(str, a))s = ""for i in range(lev): s += " "print sprint " " * levMemoizationFibonacci Revisited13def fib(n): a, b = 0, 1for i in range(n-1):a, b = b, a+b return adef fib(n):if n <= 1:return nelse:return fib(n-1) + fib(n-2)version 2 (recursive)intuitive, but ...version 1 (non-recursive)fast, but counter-intuitiveFibonacci Revisited14def fib(n): a, b = 0, 1for i in range(n-1):a, b = b, a+b return adef fib(n):if n <= 1:return nelse:return fib(n-1) + fib(n-2)version 1 (non-recursive)fast, but counter-intuitiveQiushi “Andrew” MaoHow bad it is?15def fib(n): a, b = 0, 1for i in range(n-1):a, b = b, a+b return adef fib(n):if n <= 1:return nelse:return fib(n-1) + fib(n-2)version 1 (non-recursive)fast, but counter-intuitiveO(n)O(1.6n)How to Solve this Problem?16def fib(n): a, b = 0, 1for i in range(n-1):a, b = b, a+b return adef fib(n):if n <= 1:return nelse:return fib(n-1) + fib(n-2)version 1 (non-recursive)fast, but counter-intuitiveZhishuang ZhangMemoization17def fib(n): a, b = 0, 1for i in range(n-1):a, b = b, a+b return afibs = {}def fib(n):if n in fibs:return fibs[n]if n <= 1:fibs[n] = nelse:fibs[n] = fib(n-1) + fib(n-2)return fibs[n]version 3 (memoized)intuitive, and fast!version 1 (non-recursive)fast, but counter-intuitive54321(3)(2)(1)0O(n)O(n)It’s more than that...18>>> fib(5)5>>> fib(6)8def fib(n): a, b = 0, 1for i in range(n-1):a, b = b, a+b return alecture 1 (non-recursive)fast, but counter-intuitive•anything recursive can (and should) be memoized•to share overlapping subproblems>>> fact(3)6>>> fact(5)120>>> gcd(4,2)2>>> gcd(4,6)2Counting Permutations19def perm(n, m, current = []): if len(current) == m:print " ".join( map(str, current) )return 1 return sum([ perm(n, m, current + [i]) \for i in range(1, n+1) if i not in current ])•using current as states•Exercise - will be discussed on Wednesday•lists are not hashable (but tuples are)>>> d = { [1,2] : 'a' }TypeError>>> d = { (1,2) : 'a' }OK!>>> d = { ([1], 2): 'a' }TypeErrorSetsidentity maps, unordered collectionsConstruction and Operations•sets do not have a special syntactic form•unlike [] for lists, () for tuples and {} for dicts•construction from lists, tuples, dicts (keys), and strs•in, not in, add, remove21>>> a = set((1,2))>>> aset([1, 2])>>> b = set([1,2])>>> a == bTrue>>> c = set({1:'a', 2:'b'})>>> cset([1, 2])>>> a = set([])>>> 1 in aFalse>>> a.add(1)>>> a.add('b')>>> aset([1, 'b'])>>> a.remove(1)>>> aset(['b'])Binary Operators•union, intersection, difference, xor•elements in a set are unique!22>>> a = set('abracadabra')>>> b = set('alacazam')>>> a set(['a', 'r', 'b', 'c', 'd'])>>> a - bset(['r', 'd', 'b'])>>> a | bset(['a', 'c', 'r', 'd', 'b', 'm', 'z', 'l'])>>> a & bset(['a', 'c'])>>> a ^ bset(['r', 'd', 'b', 'm', 'z', 'l'])set and frozenset type23Implementation•added to Python since 2.4•currently as identity-mapping dictionaries•s = set(a) is translated into•s = dict([(x, x) for x in a ]), or•s = dict([(x, None) for x in a ])•will be implemented as “bitwise” in Python 2.5•operations will be much