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

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

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):
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: