Loop Algorithms¶
The for
loop has simple syntax with powerful implications. If you’re learning to program for the first time it’s important for you to be able to step through the for
loop one iteration at a time as a way to understand what it does. The debugger is really great for this! Here’s an example with each iteration of the loop spelled out in a table:
This for
loops calculates the sum of every number in a list:
numbers = [1, 23, 46, 92, 9, 12, 5]
total = 0
for number in numbers:
total = total + number
print(total)
Let’s look at the value of number
and total
stepbystep:
Step # 



0 
0 

1 
1 
1 
2 
23 
24 
3 
46 
70 
4 
92 
162 
5 
9 
171 
6 
12 
183 
7 
5 
188 
Now enter the code and confirm those steps in the debugger:
[ ]:
Reduction¶
A reduction algorithm takes a squence of values and generates a single value from them. Finding the sum of all the numbers in a list, their average or the minimum value are examples of reduction algorithms.
A reduction algorithm start by initializing an output variable. Durint each step of the for
loop, the output variable is updated with a new value. After the for
loop is complete a reduction algorithm can optionally process or adjust the output variable. Here’s an example of an algorihtm that calculates the average of all the numbers in a list:
def average(numbers):
output = 0 # Initialize the output variable
for number in numbers:
output = output + number # Update the output variable
output = output / len(numbers) # Adjust the final value
return output
Let’s simulate in our heads what calling the average
function like this does:
average([1, 23, 46, 92, 9, 12, 5])
For ever step we write out the value of our variables:
Step # 



start 


1 


2 


3 


4 


5 


6 


7 


last 

Enter the example code into the next cell and run it in the debugger:
[ ]:
Filtering¶
A filtering algorithm creates a squence that only contains the desireable values from an input sequence.
The output value of a filtering algorithm is a list that’s initially empty. Each time through the for
loop a filtering algorithm uses an if
statement to see if the current value is desirable. If it is, it appends the current value to the output. Here’s an example of a filtering algorithm that filters out numbers greater than or equal to 20:
def less_than_20(numbers):
output = [] # An empty list
for number in numbers:
if number < 20:
output.append(number) # Add the desireable element
return output # Return the filtered list
Let’s simulate in our head what the less_than_20
function does:
less_than_20([1, 23, 46, 92, 9, 12, 5])
Notice that the if
is inside the for
. Simulating the loop in a table gives us:
Step # 




start 


1 



2 



3 



4 



5 



6 



7 



Now enter the example and use the debugger to confirm our thinking:
[ ]:
Mapping¶
A mapping algorithm applies an operation to every element in a squence, creating a new sequence.
Mapping algorithms start with an empty output and append a new value to it every time through the for
loop. The value that’s appended has the operation applied. Here’s an example that doubles each value in an input list to produce an output list:
def double_list(numbers):
output = [] # Start with an empty output
for number in numbers:
output.append(number * 2) # Apply the operation to every element.
return output
Let’s simulate what the double_list
function does:
double_list([1, 23, 46, 92, 9, 12, 5])
Simulating the loop in a table gives us:
Step # 



start 


1 


2 


3 


4 


5 


6 


7 


[ ]:
Example: Searching for a Value¶
Sometimes you want to find something in the list. Of course, this is conveniently done with the in
operator in Python but let’s see it in a for
loop. A search algorithm is a reduction algorithm because it takes a sequence as input and returns a single value, True
or False
. Let’s take a look at a simplistic search:
def search(value, numbers):
output = False
for number in numbers:
if number == value:
output = True
return output
Let’s simulate the algorithm with this input:
search(23, [1, 23, 46, 92, 9, 12, 5])
Step # 



start 


1 


2 


3 


4 


5 


6 


7 


last 

This algorithim is wasteful because it kept looking after it had already found 23
. An algorithm that searches a sequence shold stop when it has found what it’s looking for. The break
statement stops a for loop from executing, leaving any remaining items unseen. Here’s an algorithm that searches for a number in the list:
def search(value, numbers):
output = False
for number in numbers:
if number == value:
output = True
break
return output
Running break
stops the loop early. Here’s a simulation:
Step # 



start 


1 


2 


last 

Note: Programming Style
The break statement is controversial. Some people discourage its use because they believe that it makes code less readable, or harder to simulate in your head. As you gain experience you’ll be able to judge for yourself how readable and clear code is. Every statement has a time and a place.
Let’s rewrite search
without the break
:
def search(value, numbers):
for number in numbers:
if number == value:
return True
return False
Enter the example and confirm the simulation in the debugger:
[ ]: