We've encountered two ways to alter flow of control. The first was a function call. The second was iteration. However we don't yet have a way to make decisions - to decide whether a block of code will be executed. That power is called selection. I will now give you this power.
Selection requires evaluation of a new type of expression, a type whose value is a Boolean. So let us begin with Booleans.
We've seen four data types - int, float, str and list. Now we add a fifth, the Boolean type. Python's name for it is bool.
Class bool is tiny. It has only two members, True and False. (Notice the capitalization.) Let's prove to ourselves that Python does actually know True and False:
>>> True
True
>>> False
False
>>> type(True)
<class 'bool'>
>>> type(False)
<class 'bool'>
Expressions that yield Booleans are built from operators of two types - comparison operators and logical operators. (Remember that an operator is a function placed between its arguments.)
Python has a number of comparison operators: these take a pair of comparable objects and return a Boolean. (When are objects comparable? Python's answer will surprise you, but we'll put that off.) Let's have a list of them. Below I give name and then symbol.
Equality: ==
Inequality: !=
Greater Than: >
Greater Than or Equal: >=
Less Than: <
Less Than or Equal: <=
As I said, these take a pair of comparable objects and return a Boolean. Watch.
>>> 1 == 1
True
>>> 1 == 2
False
>>> 1 != 1
False
>>> 1 != 2
True
>>> 1 > 2
False
>>> 1 < 2
True
>>> 1 <= 1
True
>>> 1 >= 1
True
We can build more complex expressions if we like; we can insert variables into them too. Python works here as it always does - substitute in values of sub-expressions and then proceed.
>>> a = 12
>>> b = a * 12
>>> c = a + 12
>>> a == a
True
>>> a != a
False
>>> b > c
True
>>> c < a
False
>>> a + b - c >= a - b + c
True
Consider the last. We first substitute for the variables to get: 12 + 144 - 24 >= 12 - 144 + 24. This then becomes 132 >= -108. The value of this True.
Comparison operators take comparable objects and produce Booleans. Logical operators take Booleans and produce Booleans. We have three: and, or and not. Here's their logic. Assume that p and q are Boolean-valued expressions.
p and q is True when and only when both p and q are True; otherwise it's False.
p or q is False when and only when both p and q are False; otherwise it's True. Alternatively: p or q is True when one or both of p and q are True; otherwise it's False.
not p is False when p is True and True when p is False.
To the console we go:
>>> True and True
True
>>> True and False
False
>>> False and True
False
>>> False and False
False
>>> True or True
True
>>> True or False
True
>>> False or True
True
>>> False or False
False
>>> not True
False
>>> not False
True
As always, Python allows us to build up more complex expressions from simpler ones. Proceed as before - replace sub-expressions with their values until nothing is left that can be simplified. An example:
>>> False or not(True and False)
Let's figure out the value for ourselves. First do the True and False in parentheses. That has the value False. So we simplify the original expression to False or not False. The not False at the end is True, so next we simplify to False or True. This is True.
Note that not takes precedence over and or or. Thus not a and b means the same as (not a) and b. If we wished to negate last, we should use not (a and b). and and or have equal precedence.
Let's combine comparison and logical operators together in a few super-Booleans. Really you should find them quite intuitive.
>>> 1 > 2 or 2 < 1
False
>>> 1 > 2 or 2 > 1
True
>>> 1 > 2 and 2 > 1
False
>>> not(1 > 2 and 2 > 1)
True
>>> a, b, c = 3, 4, 5
>>> not(a**2 + b**2 == c**2)
False
(I snuck something in, something new. It's the line a, b, c = 3, 4, 5. Yes, this is possible. We can assign values to multiple variables on a single line. Order matters of course. The first variable on the left gets the first value on the right, the second variable on the left gets the second value on the right, etc. We'll have more to say about this later.)
What's the purpose of Booleans? One answer: decide whether to execute a block of code. I think it best to show you the code first. After I'll analyze.
1. def abs_val(n):
2. if n < 0:
3. n = n * -1
4. return n
We see here a new keyword, the keyword if. How does it work? It's really very simple: if the Boolean that follows the if has the value True, execute the indented block of code underneath; otherwise skip that block and continue on. For example, if n has the value -12, the Boolean expression n < 0 is True, and so we execute the indented block that consists of line 3; this mean that n's sign is changed. But if n were for example 3, the Boolean expression n < 0 would be False and we'd skip to line 4 and return the value 3.
A few test runs:
>>> abs_val(0)
0
>>> abs_val(1)
1
>>> abs_val(-2)
2
For sure if is powerful. It allows us to decide whether to execute a block of code. But what if we wanted to decide which among a number of blocks of code to execute? Python's gotcha covered (as it almost always does). What we need is the if-elif-else structure. (The "elif" is short for "else if".)
Here's an example of an if-elif-else block.
def letter_grade(num_grade):
# return the letter grade associated with a given numerical grade
if num_grade >= 100:
grade = 'A+'
elif num_grade >= 90:
grade = 'A'
elif num_grade >= 80:
grade = 'B'
elif num_grade >= 70:
grade = 'C'
elif num_grade >= 60:
grade = 'D'
else:
grade = 'F'
return grade
We first test the condition after the if. If True, grade is assigned 'A+' and the rest of the if-elif-else block is skipped. If False, we then test the condition after the first elif. If True, grade is assigned 'A' and the rest of the if-elif-else block is skipped. We continue in this way until either we find an elif condition that's True, or all are False; and if all are False, we automatically execute the else block.
(You might have wondered why for the 'B' range, we checked only whether the grade was greater than or equal to 80. Shouldn't we check whether it's less than 90 too? The answer is that we'll get to the num_grade >= 80 check only if the checks above - num_grade >= 100 and num_grade >= 90 - both fail. So if we check whether num_grade is greater than or equal to 80, we'll already know that it's not 90 or above.)
This is the logic of if-elif-else. Search through the if and subsequent elifs for a True; execute the sub-block of code under the first that's True and then skip the rest of the if-elif-else block. If no if or elif is True, execute the else sub-block.
Note that if we wish we can have just an if and an else. Or just an if and some number of elifs. Like this:
def letter_grade(num_grade):
if num_grade >= 90:
return 'A'
else:
return 'F'
What an ogre this teacher is! Either you get an A or you fail.
Here's if and elif, but no else:
def letter_grade(num_grade):
if num_grade >= 70:
return 'pass'
elif num_grade < 70:
return 'fail'
The course is apparently pass-fail. (You see, don't you, that this last code snippet could be done with just if and else? If the numeric grade isn't greater than or equal to 70, it's automatically less than 70. So we didn't really need to do the < 70 check. We could have put return 'fail' under else.)
Remember how we could have iterated iteration? (That was a for loop inside another for loop.) Well, we can also have selected selection; that is, we can have selection inside an indented block of code that itself is part of some selection block. Like this. (We have our ogre again. If you don't get an A+ or an A, you fail.)
def letter_grade(num_grade):
if num_grade >= 90:
if num_grade >= 100:
grade = 'A+'
else:
grade = 'A'
else:
grade = 'F'
return grade
How does this work? Let's think it through. Let's say num_grade get's the value 101. We then evaluate num_grade > 90. That's True. So we execute the block of intended code immediately below. That means we immediately evaluate a second Boolean expression, namely num_grade >= 100. That's True too. So grade is then given the value 'A+'.
What if num_grade had been 98? Well, the test num_grade > 90 would be True, so we'd then test whether num_grad >= 100. That's now False, so we'd drop down to the associated else and grade would be the value 'A'.
If find this intensely cool! Indented blocks of code can be whatever we like. They can be iteration. They can be selection. So there can be iteration inside of iteration. And selection inside selection. And iteration inside selection. And selection inside iteration. And selection inside iteration inside selection. Etc. The possibilities are endless!
The selection of the previous section was stacked; that is, we had selection inside selection. We could have done it with flat selection. Like this:
def letter_grade(num_grade):
if num_grade >= 100:
grade = 'A+'
elif grade >= 90:
grade = 'A'
else:
grade = 'F'
return grade
Which do you prefer? The flat version is shorter - seven lines of code in the body instead of eight. But honestly I prefer the longer version. It makes clearer that really we have two possibilities - A (whether A+ or just plain A) or F.
Let's do another example where we can either have our selection stacked or flat. I have in mind a pointless little game. We'll send a function a list of integers, and we'll score that list in this way:
A negative value decreases the score by 1.
A zero increases the score by 4 .
A positive that's even increases the score by 2.
A positive that's odd increases the score by 1.
Stacked Solution:
def score(L):
score = 0
for n in L:
if n < 0:
score -= 1
elif n == 0:
score += 4
else:
if n % 2 == 0:
score += 2
else:
score += 1
(See the n % 2 == 0? In English that's: the remainder when divided by 2 is 0. That's True when n is even, False when it's odd.)
Flat Solution:
def score(L):
score = 0
for n in L:
if n < 0:
score -= 1
elif n == 0:
score += 4
elif n % 2 == 0:
score += 2
else:
score += 1
(Note that the second elif could have been elif n > 0 and n % 2 == 0. But the n > 0 isn't necessary. If we reach the second elif, we already know that n > 0.)
Again I find the stacked version easier to follow. It makes clear that we really have three possibilities here - negative, zero and positive; and it makes clear that in the positive range, we distinguish the odds from the evens. But of course you'll make your own judgment. Just know that there are many ways to get the logic right.
The subject of the last chapter was for-type iteration - "definite iteration" we called it. Python has a second type of iteration, the while-type. Iteration of this sort is indefinite. Typically we don't know at the start how many times we'll loop.
Our syntax here is:
while <Boolean expression>:
<body>
The while body iterates until the Boolean expression is False.
Here's a pointless but illustrative task. Write a function that, for a given positive integer n, determines how many odd perfect squares are less than or equal to n. Now perhaps there's some clever way to compute this directly. But I don't feel clever at the moment. So let's just generate perfect squares in succession, count as we do, and continue on until our perfect squares exceeds n.
1. def perf_squares(n):
2. count = 0
3. curr_odd = 1
4. while curr_odd ** 2 <= n:
5. count = count + 1
6. curr_odd = curr_odd + 2
7. return count
Let's follow it out if perf_squares is sent a value of 25.
count and curr_odd are initialized to 0 and 1 respectively.
Next we encounter the line that begins with a while. Python evaluates the Boolean expression that follows - curr_odd ** 2 <= n. It's True, since curr_odd ** 2 is 1 and n is 25.
Since the Boolean is true, we execute the body of the while loop. That's lines 5 and 6. count becomes 1 and curr_odd becomes 3.
After lines 5 and 6 are done, we loop back up to line 4 and check the Boolean again. curr_odd ** 2 is now 9 and n is still 25. So we execute the body again.
count becomes 2 and curr_odd becomes 5.
Again we loop back to line 4. The Boolean is true again - 25 is indeed less than or equal to 25. So we execute the body a third time.
count becomes 3 and curr_odd becomes 6.
Back we go to line 4. Now the Boolean is false - curr_odd ** 2 is 36 and 36 is not less than or equal to 25.
Since the while's Boolean is false, we skip the body of the while loop and arrive at line 7. So we return a value of 4.
Here's a wild claim: anything you can do with a for loop you can do with a while loop, but some things you can do with a while loop you cannot do with a for loop.
Let me prove the second claim first. It's really very simple. All it takes is one little two-line program.
while True:
print("spam and eggs")
Think about that first line. The first time we hit it, Python asks, "Does the Boolean after the while have the value True?" The answer? Of course! True is True! We then do the body. When the body is done, we go back to the while line and ask if it's Boolean is true. Well, True is still True. Indeed True will always be True. So we have right here an infinite loop, a loop that never stops. But no for loop goes on forever. Thus while can do something for cannot.
Now for the first claim, which again was that anything a for loop can do a while loop can do. I think an example will convince you of this. Let's have a task. We'll sum up the squares of the first n positive integers. Here's a function with a for loop that does that.
def sum_squares(n):
s = 0 # the sum
for i in range(1, n + 1):
s += i ** 2 # equivalent to s = s + i ** 2
return s
Now here's a while loop that does the same. Note that we need to initialize and increment a variable that holds the number to be squared.
def sum_squares2(n):
s = 0 # the sum
i = 1 # the integer whose square will be added to s
while i <= n:
s += i ** 2
i += 1 # increment the value of i by 1; equivalent to i = i + 1
return s
See what we did? We handled the loop variable ourselves. We initialized it. We incremented it. We kept on until it reached a certain value. You can always do this in a while loop.
Before we move on to Boolean valued functions, let me show you another way to write the while loop of sum_squares2. It makes use of a new keyword.
def sum_squares3(n):
s = 0 # the sum
i = 1 # the integers whose square will be added to s
while True:
s += i ** 2
i += 1
if i > n:
break
return s
You see it, I'm sure. The new keyword break. It stops the while loop dead in its tracks. That's what break always does, even if we don't have while True, even if we have a for loop. It stops the loop. If any of the loop body is below it, it won't be executed; and we won't enter the loop body again. (Note that if we have a loop inside a loop, break stops only the one nearest to it. It doesn't stop them all.)
We've seen examples of the use of Booleans to pick which code block (if any) gets executed. That's their primary use for sure. But it's often very convenient to write functions that return a Boolean.
Here's out task: write a function that takes as input a positive integer and returns True if it's even and False if it's not. Such a function is Boolean valued - the value that it returns is a Boolean. We'll have three versions - good, better, best.
First the good.
def is_even(n):
if n % 2 == 0:
return True
elif n % 2 != 0:
return False
Why only good? If the n % 2 == 0 check fails, we don't need to check whether n % 2 isn't 0; if the n % 2 == 0 checks fails, we already know that n % 2 isn't 0. So all we really need is an else, not a second elif. This leads to the better.
def is_even(n):
if n % 2 == 0:
return True
else:
return False
Why only better? Well, take a look at the best and I'm sure you'll agree that it's better than the better.
def is_even(n):
return n % 2 == 0
You understand, right? n % 2 == 0 is itself a Boolean! So if we return it, a Boolean is returned - True if n is divisible by 2, False if it's not. Now that's slick!
Now let's use that Boolean-valued function. Here's our task: take a positive integer n and return double n if n is even and thrice n plus 1 if it's not. (I'll call this function "collatz" for a reason that will become clear in the function set for the chapter.)
Fine
def collatz(n):
if is_even(n) == True:
result = 2 * n
if is_even(n) == False:
result = 3 * n + 1
return result
This is fine. It works. But we don't really need the second if. If the condition of the first if fails, we should automatically triple and add 1. That means else. So we have ...
Slightly Better
def collatz(n):
if is_even(n) == True:
result = 2 * n
else:
result = 3 * n + 1
return result
But we can economize even more! is_even returns a Boolean. So if_even(n) is by itself perfectly acceptable after the if. Remember: the value of a function is the value it returns! So we have ...
More Better
def collatz(n):
if is_even(n):
result = 2 * n
else:
result = 3 * n + 1
return result
But we're still not to Best. We can give another squeeze and make the function shorter still. How ? Ditch the variable result. Instead just return when we know what to return; whenever a function hits a return, that function is over, no matter where or when that return is hit. This give us ...
Even More Better
def collatz(n):
if is_even(n):
return 2 * n
else:
return 3 * n + 1
One more squeeze and we'll get to Best. Squeeze how? Drop the else. Like this ...
Best
def collatz(n):
if is_even(n):
return 2 * n
return 3 * n + 1
If n is even, then we return 2 * n and the function is complete. (As I said, a function always ends with it hits a return.) Thus we can get to the return 3 * n + 1 only if n isn't even. So we don't need the else! Now that's some pretty code! Very short. Very clear.
In the Chapter 2 function set, I had you consider an efficient cashier. This is the cashier who, when he makes change, gives you the fewest coins possible. If for instance the change is 99 cents, he will give that to you as 3 quarters, 2 dimes and 4 pennies. Now let's consider a related problem. I now want us to count the total number of ways that change could be given if we use only pennies, nickels, dimes and quarters. This, it would seem, calls for iteration, indeed for iterated iteration.
Below I give a solution to the problem and then refine that solution in a number of ways. (In Chapter 8, where the topic is recursion, I'll have you generalize the solution. There the function I'll have you write will take as input the coin values to use.) We don't often worry about program efficiency; for the most part, that's beyond the scope of Think Functional!. But now and again, we will consider ways that we might make a program more efficient. We'll find in this case that we can make it massively more efficient. Know that, if you pursue computer science, the topic of program efficiency will become absolutely central. We often need not just some solution or other, but one that's fast enough to run in reasonable time (however precisely "reasonable" is defined). If you're curious about the topic, you might start here.
In each solution below, I have four total for loops - one for pennies, one for nickels, one for dimes and one for quarters. In Solution One, the least efficient, I produce every possible penny, nickel, dime and quarter total where the total value of any one coin type is less than or equal to the change that must be made; I then test and accept only those total values that equal the change to make. For instance, for a change value of 100, Solution One would produce, but not count, a total created from 57 pennies, 9 nickels, 3 dimes and 2 quarters. Note that I keep two totals, total_count and correct_count. total_count is the total number of coin combinations produced, and correct_count is the number from total_count that actually give the correct change.
# Solution One
def coin_counts_US(change):
# Return the number of combinations of coins that will
# sum up to the value of change.
# Assume the common US coin values - 1, 5, 10 and 25 cents.
# Assume that change will be given in cents.
total_count = 0
correct_count = 0
coin_total = 0
for pennies in range(0, change + 1, 1):
coin_total = pennies
for nickels in range(0, change + 1, 5):
coin_total = pennies + nickels
for dimes in range(0, change + 1, 10):
coin_total = pennies + nickels + dimes
for quarters in range(0, change + 1, 25):
coin_total = pennies + nickels + dimes + quarters
total_count += 1
if coin_total == change:
correct_count += 1
return total_count, correct_count
Note how I produced coin values of the desired amount. I did so with an appropriate step value.
Here are some test runs of Solution One. Keep in mind that the first value in each pair is the total number of coin combinations produced and the second is the number of those that give the correct change.
>>> coin_counts_US(1)
(2, 1)
>>> coin_counts_US(10)
(66, 4)
>>> coin_counts_US(50)
(10098, 49)
>>> coin_counts_US(100)
(116655, 242)
total_count grows very, very quickly, and correct_count much, much more slowly! We should really want to do better than this. That total_count number should be brought down.
Let me show you a way. My idea is to check the value of coin_total at every point it's computed and, when it exceeds change, stop the loop in which that total was computed. How does one do that? With the break command. When asked to break, Python will stop the innermost loop - either for or while - that contains that break. (Here's a link to the official docs on the break command.) Look at this:
# Solution Two
def coin_counts_US(change):
# Return the number of combinations of coins that will
# sum up to the value of change.
# Assume the common US coin values - 1, 5, 10 and 25 cents.
# Assume that change will be given in cents.
total_count = 0
correct_count = 0
coin_total = 0
for pennies in range(0, change + 1, 1):
coin_total = pennies
for nickels in range(0, change + 1, 5):
coin_total = pennies + nickels
if coin_total > change:
break
for dimes in range(0, change + 1, 10):
coin_total = pennies + nickels + dimes
if coin_total > change:
break
for quarters in range(0, change + 1, 25):
coin_total = pennies + nickels + dimes + quarters
if coin_total > change:
break
total_count += 1
if coin_total == change:
correct_count += 1
return total_count, correct_count
After every line that computes a new value for coin_total, we check whether that total is over change, and if it is, we stop the loop. So, for instance, if the value of pennies is 93 and the value of nickels is 10, we break the nickels loop. That's great! We don't do any more nickels, and since we don't do any more nickels, we don't do any dimes or quarters, since the dimes and quarters loops are in the body of the nickels loop.
Look at see how much less work we do:
>>> coin_counts_US(1)
(2, 1)
>>> coin_counts_US(10)
(19, 4)
>>> coin_counts_US(50)
(784, 49)
>>> coin_counts_US(100)
(6962, 242)
That's fantastic! To get the 242 total ways for an input of 100, we considered just 6962 possibilities, not 116655.
But though that's a fantastic gain in efficiency, we can do even better. Indeed we can produce only those coin combinations that give the desired change. I'll show you and then say a few words about how it works.
# Solution Three
def coin_counts_US(change):
# Return the number of combinations of coins that will
# sum up to the value of change.
# Assume the common US coin values - 1, 5, 10 and 25 cents.
# Assume that change will be given in cents.
count = 0
for quarters in range(0, change // 25 + 1):
change -= quarters * 25
for dimes in range(0, change // 10 + 1):
change -= dimes * 10
for nickels in range(0, change // 5 + 1):
count += 1
change += dimes * 10
change += quarters * 25
return count
The big change made in Solution Three is that we no longer begin with pennies and then go up. Instead we begin at quarters and work and then go down. Note too that we decrease the amount of change to be made for each coin we add to a collection; for instance, if we add a quarter, we reduce the change to make by a quarter. This means that, we get to the next coin, it will typically iterate through fewer values. (This means too that in the last line of a loop, we must add back in the coin amount previously subtracted. For instance, the last line of the quarters loop is change += quarters * 25.)
Note also that we no longer need a pennies loop. Why not? Once we've generated the nickels part of the collection, all that's left of change must automatically be pennies. There's no need to have the code generate pennies when we already know how many pennies there must be.
Last note: we no longer have two count variables. Now we have just one. The reason is that every coin collection we generate is guaranteed to give the correct change! But for sake of completeness, here are the outputs:
>>> coin_counts_US(1)
1
>>> coin_counts_US(10)
4
>>> coin_counts_US(50)
49
>>> coin_counts_US(100)
242