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()
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]