CS61A Lab 1b: Higher Order Functions

Week 1b, Summer 2013

Exercise 1: Higher Order Functions

Higher order functions are functions that take a function as an input, and/or output a function. We will be exploring many applications of higher order functions. For each question, try to determine what Python would print. Then check in the interactive interpreter to see if you got the right answer.

>>> def square(x):
...     return x*x

>>> def neg(f, x):
...     return -f(x)

# Q1
>>> neg(square, 4)
_______________
>>> def first(x):
...	    x += 8
...	    def second(y):
...	        print('second')
...	        return x + y
...	    print('first')
...	    return second
...
# Q2
>>> f = first(15)
_______________
# Q3
>>> f(16)
_______________

>>> def foo(x):
...	    def bar(y):
...	        return x + y
...	    return bar

>>> boom = foo(23)
# Q4
>>> boom(42)
_______________
# Q5
>>> foo(6)(7)
_______________

>>> func = boom
# Q6
>>> func is boom
_______________
>>> func = foo(23)
# Q7
>>> func is boom
_______________
>>> def troy():
...     abed = 0
...     while abed < 10:
...         def britta():
...             return abed
...         abed += 1
...     abed = 20
...     return britta
...
>>> annie = troy()
>>> def shirley():
...     return annie
>>> pierce = shirley()
# Q8
>>> pierce()
________________

We recommend you try typing these statements into the interpreter.

1) -16
2) first
3) second
   39
4) 65
5) 13
6) True
7) False
8) 20

Exercise 2: Returning Functions

In your Hog project, you will have to work with strategies and functions that make strategies. Let's start by defining what a strategy is: a function that takes two arguments (your score and the opponent's score) and returns the number of dice to roll. The following is a strategy function that always rolls 5 dice, and is the computer's default strategy:

def default_strategy(score, op_score):
    return 5

A strategy maker is a function that defines a strategy within its body, and returns the resulting strategy. We'll define a strategy maker that returns the default strategy:

def make_default_strategy():
    def default_strategy(score, op_score):
        return 5
    return default_strategy

Of course, a strategy that doesn't adapt to the situation is not a strategy at all! Implement a strategy maker called make_weird_strategy that will take one argument called num_rolls. The strategy it returns will return the higher of num_rolls or the total number of points scored in the game thus far divided by 20, throwing away any remainder.

def make_weird_strategy(num_rolls):
    "*** YOUR CODE HERE ***"

def make_weird_strategy(num_rolls):
    def weird_strategy(score, op_score):
        return max(num_rolls, (score+op_score)//20)
    return weird_strategy

Obviously, this isn't a practical strategy, but exemplifies how a strategy maker is written. How can you write a better strategy maker? In your project, consider the rules of Hog as well as the situations in which it may be beneficial to roll more or less dice.

Exercise 3: I Heard You Liked Functions So I Put Functions In Your Functions

Define a function cycle which takes in three functions as arguments: f1, f2, f3. cycle will then return another function. The returned function should take in an integer argument n and do the following:

Return a function that takes in an argument x and does the following:
1. if n is 0, just return x
2. if n is 1, apply the first function that is passed to cycle to x
3. if n is 2, the first function passed to cycle is applied to x, and then the second function passed to cycle is applied to the result of that (i.e. f2(f1(x)))
4. if n is 3, apply the first, then the second, then the third function (i.e. f3(f2(f1(x))))
5. if n is 4, apply the first, then the second, then the third, then the first function (i.e. f1(f3(f2(f1(x)))))
6. And so forth

Hint: most of the work goes inside the most nested function.

def cycle(f1, f2, f3):
    """ Returns a function that is itself a higher order function
    >>> def add1(x):
    ...     return x + 1
    ...
    >>> def times2(x):
    ...     return x * 2
    ...
    >>> def add3(x):
    ...     return x + 3
    ...
    >>> my_cycle = cycle(add1, times2, add3)
    >>> identity = my_cycle(0)
    >>> identity(5)
    5
    >>> add_one_then_double = my_cycle(2)
    >>> add_one_then_double(1)
    4
    >>> do_all_functions = my_cycle(3)
    >>> do_all_functions(2)
    9
    >>> do_more_than_a_cycle = my_cycle(4)
    >>> do_more_than_a_cycle(2)
    10
    >>> do_two_cycles = my_cycle(6)
    >>> do_two_cycles(1)
    19
    """

    "*** YOUR CODE HERE ***"


def cycle(f1, f2, f3):
     def ret_fn(n):
         def ret(x):
             i = 0
             while i < n:
                 if i % 3 == 0:
                     x = f1(x)
                 elif i % 3 == 1:
                     x = f2(x)
                 else:
                     x = f3(x)
                 i += 1
             return x
         return ret
     return ret_fn

Exercise 4: Environment Diagrams

Try drawing environment diagrams for the following examples and predicting what Python will output:

# Q1
def square(x):
    return x * x

def double(x):
    return x + x

a = square(double(4))


# Q2
x, y = 4, 3

def reassign(arg1, arg2):
    x = arg1
    y = arg2

reassign(5, 6)


# Q3
def f(x):
    f(x)

print, f = f, print
a = f(4)
b = print(4)

# Q4
def adder_maker(x):
    def adder(y):
        return x + y
    return adder

add3 = adder_maker(3)
add3(4)
sub5 = adder_maker(-5)
sub5(6)
sub5(10) == add3(2)


    
    
      
      
Q1:
 

Q2:
 

Q3:
 

Q4:
 
    
      
    
    
 Fin.