# Lab 3: List Comprehensions, Conditionals and Iteration.

*Due at 9:00pm on 09/20/2018.*

## Starter Files

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

## Submission

When you are done, submit the lab by uploading the `lab03.py`

file to okpy.org. You may submit more than once before the
deadline; only the final submission will be graded.

- All questions for this lab are required. To submit the assignment, upload lab03.py to Okpy.org.

Last lab, we went over how to use python tutor to help us visualize the execution of python code. Let's do another example to review the concept of scopes for variables and nesting for functions.

## Scopes and Nested Functions

Letâ€™s see what nested function calls look like in the python interpreter.

Paste this code into the interpreter or follow this link Ex1

```
def bonus(score):
previousScore = score
multiplier = 1
if score > 25:
multiplier = 2
score *= multiplier
return score
print(bonus(score))
print(previousScore)
```

Now step through the code. Why does it error out? The error message reads

`NameError: name 'previousScore' is not defined`

But didn't we define `previousScore`

in the body of the `bonus`

function? We did, but that `previousScore`

is only defined in the scope of the function. So it is not accessible outside in the global scope.

Let's try another function Ex2

```
def totalScore(score):
multiplier = 2
def bonus(score):
if score > 25:
score *= multiplier
else:
score /= multiplier
return score
return score, bonus(score)
score = 12
totalScore(score)
print(score)
```

There's a lot to unpack here. We purposefully gave the variables the same names so you can see how python lookups values for variables. The general principle is that python looks for the value in the current scope first. If it can't find the variable there, it checks it's parent scope, and the parent's parent, all the way up to the global scope. If the variable still isn't found there, an error is raised. Walk through the lookup for multiplier on line 7 in your head as a sanity check.

## List Comprehensions

Now that we can create lists, assign variables, write expressions, and
define functions, we can compose these concepts to do lots of interesting
things. Python's `list comprehensions`

open a beautiful of data-centric
programming.

The comprehension is in brackets, just like a list, but rather than a static
sequence of literals, it is a dynamically computed list.

```
>>> somelist = [1, 2, 9, -1, 0]
>>> [x+1 for x in somelist]
[2, 3, 10, 0, 1]
>>> [x*x for x in somelist]
[1, 4, 81, 1, 0]
```

In general, the expression just inside the `[`

is evaluated for each element
in the list, using the variable between the `for`

and the `in`

to name each
element in succession. The result is the transformed list.

```
>>> def square(x):
... return x*x
...
>>> def squares(s):
... return [square(x) for x in s]
...
>>> squares([0,1,2,4])
[0, 1, 4, 16]
>>>x, y = 2, 3
>>> x+y
5
>>> [x+y for x,y in [(1,2), (2,3), (3,4)]]
[3, 5, 7]
```

This is a powerful design pattern, called `map`

, that you will use in often
in analyzing data. It *maps*, or transforms, one data structure into another
under some expression, often by applying a function to each of the elements.

Do you remember the Table.apply( ) function from Data 8? The Table.apply function is another great example of the `map`

design pattern as it applies a "transformation" or a function to a row or column.

Sometimes you need a sequence to get started, and Python provides handy tools
for that. One of them is `range`

.

```
>>> [x*x for x in range(10)]
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
```

You can review `range`

in Section 2.3
of Composing Programs.

### Question 1: Shopping - Tax

Let's write a function that transforms a `shopping cart`

, which we will represent as a list of 3 element tuples, by adding a specified `percent`

tax to the price of each item. We will then compute the cost of all our items including tax.

Shopping carts are represented like this:

`[(item1, cost1, quantity1), (item2, cost2, quantity2), ..., (itemN, costN, quantityN)]`

Implement `tax(shopping_cart, percent)`

and `sum(shopping_cart)`

so you can figure out how much you have to pay for all of your items.

```
def tax(shopping_cart, percent):
"""
Adds a `percent` tax to each item's price in a shopping cart.
>>> fruitCart = [("apple", 0.5, 3), ("banana", 0.25, 4)]
>>> tax(fruitCart, 10)
[('apple', 0.55, 3), ('banana', 0.275, 4)]
>>> calCart = [("oski", 1000, 1), ("go", 1, 2), ("bears", 3.5, 2)]
>>> tax(calCart, 100)
[('oski', 2000.0, 1), ('go', 2.0, 2), ('bears', 7.0, 2)]
"""
"*** YOUR CODE HERE ***"
return ______
taxMultiplier = 1 + (percent / 100)
return [(name, price * taxMultiplier, quantity) for (name, price, quantity) in shopping_cart]
```

Use OK to test your code:

`python3 ok -q tax --local`

### Question 2: Shopping - Cart Sum

```
def cartSum(shopping_cart):
"""
Sums a shopping cart
>>> fruitCart = [("apple", 0.5, 3), ("banana", 0.25, 4)]
>>> taxedFruit = tax(fruitCart, 10)
>>> cartSum(taxedFruit)
2.75
>>> calCart = [("oski", 1000, 1), ("go", 1, 2), ("bears", 3.5, 2)]
>>> taxedCal = tax(calCart, 100)
>>> cartSum(taxedCal)
2018.0
"""
"*** YOUR CODE HERE ***"
return ______
return sum([price*quantity for (name, price, quantity) in shopping_cart])
```

Use OK to test your code:

`python3 ok -q cartSum --local`

## Conditionals

You can review the syntax and behavior of `if`

statements in
Section 1.5.4
of Composing Programs.

The `conditional statement`

is a statement, not an expression; it does
not return a value. The `if-expression`

(or predicate) is evaluated
first, before any other part of the statement, to determine whether to
evaluate an `arm`

. If the `if-expression`

evaluates to a True value
then the statement(s) following the `:`

is evaluate. Otherwise, the
`else arm`

is evaluated, if present. Multiple predicates can be
chained together with `elif`

. They are evaluated sequentially. Often
conditionals are often used along with return statements in functions. For example,
in some census data you see in c8 you might want to decode the gender code.

```
def decode_gender(code):
if (code == 0):
return 'all'
elif (code == 1):
return 'male'
elif (code == 2):
return 'female'
else:
return 'unknown'
```

Conditionals are often used with assignment statements to simplify later expressions.

```
if ((year % 4) == 0) and (((year % 100) != 0) or ((year % 400) == 0)):
year_len = 366
else:
year_len = 365
<do something with year_len>
```

Or with print statements to control output

```
if (scene == 'architect skit'):
print("spam, spam, spam")
else
print("nobody expects the Spanish inquisition")
```

### Omitting the else

Consider the following function:

```
def abs(x):
if x >= 0:
return x
else:
return -x
```

It is correct to rewrite `abs`

in the following way:

```
def abs(x):
if x >= 0:
return x
return -x
```

This is a direct consequence of how `return`

works — when
Python sees a `return`

statement, it will *immediately terminate* the
function, and the rest of the function will not be evaluated. In the
above example, if `x >= 0`

, Python will never reach the final line.
Try to convince yourself that this is indeed the case before moving on.

Keep in mind that **omitting the else only works if the function is
terminated**! For example, the following function will

*always*print "less than zero", because the function is not terminated in the body of the

`if`

suite:```
>>> def foo(x):
... if x > 0:
... print("greater than zero")
... print("less than zero")
...
>>> foo(-3)
less than zero
>>> foo(4)
greater than zero
less than zero
```

In general, omitting the `else`

will make your code more concise —
however, if you find that it makes your code harder to read, by all
means use an `else`

statement.

### Question 3: Where Above

Lets use list comprehensions to implement some of the filters we could apply in Data 8's `table.where()`

function.
In particular, fill in the `where_above`

function that returns a list that filters out any elements less than or equal to `limit`

.
Try to do this in only one line.

```
def where_above(list, limit):
"""
where_above behaves like table.where(column, are.above(limit)).
The analogy is completed if you think of a column of a table as a list and return the filtered column instead of the entire table.
>>> where_above([1, 2, 3], 2)
[3]
>>> where_above(range(13), 10)
[11, 12]
>>> where_above(range(123), 120)
[121, 122]
"""
"*** YOUR CODE HERE ***"
return ______
return [n for n in list if n > limit]
```

Use OK to test your code:

`python3 ok -q where_above --local`

## Iteration: For loops

You might remember for loops from simulations in Data 8. A for loop can be constructed by using the for statement. Typically, the for statement is used to iterate through a sequence, such as a list, and perform some computing on each iteration. Here is an example:

```
def sum(s):
"""
Return the sum of the elements in the sequence, s.
>>> sum([1, 2, 3])
6
"""
total = 0
for number in s: # for each element in the sequence
total = total + number # accumulate it into the partial sum
return total # the final partial sum is the total sum
```

The line `total = total + number`

is called an accumulation statement. This statement is so common that it has a special shorthand notation.

`total += number`

### Question 4: Minmax

In c8 you often need to understand the spread of data. Write a simple function to find the minimum and maximum elements in a sequence using a for loop.

```
def minmax(s):
"""Return the minimum and maximum elements of a sequence.
>>> minmax([1, 2, -3])
(-3, 2)
>>> minmax([2])
(2, 2)
>>> minmax([])
(None, None)
"""
"*** YOUR CODE HERE ***"
return ______
mn, mx = None, None
for x in s:
if mn is None or x < mn:
mn = x
if mx is None or x > mx:
mx = x
return mn, mx
```

Use OK to test your code:

`python3 ok -q minmax --local`

## Iteration: While loops

Python also has a more basic iteration construct that is closely
related to conditionals, the `while`

loop. It does not make any
assumption of iterating through a sequence. It iterates until a
predicate is satisfied.

You can review the syntax of `while`

loops in
Section 1.5.5
of Composing Programs.

Typically, some state will be established before the while loop. The predicate will compute a boolean expression involving that state. And the body of the loop will advance the state, thereby iterating until the predicate is satisfied.

### Question 5: Closest Power of 2

Let's test out our knowledge by making a function that finds the largest power of 2 that is less than a given number. Fill in the function `closest_power_2`

below to return the closest power of 2 using a while loop.

```
def closest_power_2(x):
""" Returns the closest power of 2 that is less than x
>>> closest_power_2(6)
4
>>> closest_power_2(32)
16
>>> closest_power_2(87)
64
>>> closest_power_2(4095)
2048
>>> closest_power_2(524290)
524288
"""
"*** YOUR CODE HERE ***"
return ______
exponent = 0
while x > (2 ** (exponent + 1)):
exponent += 1
return 2 ** exponent
```

Use OK to test your code:

`python3 ok -q closest_power_2 --local`

Here's some food for thought: What mathematical operation is closely related to finding the closest power of 2? It's the logarithm! (at least with a base of 2) By keeping track of which power of 2 you are on, you can compute rounded down version of log base 2 of numbers using your `closest_power_2`

function. If this stuff is cool to you, you should check out CS61C, particularly the sections on binary representations of data, and bitwise operators.