Lab 2: Lists, List Comprehension and Iteration
Due at 11:59:59 pm on 02/06/2024.
Starter Files
Download lab02.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the OK autograder.
Introduction
In the last lab, you learned some basic expressions and wrote some python code. In this lab, we will introduce lists and take a look at how they can be used.
Lists
If you are taking or have taken Data 8, you are likely familiar with Tables
. Tables are an extremely useful and powerful data type. In CS88 we will work with other data types. Python provides
several important built-in data types that we can build from. So far, you have met numberical data types (ints, floats, and booleans) and one sequence type (strings). Lists, tuples, and dictionaries are other sequence data types in Python. Here, we will take a closer look at lists. A list can contain a sequence of values of any type.
You can create a list just by placing the values, separated by commas, within square brackets. Here are some examples. As you will see in one of the examples, lists can contain other lists.
>>> [1,2,3]
[1, 2, 3]
>>> ["frog", 3, 3.1415]
['frog', 3, 3.1415]
>>> [True, [1, 2], 42]
[True, [1, 2], 42]
Open up your python interpreter and create some lists of your own.
You learned last week that what really makes a data type useful is the operations that you can
perform on it. What can you do with lists?
>>> x = [1,2,3] # assign them to variables
>>> len(x) # get their length, i.e., the number of elements in them
3
>>> x + [4,5] # + is concatenation
[1, 2, 3, 4, 5]
>>> [1,2] * 3 # * is replication
[1, 2, 1, 2, 1, 2]
>>> len([1,2] * 3)
6
>>> [1,2] * [3,4] # what's this?
TypeError: can't multiply sequence by non-int of type 'list'
The in
operator is very useful when working with lists. It operates on the entire list and produces a boolean that answers the question, "Is this item in the list?".
>>> 2 in [1,2,3]
True
>>> "frog" in [1,2,3]
False
>>> [1,2] in [1,2,3]
False
>>> [1,2] in [[1,2],3]
True
List Comprehensions
List comprehensions are a compact and powerful way of creating new lists out of sequences. Let's work with them directly:
>>> [i**2 for i in [1, 2, 3, 4] if i%2 == 0]
[4, 16]
is equivalent to
>>> lst = []
>>> for i in [1, 2, 3, 4]:
... if i % 2 == 0:
... lst += [i**2]
>>> lst
[4, 16]
The general syntax for a list comprehension is
[<expression> for <element> in <sequence> if <conditional>]
The syntax is designed to read like English: "Compute the expression for each element in the sequence if the conditional is true."
Introduction to 'Map', 'Filter', and 'Reduce'
Map
Higher order functions fit into a domain of programming known as "functional" or "functional form" programming, centered around this idea of passing and returning functions as parameters and arguments. In class, you learned the command map
that is a fundamental example of higher order functions.
Let's take a closer look at how map
works. At its core, map
applies a function to all items in an input list. It takes in a function as the first parameter and a series of inputs as the second parameter.
map(function_to_apply, list_of_inputs)
A potentially easier way to think about map
is to draw an equivalent with a list comprehension! Given the func
(function to apply) and inputs
(list of inputs), a map is similar to this:
[func(x) for x in inputs]
Keep in mind that the map
function actually returns a map
object, not a list. We need to convert this object to a list
by passing it into the list()
function.
Let's do a Python Tutor example to understand how map works.
Open Python Tutor in a new tab.
This code should already be there:
INCR = 2
def inc(x):
return x+INCR
def mymap(fun, seq):
return [fun(x) for x in seq]
result = mymap(inc, [5, 6, 7])
print(result)
So what's happening here? In the first 3 lines, we're defining a function inc
which increments an input x
by a certain amount, INCR
.
Notice that INCR
is defined once in the Global frame. This is a nice review of how Python resolves references when there are both local and global variables. When the inc
method executes, python needs to find the value INCR
. Since the INCR
variable isn't declared locally, within the inc
function, Python will look at the parent frame, the frame in which inc
was declared, for the value of INCR
. In this case, since the inc
function was declared in the Global frame, the global INC
variable value will be used.
The second function, mymap
, is an example of how map works in the form of a list comprehension! Notice that mymap
takes in a function as its first argument and a sequence as its second. Just like map
, this list comprehension runs each element of seq
through the fun
method.
As you run through the program in Python Tutor, notice how the list comprehension in mymap
will repeatedly call the inc
function. The functional anatomy of how map
works is exactly encapsulated by the mymap
function.
Filter
The filter
keyword is similar in nature to map
with a very important distinction. In map
, the function we pass in is being applied to every item in our sequence. In filter
, the function we pass in filters the elements, only leaving the elements for which the function returns true. For example, if I wanted to remove all negative numbers from a list, I could use the filter
function to identify values that are greater than or equal to 0, and filter out the rest.
def isPositive(number):
return number >= 0
numbers = [-1, 1, -2, 2, -3, 3, -4, 4]
positive_nums = list(filter(isPositive, numbers))
Again, similar to map
, the output of the filter
function is a filter
object, not a list, so you need to call list()
. The equivalent for filter in the form of a list comprehension would look something along the lines of this:
positive_nums = [number for number in numbers if isPositive(number)]
Reduce
Reduce
takes in three different parameters: A function, a sequence, and an identity. The function and sequence are the same parameters that we saw in map
and filter
. The identity can be thought of as the container where you are going to store all of your results. In the above case, the identity would be the product
variable.
Reduce
is very useful for performing computations on lists that involve every element in the list. Computations are performed in a rolling fashion, where the function acts upon each element one at a time.
Let's say I wanted to calculate the product of the square roots of a list of numbers. The non-reduce
version of this code would look something along the lines of this:
product = 1
numbers = [4, 9, 16, 25, 36]
for num in numbers:
product = product * num**.5
Here's the reduce
version
multiplicative_identity = 1
nums = [4, 9, 16, 25, 36]
def sqrtProd(x, y):
return x * y ** .5
reduce(sqrtProd, nums, multiplicative_identity)
Required Problems
Coding Practice
Question 1: Classify the elements
Complete the function odd_even
that returns 'odd'
if the given integer x
is odd, and returns 'even'
otherwise.
Additionally, complete another function classify
that takes in a list s
and returns a new list
that applies odd_even
to all elements in s
.
def odd_even(x):
"""Classify a number as odd or even.
>>> odd_even(4)
'even'
>>> odd_even(3)
'odd'
"""
"*** YOUR CODE HERE ***"
if (x % 2) == 0:
return 'even'
else:
return 'odd'
def classify(s):
"""
Classify all the elements of a sequence as odd or even
>>> classify([0, 1, 2, 4])
['even', 'odd', 'even', 'even']
"""
"*** YOUR CODE HERE ***"
return [odd_even(x) for x in s]
Use OK to test your code:
python3 ok -q odd_even
Use OK to test your code:
python3 ok -q classify
Question 2: Find first word longer than n
Complete the function find_word
that takes in a list words
and returns the first word with a length greater than n
. If none of the words have length greater than n
, return the empty string ''
.
def find_word(words, n):
"""
>>> find_word(["cat", "window", "zookeeper"], 5)
'window'
>>> find_word(["cat", "dog", "fish"], 3)
'fish'
>>> find_word(["cat", "dog", "bro"], 3)
''
>>> find_word(["python", "java", "SQL"], 4)
'python'
"""
"*** YOUR CODE HERE ***"
for word in words:
if len(word) > n:
return word
return ''
Use OK to test your code:
python3 ok -q find_word
Question 3: If this not that
Define if_this_not_that
, which takes a list of integers i_list
, and an
integer this
, and for each element in i_list
if the element is larger than
this
then print the element, otherwise print that
.
def if_this_not_that(i_list, this):
"""
>>> original_list = [1, 2, 3, 4, 5]
>>> if_this_not_that(original_list, 3)
that
that
that
4
5
"""
"*** YOUR CODE HERE ***"
for elem in i_list:
if elem <= this:
print("that")
else:
print(elem)
Use OK to test your code:
python3 ok -q if_this_not_that
Question 4: Shuffle
Define a function shuffle
that takes a sequence with an even number of
elements (cards) and creates a new list that interleaves the elements
of the first half with the elements of the second half.
Let's better understand what it means to shuffle a list in this way. Let's say there is some list [1, 2, 3, 4, 5, 6, 7, 8]
. To interleave the first half [1, 2, 3, 4]
with the second half [5, 6, 7, 8]
means that your final list should contain the first element from the first half, then the first element from the second half, then the second element of the first half, then the second element of the second half and so on.
So the interleaved version of [1, 2, 3, 4, 5, 6, 7, 8]
would be
[1, 5, 2, 6, 3, 7, 4, 8]
.
def shuffle(cards):
"""Return a shuffled list that interleaves the two halves of cards.
>>> lst = [1, 2, 3, 4, 5, 6, 7, 8]
>>> shuffle(lst)
[1, 5, 2, 6, 3, 7, 4, 8]
>>> shuffle(range(6))
[0, 3, 1, 4, 2, 5]
>>> cards = ['AH', '1H', '2H', '3H', 'AD', '1D', '2D', '3D']
>>> shuffle(cards)
['AH', 'AD', '1H', '1D', '2H', '2D', '3H', '3D']
>>> cards # should not be changed
['AH', '1H', '2H', '3H', 'AD', '1D', '2D', '3D']
"""
assert len(cards) % 2 == 0, 'len(cards) must be even'
"*** YOUR CODE HERE ***"
half = len(cards) // 2
shuffled = []
for i in range(half):
shuffled.append(cards[i])
shuffled.append(cards[half+i])
return shuffled
Use OK to test your code:
python3 ok -q shuffle
Question 5: Perfect Pairs
Implement the function pairs
, which takes in an integer n
,
and returns a new list of lists which contains pairs of numbers from 1 to n
.
Use a list comprehension.
def pairs(n):
"""Returns a new list containing two element lists from values 1 to n
>>> pairs(1)
[[1, 1]]
>>> x = pairs(2)
>>> x
[[1, 1], [2, 2]]
>>> pairs(5)
[[1, 1], [2, 2], [3, 3], [4, 4], [5, 5]]
>>> pairs(-1)
[]
"""
"*** YOUR CODE HERE ***"
return [[i, i] for i in range(1, n + 1)]
Use OK to test your code:
python3 ok -q pairs
Question 6: Coordinates
Implement a function coords
, which takes a function, a sequence, and
an upper and lower bound on output of the function. coords
then
returns a list of x, y coordinate pairs (lists) such that:
- Each pair contains
[x, fn(x)]
- The x coordinates are the elements in the sequence
- Only pairs whose y coordinate is within the upper and lower bounds (inclusive)
See the doctests for examples.
One other thing: your answer can only be one line long. You should make use of list comprehensions!
def coords(fn, seq, lower, upper):
"""
>>> seq = [-4, -2, 0, 1, 3]
>>> def fn(x):
... return x**2
>>> coords(fn, seq, 1, 9)
[[-2, 4], [1, 1], [3, 9]]
"""
"*** YOUR CODE HERE ***"
return [[x, fn(x)] for x in seq if lower <= fn(x) and f(x) <= upper]
Use OK to test your code:
python3 ok -q coords
Submission
When you are done, submit your file to Gradescope. You only need to upload the following files:
lab02.py