Higher Order Functions
Thursday, 6/25
Announcements
Higher Order Functions
Review: Functions as Arguments
def summation(term, n):
i, total = 1, 0
while i <= n:
total += term(i)
i += 1
return total
>>> def double(x):
... return 2*x
...
>>> summation(double, 3)
12
1-argument�function
Higher Order Functions
Nested functions
Functions can be defined inside functions.
This is useful for helper functions.
def f(a, b, c):� numer_ab = a*b + b/a + a**b� denom_ac = a*c + c/a + a**c� return numer_ab / denom_ac
numer_ab & denom_ac are very similar!
Nested functions
Helper functions can simplify code!
def f(a, b, c):� def g(d):� return a*d + d/a + a**d� return g(b) / g(c)��f(2, 3, 4)
g is defined inside the body of f!
Nested functions
Helper functions can simplify code!
def f(2, b, c):� def g(d):� return a*d + d/a + a**d� return g(b) / g(c)��f(2, 3, 4)
Nested functions
Helper functions can simplify code!
def f(2, b, c):� def g(d):� return 2*d + d/2 + 2**d� return g(b) / g(c)��f(2, 3, 4)
Nested functions
Helper functions can simplify code!
def f(2, 3, c):� def g(d):� return 2*d + d/2 + 2**d� return g(3) / g(4)��f(2, 3, 4)
Nested functions
Helper functions can simplify code!
def f(2, 3, c):� def g(3):� return 2*d + d/2 + 2**d� return g(3) / g(4)��f(2, 3, 4)
Nested functions
Helper functions can simplify code!
def f(2, 3, c):� def g(3):� return 2*3 + 3/2 + 2**3� return g(3) / g(4)��f(2, 3, 4)
Nested functions
Helper functions can simplify code!
def f(2, 3, c):� def g(3):� return 2*3 + 3/2 + 2**3� return 15.5 / g(4)��f(2, 3, 4)
Nested functions
Helper functions can simplify code!
def f(2, 3, 4):� def g(4):� return 2*4 + 4/2 + 2**4� return 15.5 / g(4)��f(2, 3, 4)
Nested functions
Helper functions can simplify code!
def f(2, 3, 4):� def g(4):� return 2*4 + 4/2 + 2**4� return 15.5 / 26.0��f(2, 3, 4)
Nested functions
Helper functions can simplify code!
def f(2, 3, 4):� def g(4):� return 2*4 + 4/2 + 2**4� return 15.5 / 26.0��1.6774193548387097
Higher Order Functions
Adders
Functions that add some number to another number
def add_1(x):� return x + 1
def add_2(x):� return x + 2
def add_3(x):� return x + 3
...
def add_128(x):� return x + 128
(Demo)
make_adder
def make_adder(n):� """Return func that takes one arg k and returns k + n�� >>> add_three = make_adder(3)� >>> add_three(4)� 7� """� def adder(k):� return k + n� return adder
function that returns a function
nested function
name add_three is bound to a function
can refer to names in enclosing functions
make_adder
make_adder
( 4 )
( 3 )
def make_adder(n):� def adder(k):� return k + n� return adder
For compound call expressions, read left to right
<func make_adder>
3
<func adder>
make_adder
( 4 )
def make_adder(n):� def adder(k):� return k + n� return adder
For compound call expressions, read left to right
7
<func adder>
Environment diagram: make_adder
def make_adder(n):� def adder(k):� return k + n� return adder
make_adder(3)(4)
Label function with its parent frame
Parent frame: frame in which the function is defined
Environment diagram: make_adder
def make_adder(n):� def adder(k):� return k + n� return adder
make_adder(3)(4)
Label function with its parent frame
Copy parent frame from label on function object
Label frame with a unique identifier
Environment diagram: make_adder
def make_adder(n):� def adder(k):� return k + n� return adder
make_adder(3)(4)
Parent frame is f1!
Environment diagram: make_adder
def make_adder(n):� def adder(k):� return k + n� return adder
make_adder(3)(4)
Environment diagram: make_adder
def make_adder(n):� def adder(k):� return k + n� return adder
make_adder(3)(4)
Environment diagram: make_adder
def make_adder(n):� def adder(k):� return k + n� return adder
make_adder(3)(4)
To lookup value of n, follow the parent frames.
n?
Higher Order Functions
make_adder
def make_adder(n):� def adder(k):� return k + n� return adder
Why bother naming adder if we only use the name once?
Lambda functions
def make_adder(n):� return lambda k: n + k
The lambda expression creates an anonymous function!
lambda <parameters>: <return expression>
Translating between named and anonymous functions
def square(x):� return x * x
square = lambda x: x * x
No “return”!
Translating between named and anonymous functions
def make_adder(n):� return lambda k: n + k
make_adder = lambda n: lambda k: n + k
Translating between named and anonymous functions
def make_adder(n):� return lambda k: n + k
def make_adder(n):� def adder(k):� return n + k� return adder
make_adder = lambda n: lambda k: n + k
Lambda functions
Lambdas are expressions! You can use them anywhere you can use any other expression.
A lambda’s body can only be a single expression. This is the return expression.
Use sparingly! Better to have clear names.
Environment diagram: lambdas
id_func = lambda x: x
id_func(0)
Environment diagram: make_adder
def make_adder(n):� return lambda k: n + k
add_3 = make_adder(3)
add_3(4)
Lambda functions: practice
>>> def summation(term, n):
... i, total = 1, 0
... while i <= n:
... total += term(i)
... i += 1
... return total
...
>>> summation(lambda x: x**2, 3)
14
Lambda functions: practice
def repeat(f, x):� while f(x) != x:� x = f(x)� return x
def g(y):� return (y + 5) // 3
result = repeat(g, 5)
Hog demo!