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 step-by-step:

Step #

number

total

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.

The reduction algorithm

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 #

number

output

start

0

1

1

1

2

23

24

3

46

70

4

92

162

5

9

171

6

12

183

7

5

188

last

26.857142857

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 filtering algorithm

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 #

number

number < 20

output

start

[]

1

1

True

[1]

2

23

False

[1]

3

46

False

[1]

4

92

False

[1]

5

9

True

[1, 9]

6

12

True

[1, 9, 12]

7

5

True

[1, 9, 12, 5]

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.

The mapping algorithm

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 #

number

output

start

[]

1

1

[2]

2

23

[2, 46]

3

46

[2, 46, 92]

4

92

[2, 46, 92 184]

5

9

[2, 46, 92, 184, 18]

6

12

[2, 46, 92, 184, 18, 24]

7

5

[2, 46, 92, 184, 18, 24, 10]

[ ]:

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 #

number

output

start

False

1

1

False

2

23

True

3

46

True

4

92

True

5

9

True

6

12

True

7

5

True

last

True

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 #

number

output

start

False

1

1

False

2

23

True

last

True

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:

[ ]: