Lab 4: Lambdas, Dictionaries, and ADTs
Due at 11:59:59 pm on 2/23/2020.

Starter Files

Download lab04.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the OK autograder.

Submission

By the end of this lab, you should have submitted the lab with python3 ok --submit. You may submit more than once before the deadline; only the final submission will be graded. Check that you have successfully submitted your code on okpy.org. See this article for more instructions on okpy and submitting assignments.

• To receive full credit for this lab, all questions must be attempted.

When you are ready to submit, run ok with the --submit option:

python3 ok --submit

After submitting, ok will display a submission URL, with which you can view your submission on okpy.org.

Lambda

Lambda expressions are one-line functions that specify two things: the parameters and the return value.

lambda <parameters>: <return value>

While both lambda and def statements are related to functions, there are some differences.

lambda x: x * x
           

def square(x):
    return x * x

A lambda expression by itself is not very interesting. As with any objects such as numbers, booleans, strings, we usually:

• assign lambda to variables (foo = lambda x: x)
• pass them in to other functions (bar(lambda x: x))
• return them as the results of other functions (return lambda x: x)
• return them as the results of other lambdas (lambda x: lambda y: x + y)

In the final example above, the outer lambda (lambda x) takes in a value x, and it returns another lambda (lambda y) that takes an argument y and returns x+y.

Environment Diagrams

Environment diagrams are one of the best learning tools for understanding lambda expressions because you're able to keep track of all the different names, function objects, and arguments to functions. We highly recommend drawing environment diagrams or using Python tutor if you get stuck doing the WWPD problems below. For examples of what environment diagrams should look like, try running some code in Python tutor. Here are the rules:

Lambdas

Note: As we saw in the lambda expression section above, lambda functions have no intrinsic name. When drawing lambda functions in environment diagrams, they are labeled with the name lambda or with the lowercase Greek letter λ. This can get confusing when there are multiple lambda functions in an environment diagram, so you can distinguish them by numbering them or by writing the line number on which they were defined.

1. Draw the lambda function object and label it with λ, its formal parameters, and its parent frame. A function's parent frame is the frame in which the function was defined.

This is the only step. We are including this section to emphasize the fact that the difference between lambda expressions and def statements is that lambda expressions do not create any new bindings in the environment.

WWPD

Question 1: WWPD: Lambda the Free

Use Ok to test your knowledge with the following "What Would Python Display?" questions:

python3 ok -q lambda -u

For all WWPD questions, type Function if you believe the answer is <function...>, Error if it errors, and Nothing if nothing is displayed. As a reminder, the following two lines of code will not display anything in the Python interpreter when executed:

>>> x = None
>>> x

>>> lambda x: x  # A lambda expression with one parameter x
______
<function <lambda> at ...>
>>> a = lambda x: x  # Assigning the lambda function to the name a
>>> a(5)
______
5
>>> (lambda: 3)()  # Using a lambda expression as an operator in a call exp.
______
3
>>> b = lambda x: lambda: x  # Lambdas can return other lambdas!
>>> c = b(88)
>>> c
______
<function <lambda> at ...
>>> c()
______
88
>>> d = lambda f: f(4)  # They can have functions as arguments as well.
>>> def square(x):
...     return x * x
>>> d(square)
______
16

>>> z = 3
>>> e = lambda x: lambda y: lambda: x + y + z
>>> e(0)(1)()
______
4
>>> f = lambda z: x + z
>>> f(3)
______
NameError: name 'x' is not defined

>>> higher_order_lambda = lambda f: lambda x: f(x)
>>> g = lambda x: x * x
>>> higher_order_lambda(2)(g)  # Which argument belongs to which function call?
______
Error
>>> higher_order_lambda(g)(2)
______
4
>>> call_thrice = lambda f: lambda x: f(f(f(x)))
>>> call_thrice(lambda y: y + 1)(0)
______
3
>>> print_lambda = lambda z: print(z)  # When is the return expression of a lambda expression executed?
>>> print_lambda
______
Function
>>> one_thousand = print_lambda(1000)
______
1000
>>> one_thousand
______
# print_lambda returned None, so nothing gets displayed

Lambda

Question 2: Compose

Write a function that takes in 2 single-argument functions, f and g, and returns another lambda function that takes in a single argument x. The returned function should return the output of applying f(g(x)).

Hint: The staff solution is only 1 line!

def compose(f, g):
    """Write a function that takes in 2 single-argument functions, f and g, and returns another lambda function 
    that takes in a single argument x. The returned function should return the output of applying f(g(x)). 
    Hint: The staff solution is only 1 line!

    Return the composition function which given x, computes f(g(x)). 

    >>> add_two = lambda x: x + 2  		# adds 2 to x
    >>> square = lambda x: x ** 2 		# squares x
    >>> a = compose(square, add_two) 	# (x + 2 ) ^ 2
    >>> a(5) 
    49
    >>> mul_ten = lambda x: x * 10 		# multiplies 10 with x
    >>> b = compose(mul_ten, a) 		# ((x + 2 ) ^ 2) * 10
    >>> b(5)
    490
    >>> b(2)
    160
    """
    "*** YOUR CODE HERE ***"
    
    return lambda x: f(g(x))

Use OK to test your code:

python3 ok -q compose

Question 3: Mul_by_num

Using a lambda expression, complete the mul_by_num function. This function should take an argument and return a one argument function that multiplies any value passed to it by the original number. Its body must be one line long:

def mul_by_num(num):
    """
    Returns a function that takes one argument and returns num
    times that argument.
    >>> x = mul_by_num(5)
    >>> y = mul_by_num(2)
    >>> x(3)
    15
    >>> y(-4)
    -8
    """
    "*** YOUR CODE HERE ***"
    
    return lambda num2: num * num2

Use OK to test your code:

python3 ok -q mul_by_num

Abstract Data Types

Data abstraction is a powerful concept in computer science that allows programmers to treat code as objects --- for example, car objects, chair objects, people objects, etc. That way, programmers don't have to worry about how code is implemented --- they just have to know what it does.

Data abstraction mimics how we think about the world. For example, when you want to drive a car, you don't need to know how the engine was built or what kind of material the tires are made of. You just have to know how to turn the wheel and press the gas pedal.

An abstract data type consists of two types of functions:

• Constructors: functions that build the abstract data type.
• Selectors: functions that retrieve information from the data type.

For example, say we have an abstract data type called city. This city object will hold the city's name, and its latitude and longitude. To create a city object, you'd use a constructor like

city = make_city(name, lat, lon)

To extract the information of a city object, you would use the selectors like

get_name(city)
get_lat(city)
get_lon(city)

For example, here is how we would use the make_city constructor to create a city object to represent Berkeley and the selectors to access its information.

>>> berkeley = make_city('Berkeley', 122, 37)
>>> get_name(berkeley)
'Berkeley'
>>> get_lat(berkeley)
122
>>> get_lon(berkeley)
37

Notice that we don't need to know how these functions were implemented. We are assuming that someone else has defined them for us.

It's okay if the end user doesn't know how functions were implemented. However, the functions still have to be defined by someone. We'll look into defining the constructors and selectors later in this discussion.

Question 4: Distance

We will now use those selectors to write distance, which computes the distance between two city objects. Recall that the distance between two coordinate pairs, (x1, y1) and (x2, y2) can be found by calculating the sqrt of (x1 - x2)**2 + (y1 - y2)**2. We have already imported sqrt for your convenience, so use that and the appropriate selectors to fill in the function.

from math import sqrt
def distance(city_1, city_2):
    """
    >>> city1 = make_city('city1', 0, 1)
    >>> city2 = make_city('city2', 0, 2)
    >>> distance(city1, city2)
    1.0
    """

    "*** YOUR CODE HERE ***"
    
    lat_1, lon_1 = get_lat(city_1), get_lon(city_1)
    lat_2, lon_2 = get_lat(city_2), get_lon(city_2)
    return sqrt((lat_1 - lat_2)**2 + (lon_1 - lon_2)**2)

Use OK to test your code:

python3 ok -q distance

Question 5: Closer city

Implement closer_city, a function that takes a latitude, longitude, and two cities, and returns the name of the city that is relatively closer to the provided latitude and longitude.

You may only use selectors and constructors (introduced above) for this question. You may also use the distance function defined above. Remember, the point of data abstraction, as we've said, is that we do not need to know how an abstract data type is implemented, but rather just how we can interact with and use the data type.

def closer_city(lat, lon, city1, city2):
    """ Returns the name of either city1 or city2, whichever is closest
        to coordinate (lat, lon).

        >>> berkeley = make_city('Berkeley', 37.87, 112.26)
        >>> stanford = make_city('Stanford', 34.05, 118.25)
        >>> closer_city(38.33, 121.44, berkeley, stanford)
        'Stanford'
        >>> bucharest = make_city('Bucharest', 44.43, 26.10)
        >>> vienna = make_city('Vienna', 48.20, 16.37)
        >>> closer_city(41.29, 174.78, bucharest, vienna)
        'Bucharest'
    """
    "*** YOUR CODE HERE ***"
    return <REPLACE THIS>
    new_city = make_city('arb', lat, lon)
    dist1 = distance(city1, new_city)
    dist2 = distance(city2, new_city)
    if dist1 < dist2:
         return get_name(city1)
    return get_name(city2)

Use OK to test your code:

python3 ok -q closer_city

Question 6: Closer City Abstraction

Run the following ok test to make sure that you are using abstraction barriers correctly! You should not need to change your code from the previous question to pass this test.

Use OK to test your code:

python3 ok -q check_abstraction

Dictionaries

You've actually seen several abstract data types! List, tuples, ranges, and even strings are examples of abstract data types. Dictionary is another example of abstract data types.

Dictionaries are unordered sets of key-value pairs. To create a dictionary, use the following syntax:

>>> singers = { 'Iggy Azalea': 'Fancy', 'Beyonce': 'Flawless', 'Adam Levine': 'Maps'}

The curly braces denote the key-value pairs in your dictionary. Each key-value pair is separated by a comma. For each pair, the key appears to the left of the colon and the value appears to the right of the colon. (This is a dictionary's constructor!) You can retrieve values from your dictionary by "indexing" using the key:

>>> singers['Beyonce']
'Flawless'
>>> singers['Iggy Azalea']
'Fancy'

You can update an entry for an existing key in the dictionary using the following syntax. What this means is that each key is unique. Be careful, adding a new key follows identical syntax!

>>> singers['Beyonce'] = 'Survivor'
>>> singers['Beyonce']
'Survivor'
>>> singers['Nicki Minaj'] = 'Anaconda' # new entry!
>>> singers['Nicki Minaj']
'Anaconda'

You can also check for membership of keys!

>>> 'Adam Levine' in singers
True

Recall how we can iterate through a list using for-loops. For example, you can do something like this:

>>> a = [1,2,3]
>>> for each in a:
...     print(each)
1
2
3

What happens if you iterate through a dictionary? Can you even iterate through a dictionary?? Notice what happens:

>>> shopping_cart = {"apple":3, "bananas":4, "orange":6}
>>> for each in shopping_cart:
...     print(each)
apple
bananas
orange

Notice that when you iterate through a dictionary, the set of keys is what you iterate through. How would you print out values instead? You can simply do:

>>> shopping_cart = {"apple":3, "bananas":4, "orange":6}
>>> for each in shopping_cart:
...     print(shopping_cart[each])
3
4
5

Question 7: Counter

Implement the function counter which takes in a string of words, and returns a dictionary where each key is a word in the message, and each value is the number of times that word is present in the original string.

def counter(message):
    """ Returns a dictionary of each word in message mapped
    to the number of times it appears in the input string.

    >>> x = counter('to be or not to be')
    >>> x['to']
    2
    >>> x['be']
    2
    >>> x['not']
    1
    >>> y = counter('run forrest run')
    >>> y['run']
    2
    >>> y['forrest']
    1
    """
    word_list = message.split()
    "*** YOUR CODE HERE ***"
    
    result_dict = {}
    for word in word_list:
        if word in result_dict:
            result_dict[word] += 1
        else:
            result_dict[word] = 1
    return result_dict

Use OK to test your code:

python3 ok -q counter

Required Practice ProblemsOpen in a new window

These questions are a mix of Parsons Problems, Code Tracing questions, and Code Writing questions.

Confused about how to use the tool? Check out https://codestyle.herokuapp.com/cs88/lab01 for some problems designed to demonstrate how to solve these types of problems.

These cover some similar material to lab, so can be helpful to further review or try to learn the material. Unlike lab and homework, after you've worked for long enough and tested your code enough times on any of these questions, you'll have the option to view an instructor solution. You'll unlock each question one at a time, either by correctly answering the previous question or by viewing an instructor solution.

Use OK to test your code:

python3 ok -q practice_problems

Submit

Make sure to submit this assignment by running:

python3 ok --submit

Optional: Environment Diagram Practice

There is no submission for this component. However, we still encourage you to do these problems on paper to develop familiarity with Environment Diagrams, which will appear on the exam.

Question 8: Make Adder

Draw the environment diagram for the following code:

n = 9
def make_adder(n):
    return lambda k: k + n
add_ten = make_adder(n+1)
result = add_ten(n)

There are 3 frames total (including the Global frame). In addition, consider the following questions:

1. In the Global frame, the name add_ten points to a function object. What is the intrinsic name of that function object, and what frame is its parent?
2. In frame f2, what name is the frame labeled with (add_ten or λ)? Which frame is the parent of f2?
3. What value is the variable result bound to in the Global frame?

Question 9: Lambda the Environment Diagram

Try drawing an environment diagram for the following code and predict what Python will output.

You do not need to submit or unlock this question through Ok. Instead, you can check your work with the Online Python Tutor, but try drawing it yourself first!

>>> a = lambda x: x * 2 + 1
>>> def b(b, x):
...     return b(x + a(x))
>>> x = 3
>>> b(a, x)
______
21 # Interactive solution: https://goo.gl/Lu99QR