CMU 15-112: Fundamentals of Programming and Computer Science
Class Notes: Functional Programming with map/filter/reduce


  1. map / filter / reduce
    ############################################# # map(fn, L) ############################################# def myMap(fn, L): # iterative solution result = [ ] for val in L: result.append(fn(val)) return result def myMap(fn, L): # list comprehension return [fn(val) for val in L] def myMap(fn, L): # recursive solution if (len(L) == 0): return [ ] else: return [fn(L[0])] + myMap(fn, L[1:]) def myMap(fn, L, i=0): # recursive solution with less memory allocation (less garbage) if (i >= len(L)): return [ ] else: return [fn(L[i])] + myMap(fn, L, i+1) def myMap(fn, L): # recursive solution by halves if (len(L) == 0): return [ ] elif (len(L) == 1): return [fn(L[0])] else: mid = len(L)//2 return myMap(fn, L[:mid]) + myMap(fn, L[mid:]) def myMap(fn, L): # builtin map return list(map(fn, L)) def testMyMap(): print('Testing myMap()...', end='') # test with a named/def'd function def f(x): return x+1 assert(myMap(f, [ ]) == [ ]) assert(myMap(f, [1,2,3]) == [2,3,4]) # test with an anonymous lambda function stored in a local variable f = lambda x: x+5 assert(myMap(f, [ ]) == [ ]) assert(myMap(f, [1,2,3]) == [6,7,8]) # test with an anonymous lambda function not stored in a local variable assert(myMap(lambda x: 10*x, [ ]) == [ ]) assert(myMap(lambda x: 10*x, [1,2,3]) == [10, 20, 30]) print('Passed.') ############################################# # filter(fn, L) ############################################# def myFilter(fn, L): # iterative solution result = [ ] for val in L: if (fn(val) == True): result.append(val) return result def myFilter(fn, L): # list comprehension return [val for val in L if fn(val)] def myFilter(fn, L): # recursive solution if (len(L) == 0): return [ ] else: first = [L[0]] if (fn(L[0]) == True) else [ ] rest = myFilter(fn, L[1:]) return first + rest def myFilter(fn, L): # recursive solution (compressed) if (len(L) == 0): return [ ] else: return ([L[0]] if (fn(L[0]) == True) else [ ]) + myFilter(fn, L[1:]) def myFilter(fn, L, i=0): # recursive solution with less memory allocation (less garbage) if (i >= len(L)): return [ ] else: first = [L[i]] if (fn(L[i]) == True) else [ ] rest = myFilter(fn, L, i+1) return first + rest def myFilter(fn, L): # recursive solution by halves if (len(L) == 0): return [ ] elif (len(L) == 1): return [L[0]] if (fn(L[0]) == True) else [ ] else: mid = len(L)//2 return myFilter(fn, L[:mid]) + myFilter(fn, L[mid:]) def myFilter(fn, L): # builtin filter return list(filter(fn, L)) def testMyFilter(): print('Testing myFilter()...', end='') # test with a named/def'd function def f(x): return x > 2 assert(myFilter(f, [ ]) == [ ]) assert(myFilter(f, range(6)) == [3,4,5]) # test with an anonymous lambda function stored in a local variable f = lambda x: x < 2 assert(myFilter(f, [ ]) == [ ]) assert(myFilter(f, range(6)) == [0,1]) # test with an anonymous lambda function not stored in a local variable assert(myFilter(lambda x: abs(x-3)==1, [ ]) == [ ]) assert(myFilter(lambda x: abs(x-3)==1, range(6)) == [2,4]) print('Passed.') ############################################# # reduce(fn, L, initialValue) ############################################# def myReduce(fn, L, initialValue=0): # iterative solution result = initialValue for val in L: result = fn(result, val) return result def myReduce(fn, L, initialValue=0): # recursive solution if (len(L) == 0): return initialValue else: return myReduce(fn, L[1:], fn(initialValue, L[0])) def myReduce(fn, L, initialValue=0, i=0): # recursive solution with less memory allocation (less garbage) if (i >= len(L)): return initialValue else: return myReduce(fn, L, fn(initialValue, L[i]), i+1) import functools def myReduce(fn, L, initialValue=0): # builtin reduce return functools.reduce(fn, L, initialValue) def testMyReduce(): print('Testing myReduce()...', end='') # test with a named/def'd function def f(x, y): return x+y assert(myReduce(f, range(1, 6)) == 1+2+3+4+5) # test with an anonymous lambda function stored in a local variable f = lambda x,y: x*y assert(myReduce(f, range(1, 6), 1) == 1*2*3*4*5) # test with an anonymous lambda function not stored in a local variable assert(myReduce(lambda x,y: max(x,y), range(1,6), 1) == 5) print('Passed.') ############################################# # main ############################################# def testAll(): testMyMap() testMyFilter() testMyReduce() if (__name__ == '__main__'): testAll()

  2. Practice with map / filter / reduce
    from functools import reduce # Practice Code Tracing with reduce: def r1(L): return reduce(lambda x,y: x + y**2, L, 0) print(r1([2,3,5])) def r2(L): # Note: this would probably be better with a list comprehension or map return reduce(lambda x,y: x + [y**2], L, [ ]) print(r2([2,3,5])) def r3(L): def f(listPair, nextVal): (L1, L2) = listPair if (nextVal % 2 == 0): L1.append(nextVal) else: L2.append(nextVal) return listPair return reduce(f, L, ([],[])) print(r3(range(10,20))) def r4(L): def f(result, y): (a,b) = result return (min(a,y), max(b,y)) return reduce(f, L, (L[0], L[0])) print(r4([2,4,5,6,7,1,3])) def r5(d): return sorted(reduce(lambda L, y: L if (y%2==0) else L+[d[y]], d, [ ])) print(r5({1:'a', 2:'b', 3:'c', 4:'d', 5:'e', 6:'f'})) # Practice Task: Given L, return list of squares of odds in L # All of these work: def t1(L): return list(map(lambda x:x**2, filter(lambda x: x%2==1, L))) print(t1(range(6))) # [1, 9, 25] def t2(L): # of course, this is iterative... return [x**2 for x in filter(lambda x: x%2==1, L)] print(t2(range(6))) # [1, 9, 25] def t3(L): return reduce(lambda M,y: M if (y%2==0) else M+[y**2], L, [ ]) print(t3(range(6))) # [1, 9, 25]