# Introduction

In the last lab, you learned about higher order functions and environments. In this lab, we will introduce lists and take a look at how they can be used.

# Lists

In Data 8, you have recently started working 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
```

# 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)
```

# Problems

### Question 1: Classify the elements

Complete the function `odd_even`

that classifies an number as either `'odd'`

or `'even'`

and the function `classify`

that takes in a list and applies `odd_even`

to all elements in the list.

```
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: 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 3: 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 card(n):
"""Return the playing card numeral as a string for a positive n <= 13."""
assert type(n) == int and n > 0 and n <= 13, "Bad card n"
specials = {1: 'A', 11: 'J', 12: 'Q', 13: 'K'}
return specials.get(n, str(n))
def shuffle(cards):
"""Return a shuffled list that interleaves the two halves of cards.
>>> shuffle(range(6))
[0, 3, 1, 4, 2, 5]
>>> suits = ['♡', '♢', '♤', '♧']
>>> cards = [card(n) + suit for n in range(1,14) for suit in suits]
>>> cards[:12]
['A♡', 'A♢', 'A♤', 'A♧', '2♡', '2♢', '2♤', '2♧', '3♡', '3♢', '3♤', '3♧']
>>> cards[26:30]
['7♤', '7♧', '8♡', '8♢']
>>> shuffle(cards)[:12]
['A♡', '7♤', 'A♢', '7♧', 'A♤', '8♡', 'A♧', '8♢', '2♡', '8♤', '2♢', '8♧']
>>> shuffle(shuffle(cards))[:12]
['A♡', '4♢', '7♤', '10♧', 'A♢', '4♤', '7♧', 'J♡', 'A♤', '4♧', '8♡', 'J♢']
>>> cards[:12] # Should not be changed
['A♡', 'A♢', 'A♤', 'A♧', '2♡', '2♢', '2♤', '2♧', '3♡', '3♢', '3♤', '3♧']
"""
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`

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."

### Question 4: 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 5: Deck of cards

Write a list comprehension that will create a deck of cards, given a
list of `suits`

and a list of `numbers`

. Each
element in the list will be a card, which is represented by a 2-element list
of the form `[suit, number]`

.

```
def deck(suits, numbers):
"""Creates a deck of cards (a list of 2-element lists) with the given
suits and numbers. Each element in the returned list should be of the form
[suit, number].
>>> deck(['S', 'C'], [1, 2, 3])
[['S', 1], ['S', 2], ['S', 3], ['C', 1], ['C', 2], ['C', 3]]
>>> deck(['S', 'C'], [3, 2, 1])
[['S', 3], ['S', 2], ['S', 1], ['C', 3], ['C', 2], ['C', 1]]
>>> deck([], [3, 2, 1])
[]
>>> deck(['S', 'C'], [])
[]
"""
"*** YOUR CODE HERE ***"
return [[suit, number] for suit in suits
for number in numbers]
```

Use OK to test your code:

`python3 ok -q deck`

## Required Practice Problems Open in a new window

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

You should answer the questions on the study tool, and once you are completed with the required problems on the tool for that week, you will receive an okpy secret key that you will need to submit to show completion of the practice problems on the tool. Copy paste that secret key into the `lab03_practice_problems`

function at the bottom, along with your okpy email in the first line. Then, to test that you've correctly completed the problem, you can run the following command.

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 Questions

### Question 6: Trade

In the integer market, each participant has a list of positive integers to trade. When two participants meet, they trade the smallest non-empty prefix of their list of integers. A prefix is a slice that starts at index 0.

Write a function `trade`

that exchanges the first `m`

elements of list `first`

with the first `n`

elements of list `second`

, such that the sums of those
elements are equal, and the sum is as small as possible. If no such prefix
exists, return the string `'No deal!'`

and do not change either list. Otherwise
change both lists and return `'Deal!'`

.

Some code is provided that needs to be edited, but other code is needed as well.

```
def trade(first, second):
"""Exchange the smallest prefixes of first and second that have equal sum.
>>> a = [1, 1, 3, 2, 1, 1, 4]
>>> b = [4, 3, 2, 7]
>>> trade(a, b) # Trades 1+1+3+2=7 for 4+3=7
'Deal!'
>>> a
[4, 3, 1, 1, 4]
>>> b
[1, 1, 3, 2, 2, 7]
>>> c = [3, 3, 2, 4, 1]
>>> trade(b, c)
'No deal!'
>>> b
[1, 1, 3, 2, 2, 7]
>>> c
[3, 3, 2, 4, 1]
>>> trade(a, c)
'Deal!'
>>> a
[3, 3, 2, 1, 4]
>>> b
[1, 1, 3, 2, 2, 7]
>>> c
[4, 3, 1, 4, 1]
"""
m, n = 1, 1
"*** YOUR CODE HERE ***"
equal_prefix = lambda: sum(first[:m]) == sum(second[:n])
while m < len(first) and n < len(second) and not equal_prefix():
if sum(first[:m]) < sum(second[:n]):
m += 1
else:
n += 1
if False: # change this line!
if equal_prefix(): first[:m], second[:n] = second[:n], first[:m]
return 'Deal!'
else:
return 'No deal!'
```

Use OK to test your code:

`python3 ok -q trade`