Higher-Order Functions
Department of Computer Science & Engineering
The Pennsylvania State University
Characteristics of Functions
• A function's domain is the set of all inputs it might possibly take as arguments
• A function's range is the set of output values it might possibly return
• A pure function's behavior is the relationship it creates between input and output
def square(num):
return num*num
• Domain: num is a real number
• Range: returns a non-negative real number
• Behavior: return value is the square of the input
Designing a Function
• Give each function exactly one job
NOT
• Don’t repeat yourself. Implement a process just once, but execute it many times
• Define functions generally
Higher-Order Functions
Generalization
Shape:
3 3 2
Area: 1 ∙ r2 π ∙ r2 ( )∙r
2
Higher-Order Functions
from math import pi, sqrt
def areaSquare(r):
return r * r
def areaCircle(r):
return r * r * pi
def areaHexagon(r):
return r * r * 3 * sqrt(3) / 2
>>> areaSquare(4)
16
>>> areaCircle(5)
78.53981633974483
>>> areaHexagon(9)
210.44417311961857
>>> areaCircle(-5)
78.53981633974483
Higher-Order Functions
from math import pi, sqrt
def area(r, shape_constant):
if r<0:
return 'Length must be positive'
return r * r * shape_constant
Higher-Order Functions
The common structure among functions may be a computational process, rather than a
number
Higher-Order Functions
def sumNatural(n):
total, k = 0, 1
while k <= n:
total= total + k
k+=1
return total
>>> sumNatural(4)
10
>>> sumNatural(5)
15
Higher-Order Functions
def sumCubes(n):
total, k = 0, 1
while k <= n:
total= total + pow(k,3)
k+=1
return total
>>> sumCubes(4)
100
>>> sumCubes(5)
225
Higher-Order Functions
def natural(k):
return k
def cube(k):
return pow(k, 3)
def expression(k):
return 8 / ((k * 4 - 3)*(k * 4 - 1))
Higher-Order Functions
def summation(n, term):
Higher-Order Functions
def sumNatural(n):
return summation(n,natural)
def sumCubes(n):
return summation(n,cube)
>>> sumNatural(4)
10
>>> sumNatural(5)
15
>>> sumCubes(4)
100
>>> sumCubes(5)
225
Higher-Order Functions
def cube(k): Function with a single
argument (not called
return pow(k, 3) term)
def summation(n, term):
total, k = 0, 1 Formal parameter that will be
while k <= n: bound to a function
total= total + term(k)
k+=1
return total
The function bound to term
gets called here
def sumCubes(n):
return summation(n,cube)
Higher-Order Functions
Nested Functions
Returns a function that takes
def makeMult(n): an argument k and returns k
def multiply(k): times n
return k * n
return multiply
>>> times=makeMult(5)
>>> times(3)
15
OR
>>> makeMult(5)(3)
15
Purpose of Higher-Order Functions
• Functions are first-class: Functions can be manipulated as
values in our programming language.
• Higher-order function: A function that takes a function as an
argument value or returns a function as a return value
• Higher-order functions:
Express general methods of computation
Remove repetition from programs
Separate concerns among functions
Functional Programming
Department of Computer Science & Engineering
The Pennsylvania State University
Introduction
• Functions are a method of abstraction that describe compound operations
independent of the particular values of their arguments
• In functional programming, functions take input and produce output, without
any side effects
• Functions that manipulate functions are called higher-order functions
def fac(n):
total = 1 Imperative
for i in range(n):
total = total *(i+1)
return total
def fac(n):
if n == 0:
Functional return 1
else:
return n * fac(n-1)
Lambda Expressions
• Lambda expressions are anonymous functions that are usually passed as
parameters to other functions
• The general syntax of a lambda function is:
lambda argument_list: expression
• Lambda expressions can have only one line of code and automatically return
the computed value, so they do not need the return statement
def sum(x,y):
return x + y sum = lambda x, y : x + y
sum(3,4)
The map() function
map() takes a function and a collection of items and makes a new, empty
collection, runs the function on each item in the original collection and inserts
each return value into the new collection. It returns the new collection.
map(function_to_apply, list_of_inputs)
name_lengths = map(len, ["Alex", "Sandy", "Jeffrey"])
print(list(name_lengths))
squares = map(lambda x: x * x, [0, 1, 2, 3, 4, 5])
print(list(squares))
The filter() function
filter() offers an elegant way to filter out all the elements of a sequence for
which a function returns True:
filter(function_to_apply, list_of_inputs)
The function_to_apply has to return a Boolean value and will be applied to every
element of the list
number_list = range(-10, 5)
less_than_zero = filter(lambda x: x < 0, number_list)
print(list(less_than_zero))
The reduce() function
reduce() performs computation on a list and returns the result. While map applies a
function over a sequence, producing a sequence as output, reduce applies a function of
two arguments cumulatively to the items in a sequence, in order to reduce the sequence
to a single value.
reduce(function_to_apply, list_of_inputs)
from functools import reduce
product = reduce((lambda x, y: x * y), [1, 2, 3, 4, 5])
print(product)
List Comprehension
List comprehensions provide a concise way to create lists. Common applications are to
make new lists where each element is the result of some operations applied to each
member of another sequence or iterable, or to create a subsequence of those elements
that satisfy a certain condition
>>> squares = []
>>> for x in range(10):
... [Link](x**2)
...
>>> squares
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
squares = list(map(lambda x: x**2, range(10)))
squares = [x**2 for x in range(10)]
List Comprehension
The basic syntax for list comprehension is:
[expression for item in list if conditional]
This is equivalent to:
for item in list:
if conditional:
expression
What you want vs How to do
numbers = [1, 2, 3, 4, 5]
total = 0
for number in numbers:
total += number
print(total)
from functools import reduce
numbers = [1, 2, 3, 4, 5]
print(reduce(lambda x, y: x + y, numbers))
Summarizing