### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# CS 61A Lecture 4 CS 61A

CAL

### View Full Document

## About this Document

## 4

## 0

## Popular in The Structure and Interpretation of Computer Programs

## Popular in Elect Engr & Computer Science

This 26 page Class Notes was uploaded by Scott Lee on Thursday September 8, 2016. The Class Notes belongs to CS 61A at University of California Berkeley taught by John DeNero in Fall 2016. Since its upload, it has received 4 views. For similar materials see The Structure and Interpretation of Computer Programs in Elect Engr & Computer Science at University of California Berkeley.

## Reviews for CS 61A Lecture 4

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/08/16

61A Lecture 4 Announcements Iteration Example The Fibonacci Sequence 4 The Fibonacci Sequence 4 The Fibonacci Sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 4 The Fibonacci Sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 4 The Fibonacci Sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 4 The Fibonacci Sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 4 def ﬁb(n): """Compute the nth Fibonacci number, for N >= 1.""" pred, curr = 0, 1 # 0th and 1st Fibonacci numbers k = 1 # curr is the kth Fibonacci number while k < n: pred, curr = curr, pred + curr k = k + 1 return curr The Fibonacci Sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 4 def ﬁb(n): """Compute the nth Fibonacci number, for N >= 1.""" pred, curr = 0, 1 # 0th and 1st Fibonacci numbers k = 1 # curr is the kth Fibonacci number while k < n: pred, curr = curr, pred + curr k = k + 1 return curr The Fibonacci Sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 4 The next Fibonacci number is the sum of the current one and its predecessor ﬁb n pred curr k 5 def ﬁb(n): """Compute the nth Fibonacci number, for N >= 1.""" pred, curr = 0, 1 # 0th and 1st Fibonacci numbers k = 1 # curr is the kth Fibonacci number while k < n: pred, curr = curr, pred + curr k = k + 1 return curr The Fibonacci Sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 4 The next Fibonacci number is the sum of the current one and its predecessor ﬁb n pred curr k 5 def ﬁb(n): """Compute the nth Fibonacci number, for N >= 1.""" pred, curr = 0, 1 # 0th and 1st Fibonacci numbers k = 1 # curr is the kth Fibonacci number while k < n: pred, curr = curr, pred + curr k = k + 1 return curr The Fibonacci Sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 4 The next Fibonacci number is the sum of the current one and its predecessor 1 ﬁb n pred curr k 5 def ﬁb(n): """Compute the nth Fibonacci number, for N >= 1.""" pred, curr = 0, 1 # 0th and 1st Fibonacci numbers k = 1 # curr is the kth Fibonacci number while k < n: pred, curr = curr, pred + curr k = k + 1 return curr The Fibonacci Sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 4 The next Fibonacci number is the sum of the current one and its predecessor 1 ﬁb n pred curr k 5 def ﬁb(n): """Compute the nth Fibonacci number, for N >= 1.""" pred, curr = 0, 1 # 0th and 1st Fibonacci numbers k = 1 # curr is the kth Fibonacci number while k < n: pred, curr = curr, pred + curr k = k + 1 return curr The Fibonacci Sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 4 The next Fibonacci number is the sum of the current one and its predecessor 2 ﬁb n pred curr k 5 def ﬁb(n): """Compute the nth Fibonacci number, for N >= 1.""" pred, curr = 0, 1 # 0th and 1st Fibonacci numbers k = 1 # curr is the kth Fibonacci number while k < n: pred, curr = curr, pred + curr k = k + 1 return curr The Fibonacci Sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 4 The next Fibonacci number is the sum of the current one and its predecessor 3 ﬁb n pred curr k 5 def ﬁb(n): """Compute the nth Fibonacci number, for N >= 1.""" pred, curr = 0, 1 # 0th and 1st Fibonacci numbers k = 1 # curr is the kth Fibonacci number while k < n: pred, curr = curr, pred + curr k = k + 1 return curr The Fibonacci Sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 4 The next Fibonacci number is the sum of the current one and its predecessor 4 ﬁb n pred curr k 5 def ﬁb(n): """Compute the nth Fibonacci number, for N >= 1.""" pred, curr = 0, 1 # 0th and 1st Fibonacci numbers k = 1 # curr is the kth Fibonacci number while k < n: pred, curr = curr, pred + curr k = k + 1 return curr The Fibonacci Sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 4 The next Fibonacci number is the sum of the current one and its predecessor 5 Discussion Question 5 def ﬁb(n): """Compute the nth Fibonacci number?""" pred, curr = 0, 1 k = 1 while k < n: pred, curr = curr, pred + curr k = k + 1 return curr 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 Discussion Question 5 def ﬁb(n): """Compute the nth Fibonacci number?""" pred, curr = 0, 1 k = 1 while k < n: pred, curr = curr, pred + curr k = k + 1 return curr 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 pred, curr = 1, 0 k = 0 Discussion Question 5 Is this alternative deﬁnition of ﬁb the same or different from the original ﬁb? def ﬁb(n): """Compute the nth Fibonacci number?""" pred, curr = 0, 1 k = 1 while k < n: pred, curr = curr, pred + curr k = k + 1 return curr 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 pred, curr = 1, 0 k = 0 Discussion Question 5 Is this alternative deﬁnition of ﬁb the same or different from the original ﬁb? def ﬁb(n): """Compute the nth Fibonacci number?""" pred, curr = 0, 1 k = 1 while k < n: pred, curr = curr, pred + curr k = k + 1 return curr 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 I'm still here pred, curr = 1, 0 k = 0 Discussion Question 5 Is this alternative deﬁnition of ﬁb the same or different from the original ﬁb? def ﬁb(n): """Compute the nth Fibonacci number?""" pred, curr = 0, 1 k = 1 while k < n: pred, curr = curr, pred + curr k = k + 1 return curr 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 I'm still here pred, curr = 1, 0 k = 0 (Demo) Designing Functions Describing Functions 7 Describing Functions A function's domain is the set of all inputs it might possibly take as arguments. 7 Describing 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. 7 Describing 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. 7 Describing 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. 7 def square(x): """Return X * X.""" Describing 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. 7 def square(x): """Return X * X.""" def ﬁb(n): """Compute the nth Fibonacci number, for N >= 1.""" Describing 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. 7 def square(x): """Return X * X.""" def ﬁb(n): """Compute the nth Fibonacci number, for N >= 1.""" x is a real number Describing 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. 7 def square(x): """Return X * X.""" def ﬁb(n): """Compute the nth Fibonacci number, for N >= 1.""" x is a real number returns a non-negative real number Describing 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. 7 def square(x): """Return X * X.""" def ﬁb(n): """Compute the nth Fibonacci number, for N >= 1.""" x is a real number returns a non-negative real number return value is the square of the input Describing 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. 7 def square(x): """Return X * X.""" def ﬁb(n): """Compute the nth Fibonacci number, for N >= 1.""" x is a real number returns a non-negative real number return value is the square of the input n is an integer greater than or equal to 1 Describing 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. 7 def square(x): """Return X * X.""" def ﬁb(n): """Compute the nth Fibonacci number, for N >= 1.""" x is a real number returns a non-negative real number return value is the square of the input n is an integer greater than or equal to 1 returns a Fibonacci number Describing 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. 7 def square(x): """Return X * X.""" def ﬁb(n): """Compute the nth Fibonacci number, for N >= 1.""" x is a real number returns a non-negative real number return value is the square of the input n is an integer greater than or equal to 1 returns a Fibonacci number return value is the nth Fibonacci number A Guide to Designing Function 8 A Guide to Designing Function Give each function exactly one job, but make it apply to many related situations 8 A Guide to Designing Function Give each function exactly one job, but make it apply to many related situations 8 >>> round(1.23) 1 A Guide to Designing Function Give each function exactly one job, but make it apply to many related situations 8 >>> round(1.23, 1) 1.2 >>> round(1.23) 1 A Guide to Designing Function Give each function exactly one job, but make it apply to many related situations 8 >>> round(1.23, 1) 1.2 >>> round(1.23, 0) 1 >>> round(1.23) 1 A Guide to Designing Function Give each function exactly one job, but make it apply to many related situations 8 >>> round(1.23, 1) 1.2 >>> round(1.23, 0) 1 >>> round(1.23, 5) 1.23 >>> round(1.23) 1 A Guide to Designing Function Give each function exactly one job, but make it apply to many related situations 8 Don’t repeat yourself (DRY). Implement a process just once, but execute it many times. >>> round(1.23, 1) 1.2 >>> round(1.23, 0) 1 >>> round(1.23, 5) 1.23 >>> round(1.23) 1 A Guide to Designing Function Give each function exactly one job, but make it apply to many related situations 8 Don’t repeat yourself (DRY). Implement a process just once, but execute it many times. >>> round(1.23, 1) 1.2 >>> round(1.23, 0) 1 >>> round(1.23, 5) 1.23 (Demo) >>> round(1.23) 1 A Guide to Designing Function Give each function exactly one job, but make it apply to many related situations 8 Don’t repeat yourself (DRY). Implement a process just once, but execute it many times. >>> round(1.23, 1) 1.2 >>> round(1.23, 0) 1 >>> round(1.23, 5) 1.23 (Demo) >>> round(1.23) 1 Generalization Generalizing Patterns with Arguments 10 Generalizing Patterns with Arguments Regular geometric shapes relate length and area. 10 Shape: Generalizing Patterns with Arguments Regular geometric shapes relate length and area. 10 Shape: Generalizing Patterns with Arguments Regular geometric shapes relate length and area. r 10 Shape: Generalizing Patterns with Arguments Regular geometric shapes relate length and area. r r 10 Shape: Generalizing Patterns with Arguments Regular geometric shapes relate length and area. r r r 10 Shape: Generalizing Patterns with Arguments Regular geometric shapes relate length and area. r r r Area: 10 Shape: r2 Generalizing Patterns with Arguments Regular geometric shapes relate length and area. r r r Area: 10 Shape: r2 ⇡ · r2 Generalizing Patterns with Arguments Regular geometric shapes relate length and area. r r r Area: 10 Shape: r2 ⇡ · r2 3 p3 2 · r2 Generalizing Patterns with Arguments Regular geometric shapes relate length and area. r r r Area: 10 Shape: r2 ⇡ · r2 3 p3 2 · r2 1 · r2 Generalizing Patterns with Arguments Regular geometric shapes relate length and area. r r r Area: 10 Shape: r2 ⇡ · r2 3 p3 2 · r2 1 · r2 Generalizing Patterns with Arguments Regular geometric shapes relate length and area. r r r Area: 10 Shape: r2 ⇡ · r2 3 p3 2 · r2 1 · r2 Generalizing Patterns with Arguments Regular geometric shapes relate length and area. r r r Area: 10 Shape: r2 ⇡ · r2 3 p3 2 · r2 1 · r2 Generalizing Patterns with Arguments Regular geometric shapes relate length and area. r r r Area: 10 Shape: r2 ⇡ · r2 3 p3 2 · r2 1 · r2 Generalizing Patterns with Arguments Regular geometric shapes relate length and area. r r r Area: Finding common structure allows for shared implementation 10 Shape: r2 ⇡ · r2 3 p3 2 · r2 1 · r2 Generalizing Patterns with Arguments Regular geometric shapes relate length and area. r r r Area: Finding common structure allows for shared implementation 10 (Demo) Higher-Order Functions Generalizing Over Computational Processes 12 Generalizing Over Computational Processes The common structure among functions may be a computational process, rather than a number. 12 X 5 k=1 k = 1 + 2 + 3 + 4 + 5 = 15 X 5 k=1 k3 = 13 + 23 + 33 + 43 + 53 = 225 X 5 k=1 8 (4k ! 3) · (4k ! 1) = 8 3 + 8 35 + 8 99 + 8 195 + 8 323 = 3.04 Generalizing Over Computational Processes The common structure among functions may be a computational process, rather than a number. 12 X 5 k=1 k = 1 + 2 + 3 + 4 + 5 = 15 X 5 k=1 k3 = 13 + 23 + 33 + 43 + 53 = 225 X 5 k=1 8 (4k ! 3) · (4k ! 1) = 8 3 + 8 35 + 8 99 + 8 195 + 8 323 = 3.04 Generalizing Over Computational Processes The common structure among functions may be a computational process, rather than a number. 12 X 5 k=1 k = 1 + 2 + 3 + 4 + 5 = 15 X 5 k=1 k3 = 13 + 23 + 33 + 43 + 53 = 225 X 5 k=1 8 (4k ! 3) · (4k ! 1) = 8 3 + 8 35 + 8 99 + 8 195 + 8 323 = 3.04 Generalizing Over Computational Processes The common structure among functions may be a computational process, rather than a number. 12 X 5 k=1 k = 1 + 2 + 3 + 4 + 5 = 15 X 5 k=1 k3 = 13 + 23 + 33 + 43 + 53 = 225 X 5 k=1 8 (4k ! 3) · (4k ! 1) = 8 3 + 8 35 + 8 99 + 8 195 + 8 323 = 3.04 Generalizing Over Computational Processes The common structure among functions may be a computational process, rather than a number. 12 X 5 k=1 k = 1 + 2 + 3 + 4 + 5 = 15 X 5 k=1 k3 = 13 + 23 + 33 + 43 + 53 = 225 X 5 k=1 8 (4k ! 3) · (4k ! 1) = 8 3 + 8 35 + 8 99 + 8 195 + 8 323 = 3.04 Generalizing Over Computational Processes The common structure among functions may be a computational process, rather than a number. 12 (Demo) Summation Example hof.py Page 2 return total def identity(k): return k def cube(k): return pow(k, 3) def summation(n, term): """Sum the ﬁrst n terms of a sequence. >>> summation(5, cube) 225 """ total, k = 0, 1 while k <= n: total, k = total + term(k), k + 1 return total def pi_term(k): return 8 / (k * 4 − 3) / (k * 4 − 1) # Local function deﬁnitions; returning functions def make_adder(n): """Return a function that takes one argument k and returns k + n. >>> add_three = make_adder(3) >>> add_three(4) 7 """ def adder(k): return k + n return adder def compose1(f, g): """Return a function that composes f and g. f, g −− functions of a single argument """ def h(x): return f(g(x)) return h @main def run(): interact() 13 Summation Example hof.py Page 2 return total def identity(k): return k def cube(k): return pow(k, 3) def summation(n, term): """Sum the ﬁrst n terms of a sequence. >>> summation(5, cube) 225 """ total, k = 0, 1 while k <= n: total, k = total + term(k), k + 1 return total def pi_term(k): return 8 / (k * 4 − 3) / (k * 4 − 1) # Local function deﬁnitions; returning functions def make_adder(n): """Return a function that takes one argument k and returns k + n. >>> add_three = make_adder(3) >>> add_three(4) 7 """ def adder(k): return k + n return adder def compose1(f, g): """Return a function that composes f and g. f, g −− functions of a single argument """ def h(x): return f(g(x)) return h @main def run(): interact() Function of a single argument (not called "term") 13 Summation Example hof.py Page 2 return total def identity(k): return k def cube(k): return pow(k, 3) def summation(n, term): """Sum the ﬁrst n terms of a sequence. >>> summation(5, cube) 225 """ total, k = 0, 1 while k <= n: total, k = total + term(k), k + 1 return total def pi_term(k): return 8 / (k * 4 − 3) / (k * 4 − 1) # Local function deﬁnitions; returning functions def make_adder(n): """Return a function that takes one argument k and returns k + n. >>> add_three = make_adder(3) >>> add_three(4) 7 """ def adder(k): return k + n return adder def compose1(f, g): """Return a function that composes f and g. f, g −− functions of a single argument """ def h(x): return f(g(x)) return h @main def run(): interact() Function of a single argument (not called "term") A formal parameter that will be bound to a function 13 Summation Example hof.py Page 2 return total def identity(k): return k def cube(k): return pow(k, 3) def summation(n, term): """Sum the ﬁrst n terms of a sequence. >>> summation(5, cube) 225 """ total, k = 0, 1 while k <= n: total, k = total + term(k), k + 1 return total def pi_term(k): return 8 / (k * 4 − 3) / (k * 4 − 1) # Local function deﬁnitions; returning functions def make_adder(n): """Return a function that takes one argument k and returns k + n. >>> add_three = make_adder(3) >>> add_three(4) 7 """ def adder(k): return k + n return adder def compose1(f, g): """Return a function that composes f and g. f, g −− functions of a single argument """ def h(x): return f(g(x)) return h @main def run(): interact() Function of a single argument (not called "term") A formal parameter that will be bound to a function The function bound to term gets called here 13 Summation Example hof.py Page 2 return total def identity(k): return k def cube(k): return pow(k, 3) def summation(n, term): """Sum the ﬁrst n terms of a sequence. >>> summation(5, cube) 225 """ total, k = 0, 1 while k <= n: total, k = total + term(k), k + 1 return total def pi_term(k): return 8 / (k * 4 − 3) / (k * 4 − 1) # Local function deﬁnitions; returning functions def make_adder(n): """Return a function that takes one argument k and returns k + n. >>> add_three = make_adder(3) >>> add_three(4) 7 """ def adder(k): return k + n return adder def compose1(f, g): """Return a function that composes f and g. f, g −− functions of a single argument """ def h(x): return f(g(x)) return h @main def run(): interact() Function of a single argument (not called "term") A formal parameter that will be bound to a function The function bound to term gets called here The cube function is passed as an argument value 13 Summation Example hof.py Page 2 return total def identity(k): return k def cube(k): return pow(k, 3) def summation(n, term): """Sum the ﬁrst n terms of a sequence. >>> summation(5, cube) 225 """ total, k = 0, 1 while k <= n: total, k = total + term(k), k + 1 return total def pi_term(k): return 8 / (k * 4 − 3) / (k * 4 − 1) # Local function deﬁnitions; returning functions def make_adder(n): """Return a function that takes one argument k and returns k + n. >>> add_three = make_adder(3) >>> add_three(4) 7 """ def adder(k): return k + n return adder def compose1(f, g): """Return a function that composes f and g. f, g −− functions of a single argument """ def h(x): return f(g(x)) return h @main def run(): interact() Function of a single argument (not called "term") A formal parameter that will be bound to a function The function bound to term gets called here The cube function is passed as an argument value 0 + 1 + 8 + 27 + 64 + 125 13 Functions as Return Values (Demo) Locally Deﬁned Functions 15 Locally Deﬁned Functions Functions deﬁned within other function bodies are bound to names in a local frame 15 hof.py Page 2 return total def identity(k): return k def cube(k): return pow(k, 3) def summation(n, term): """Sum the ﬁrst n terms of a sequence. >>> summation(5, cube) 225 """ total, k = 0, 1 while k <= n: total, k = total + term(k), k + 1 return total def pi_term(k): return 8 / (k * 4 − 3) / (k * 4 − 1) # Local function deﬁnitions; returning functions def make_adder(n): """Return a function that takes one argument k and returns k + n. >>> add_three = make_adder(3) >>> add_three(4) 7 """ def adder(k): return k + n return adder def compose1(f, g): """Return a function that composes f and g. f, g −− functions of a single argument """ def h(x): return f(g(x)) return h @main def run(): interact() Locally Deﬁned Functions Functions deﬁned within other function bodies are bound to names in a local frame 15 hof.py Page 2 return total def identity(k): return k def cube(k): return pow(k, 3) def summation(n, term): """Sum the ﬁrst n terms of a sequence. >>> summation(5, cube) 225 """ total, k = 0, 1 while k <= n: total, k = total + term(k), k + 1 return total def pi_term(k): return 8 / (k * 4 − 3) / (k * 4 − 1) # Local function deﬁnitions; returning functions def make_adder(n): """Return a function that takes one argument k and returns k + n. >>> add_three = make_adder(3) >>> add_three(4) 7 """ def adder(k): return k + n return adder def compose1(f, g): """Return a function that composes f and g. f, g −− functions of a single argument """ def h(x): return f(g(x)) return h @main def run(): interact() Locally Deﬁned Functions A function that returns a function Functions deﬁned within other function bodies are bound to names in a local frame 15 hof.py Page 2 return total def identity(k): return k def cube(k): return pow(k, 3) def summation(n, term): """Sum the ﬁrst n terms of a sequence. >>> summation(5, cube) 225 """ total, k = 0, 1 while k <= n: total, k = total + term(k), k + 1 return total def pi_term(k): return 8 / (k * 4 − 3) / (k * 4 − 1) # Local function deﬁnitions; returning functions def make_adder(n): """Return a function that takes one argument k and returns k + n. >>> add_three = make_adder(3) >>> add_three(4) 7 """ def adder(k): return k + n return adder def compose1(f, g): """Return a function that composes f and g. f, g −− functions of a single argument """ def h(x): return f(g(x)) return h @main def run(): interact() Locally Deﬁned Functions A function that returns a function The name add_three is bound to a function Functions deﬁned within other function bodies are bound to names in a local frame 15 hof.py Page 2 return total def identity(k): return k def cube(k): return pow(k, 3) def summation(n, term): """Sum the ﬁrst n terms of a sequence. >>> summation(5, cube) 225 """ total, k = 0, 1 while k <= n: total, k = total + term(k), k + 1 return total def pi_term(k): return 8 / (k * 4 − 3) / (k * 4 − 1) # Local function deﬁnitions; returning functions def make_adder(n): """Return a function that takes one argument k and returns k + n. >>> add_three = make_adder(3) >>> add_three(4) 7 """ def adder(k): return k + n return adder def compose1(f, g): """Return a function that composes f and g. f, g −− functions of a single argument """ def h(x): return f(g(x)) return h @main def run(): interact() Locally Deﬁned Functions A function that returns a function A def statement within another def statement The name add_three is bound to a function Functions deﬁned within other function bodies are bound to names in a local frame 15 hof.py Page 2 return total def identity(k): return k def cube(k): return pow(k, 3) def summation(n, term): """Sum the ﬁrst n terms of a sequence. >>> summation(5, cube) 225 """ total, k = 0, 1 while k <= n: total, k = total + term(k), k + 1 return total def pi_term(k): return 8 / (k * 4 − 3) / (k * 4 − 1) # Local function deﬁnitions; returning functions def make_adder(n): """Return a function that takes one argument k and returns k + n. >>> add_three = make_adder(3) >>> add_three(4) 7 """ def adder(k): return k + n return adder def compose1(f, g): """Return a function that composes f and g. f, g −− functions of a single argument """ def h(x): return f(g(x)) return h @main def run(): interact() Locally Deﬁned Functions A function that returns a function A def statement within another def statement The name add_three is bound to a function Can refer to names in the enclosing function Functions deﬁned within other function bodies are bound to names in a local frame 15 Call Expressions as Operator Expressions 16 Call Expressions as Operator Expressions make_adder(1) ( 2 ) 16 Call Expressions as Operator Expressions make_adder(1) ( 2 ) Operator 16 Call Expressions as Operator Expressions make_adder(1) ( 2 ) Operator Operand 16 Call Expressions as Operator Expressions make_adder(1) ( 2 ) Operator Operand An expression that evaluates to a function 16 Call Expressions as Operator Expressions make_adder(1) ( 2 ) Operator Operand An expression that evaluates to a function An expression that evaluates to its argument 16 Call Expressions as Operator Expressions make_adder(1) ( 2 ) Operator Operand An expression that evaluates to a function An expression that evaluates to its argument 16 Call Expressions as Operator Expressions make_adder(1) ( 2 ) Operator Operand An expression that evaluates to a function An expression that evaluates to its argument 16 make_adder(1) Call Expressions as Operator Expressions make_adder(1) ( 2 ) Operator Operand An expression that evaluates to a function An expression that evaluates to its argument 16 make_adder(1) func make_adder(n) Call Expressions as Operator Expressions make_adder(1) ( 2 ) Operator Operand An expression that evaluates to a function An expression that evaluates to its argument 16 make_adder(1) func make_adder(n) 1 make_adder( n ): Call Expressions as Operator Expressions make_adder(1) ( 2 ) Operator Operand An expression that evaluates to a function An expression that evaluates to its argument 16 make_adder(1) func make_adder(n) 1 make_adder( n ): Call Expressions as Operator Expressions make_adder(1) ( 2 ) Operator Operand An expression that evaluates to a function An expression that evaluates to its argument 16 make_adder(1) func make_adder(n) 1 make_adder( n ): Call Expressions as Operator Expressions make_adder(1) ( 2 ) Operator Operand An expression that evaluates to a function An expression that evaluates to its argument 16 make_adder(1) func make_adder(n) 1 func adder(k) make_adder( n ): Call Expressions as Operator Expressions make_adder(1) ( 2 ) Operator Operand An expression that evaluates to a function An expression that evaluates to its argument 16 make_adder(1) func adder(k) func make_adder(n) 1 func adder(k) make_adder( n ): Call Expressions as Operator Expressions make_adder(1) ( 2 ) Operator Operand An expression that evaluates to a function An expression that evaluates to its argument 16 2 make_adder(1) func adder(k) func make_adder(n) 1 func adder(k) make_adder( n ): Call Expressions as Operator Expressions make_adder(1) ( 2 ) Operator Operand An expression that evaluates to a function An expression that evaluates to its argument 16 2 make_adder(1) func adder(k) func make_adder(n) 1 func adder(k) make_adder( n ): Call Expressions as Operator Expressions make_adder(1) ( 2 ) Operator Operand An expression that evaluates to a function An expression that evaluates to its argument 16 2 3 make_adder(1) func adder(k) func make_adder(n) 1 func adder(k)

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "I made $350 in just two days after posting my first study guide."

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.