61A Lecture 4

Wednesday, January 28
Announcements

• Homework 1 due Wednesday 1/28 at 11:59pm. Late homework is not accepted!

§ Check your submission on ok.cs61a.org and submit again if it's not right

• Take-home quiz 1 released Wednesday 1/28, due Thursday 1/29 at 11:59pm

§ Open-computer, open notes, closed friends

§ Content Covered: Lectures through Monday 1/26 (same topics as Homework 1)

§ If you receive 0/3, talk to your TA (or me) about how to approach the course

• Extra lectures: Earn 1 unit (pass/no pass) by learning about optional additional topics

§ First extra lecture: Thursday 1/29 5-6:30pm in 2050 VLSB (Come there to learn more)

• Project 1 due Thursday 2/5 at 11:59pm

2
Iteration Example
The Fibonacci Sequence

0,
1,
1,
2,
3,
5,
8,
13
,
21
,
34
,
55
,
89
,
14
4,
23
3,
def fib(n): 37
7,
"""Compute the nth Fibonacci number, for N >= 1.""" 61
0,
pred, curr = 0, 1 # Zeroth and first Fibonacci numbers 98
7
k = 1 # curr is the kth Fibonacci number
while k < n:
pred, curr = curr, pred + curr
k = k + 1
return curr The next Fibonacci number is the sum of
the current one and its predecessor

4
Discussion Question 1

What does pyramid compute?

2
n
def pyramid(n):
a, b, total = 0, n, 0
while b:
(n + 1)2 a, b = a+1, b-1
total = total + a + b
return total

2 · (n + 1)
a b
I'm still here

n2 + 1

n · (n + 1)

5
Designing Functions
Characteristics of Functions

def square(x): def fib(n):

"""Return X * X.""" """Compute the nth Fibonacci number, for N >= 1."""

A function's domain is the set of all inputs it might possibly take as arguments.

!
x is a real number n is an integer greater than or equal to 1
!

A function's range is the set of output values it might possibly return.

!
returns a non-negative returns a Fibonacci number
real number
!

A pure function's behavior is the relationship it creates between input and output.

return value is the return value is the nth Fibonacci number

square of the input

7
A Guide to Designing Function

Give each function exactly one job.

!
not
!

Don’t repeat yourself (DRY). Implement a process just once, but execute it many times.

Define functions generally.

8
Generalization
Generalizing Patterns with Arguments

Regular geometric shapes relate length and area.

Shape:
r r
r

p
3 3 2
Area: 1·r 2 ⇡ · r2 ·r
2
Finding common structure allows for shared implementation

(Demo)
10
Higher-Order Functions
Generalizing Over Computational Processes

The common structure among functions may be a computational process, rather than a number.

5
X
k =1+2+3+4+5 = 15
k=1

5
X
k 3 = 13 + 23 + 33 + 43 + 53 = 225
k=1

5
X 8 8 8 8 8 8
= + + + + = 3.04
(4k 3) · (4k 1) 3 35 99 195 323
k=1

(Demo)
12
 hof.py

return total
Summation Example
def identity(k):
return k
Function of a single argument
def cube(k): (not called "term")
return pow(k, 3)
A formal parameter that will
def summation(n, term): be bound to a function
"""Sum the first n terms of a sequence.
>>> summation(5, cube)
225
The cube function is passed
""" as an argument value
total, k = 0, 1
while k <= n:
total, k = total + term(k), k + 1
return total
The function bound to term
0 + 1 + 8 + 27 + 64 + 125
def pi_term(k): gets called here
return 8 / (k * 4 − 3) / (k * 4 − 1)
13

# Local function definitions; returning functions

def make_adder(n):
"""Return a function that takes one argument k and re
Functions as Return Values

(Demo)
 def summation(n, term):
"""Sum the first n terms of a sequence.
>>> summation(5, cube)
225
"""
total, k = 0, 1
while k <= n:
Locally Defined Functions
total, k = total + term(k), k + 1
return total
Functions defined within other function bodies are bound to names in a local frame
def pi_term(k):
return 8 / (k * 4 − 3) / (k * 4 − 1)
A function that
# Local afunction
returns function definitions; returning functions
def make_adder(n):
"""Return a function that takes one argument k and returns k + n.

>>> add_three = make_adder(3) The name add_three is bound

>>> add_three(4) to a function
7
"""
def adder(k): A def statement within
return k + n another def statement
return adder
Cang):
def compose1(f, refer to names in the
enclosing that
"""Return a function function
composes f and g.
f, g −− functions of a single argument 15
"""
def h(x):
return f(g(x))
return h
Call Expressions as Operator Expressions

An expression that An expression that

evaluates to a function evaluates to its argument

Operator Operand

3
make_adder(1) ( 2 )

func adder(k) 2
make_adder(1)

func make_adder(n) 1 make_adder( n ):

func adder(k)

16
Environments for Higher-Order Functions
Names can be Bound to Functional Arguments

Applying a user-defined function:

• Create a new frame

• Bind formal parameters
(f & x) to arguments
• Execute the body:
return f(f(x))

18
Interactive Diagram
Discussion Question

What is the value of the final expression below? (Demo)

def repeat(f, x):

while f(x) != x:
x = f(x)
return x
!
def g(y):
return (y + 5) // 3
!
result = repeat(g, 5)

If you think
there's an error

19
Interactive Diagram