Contents |

Loops are used to repeatedly execute some code. The most
basic loop structure in Python is the *while* loop, an example of
which is:

i = 0 while (i < 10): print(i,end="") i = i + 1

We see a `while` loop looks much like an `if`
statement.
The difference
is that blocks belonging to `if`s are evaluated at most once whereas
blocks associated with loops may be evaluated many many times.
Another difference in nomenclature is that the block of a loop
is known as the *body* (like blocks associated with function
definitions). Furthermore, the loop test expression is known
as the *loop condition*.

As Computer Scientists hate to type extra characters if they can help it, you will often see:

i = i + 1

written as

i += 1

The latter version is read as "increment *i*" and
saves a whopping two characters of typing.

A *while* loop tests its condition before the body of the loop is
executed. If the initial test fails, the body is not executed at all. For
example:

i = 10 while (i < 10): print(i,end="") i += 1

never prints out anything since the test immediately fails. In this example, however:

i = 0; while (i < 10): print(i,end="") i += 1

the loop prints out the digits 0 through 9:

0123456789

A `while` loop repeatedly evaluates its body
as long as the loop condition remains true.

To write an infinite loop, use `True` as the condition:

while (True): i = getInput() print("input is",i) process(i)

There are many kinds of loops in Python, in this text
we will only refer to `while` loops and `for`
loops that count,
as these are commonly found in other programming languages.
The `while` loop we have seen; here is an example of a counting
`for` loop:

for i in range(0,10,1): print(i)

This loop is exactly equivalent to:

i = 0 while (i < 10): print(i) i += 1

In fact, a while loop of the general form:

i = INIT while (i < LIMIT): # body ... i += STEP

can be written as a counting `for`

loop:

for i in range(INIT,LIMIT,STEP): # body ...

The *range* function counts from
`INIT` to `LIMIT` (non-inclusive)
by `STEP` and these
values are assigned
to *i*, in turn. After each assignment to *i*,
the loop body is evaluated.
After the last value is assigned to *i* and the
loop body evaluated on last time, the `for`

loop ends.

In Python, the *range* function assumes 1 for the step
if the step is omitted and assumes 0 for the initial
value and 1 for the step if both the initial value and
step are omitted.
However, in this text, we will always give the initial
value and step of the `for`

loop explicitly.

For loops are commonly used to sweep through each element of an array:

for i in range(0,len(items),1): print(items[i])

Recall the items in an array of *n* elements are located at
indices *0* through *n - 1*. These are exactly the values
produced by the *range* function. So, this loop accesses
each element, by its index, in turn, and thus prints out
each element, in turn.
Since using an index of *n* in an array of *n* items produces an
error, the *range* function conveniently makes its given
limit non-inclusive.

As stated earlier, there are other kinds of loops in
Python, some of which, at times, are more convenient
to use than a `while` loop or a counting `for` loop. However,
anything that can be done with those other loops can be
done with the loops presented here.
Loops and arrays go very well
together;
the next sections detail some common loop patterns involving
arrays.

The counting pattern is used to count the number of items
in a collection. Note that the built-in function *len* already
does this for Python arrays, so counting the elements in an array
is a bit of a waste of time.
Still, it is about the easiest loop to write, so let's forge ahead^{20}:

count = 0 for i in range(0,len(items),1): count += 1

When the loop finishes, the variable *count* holds the number of
items in the array.
In general, the counting pattern increments a counter every time the loop
body is evaluated.

A variation on the counting pattern involves filtering. When *filtering*,
we use an `if` statement to decide whether we should count an item
or not. Suppose we wish to count the number of even items in
an array:

count = 0 for i in range(0,len(items),1): if (items[i] % 2 == 0): count += 1

When this loop terminates, the variable *count* will hold the
number of even integers in the array of items. The `if`

makes sure
the count
is incremented only when the item of interest is even.

Similar to the counting pattern, the *accumulate* pattern
updates a variable, not by increasing its value by one, but by the value of
an item. This loop, sums all the values in an array:

total = 0 for i in range(0,len(items),1): total += items[i]

By convention, the variable *total* is used to accumulate the item
values. When accumulating a sum, the total is initialized to zero. When
accumulating a product, the total is initialized to one^{21}.

Similar to the *accumulate* pattern, the *filtered-accumulate* pattern
updates a variable only if some test is passed.
This function sums all the even values in a given array, returning
the final sum:

def sumEvens(items): total = 0 for i in range(0,len(items),1): if (items[i] % 2 == 0): total += items[i] return total

As before, the variable *total* is used to accumulate the item
values. As with a regular accumulating, *total* is initialized to zero when
accumulating a sum. The initialization value is one when
accumulating a product and the initialization value is
the empty array when accumulating an array (see *filtering* below).

The *search* pattern is a slight variation of *filtered-counting*.
Suppose we wish to see if a value is present in an array. We can
use a filtered-counting approach; if the count is greater than
zero, we know that the item was indeed in the array.

def find(target,items): # is target in items? return occurrences(target,items) > 0 def occurrences(target,items): count = 0 for i in range(0,len(items),1): if (items[i] == target): count = count + 1 return count

In this case, *occurrences* implements the filtered-count pattern and
helps *find* do its job. We designate
such functions as *occurrences* and the like, *helper functions*.
However, we can improve the efficiency of *find* by
having it
partially implement the filtered-count,
but short-circuiting the
search once the target item is found. We do this
by returning from the body of the loop:

def find(target,items): for i in range(0,len(items),1): if (items[i] == target): return True # short-circuit! return False

When the array is empty, we return false, as indicated by the last line of the function, because the loop never runs and thus the return inside the loop can never be reached. In the same vein, if no item matches the target, we cannot return true, and eventually the loop exits and false is returned.

As a beginning programmer, however, you should be wary of returning from the body of a loop. The reason is most beginners end up defining the function this way instead:

def find(target,items): for i in range(0,len(items),1): if (items[i] == target): return True else: return False

The behavior of this latter version of *find* is incorrect,
but unfortunately, it appears to work correctly under some
conditions. If you cannot figure out why this version
fails under some conditions and appears to succeed under
others, you most definitely should stay away from placing
returns in loop bodies.

Often, we wish to find the largest or smallest value in an array. Here is one approach, which assumes that the first item is the largest and then corrects that assumption if need be:

largest = items[0] for i in range(0,len(items),1): if (items[i] > largest): largest = items[i]

When this loop terminates, the variable *largest* holds the
largest value. We can improve the loop slightly by noting
that the first time the loop body evaluates, we compare the
putative largest value against itself, which is a worthless
endeavor. To fix this, we can start the index variable *i*
at 1 instead:

largest = items[0] for i in range(1,len(items),1): #start comparing at index 1 if (items[i] > largest): largest = items[i]

Novice programmers often make the mistake of initialing setting
*largest* to zero and then comparing all values against *largest*,
as in:

largest = 0 for i in range(0,len(items),1): if (items[i] > largest): largest = items[i]

This code appears to work in some cases, namely if the largest value in the array is greater than or equal to zero. If not, as is the case when all values in the array are negative, the code produces an erroneous result of zero as the largest value.

Sometimes, we wish to find the index of the most extreme value in an array rather than the actual extreme value. In such cases, we assume index zero holds the extreme value:

ilargest = 0 for i in range(1,len(items),1): if (items[i] > items[ilargest]): ilargest = i

Here, we successively store the index of the largest value
see so far in the variable *ilargest*.

A special case of a filtered-accumulation is called *filter*.
Instead of summing the filtered items (for example), we collect
the filtered items into an array. The new array is said to be
a *reduction* of the original array.

Suppose we wish to extract the even numbers from an array. The
code looks very much like the *sumEvens* function,
but instead of adding in the desired item,
we make an array out of it and add it to the back of the
growing array of even numbers:

def extractEvens(items): evens = [] for i in range(0,len(items),1): if (isEven(items[i])): evens = evens + [items[i]] # array concatenation return evens

Given an array of integers, *extractEvens* returns a (possibly empty)
array of the even numbers:

>>> extractEvens([4,2,5,2,7,0,8,3,7]) [4, 2, 2, 0, 8] >>> extractEvens([1,3,5,7,9]) []

Note that our use of array concatenation makes our *extractEvens* function
run very slowly for very large arrays^{22}.
To speed up *extractEvens*, we will use the object nature of arrays and
invoke the *append* method to add an new element to the end of the existing
array^{23}.
In Python, one invokes a method on an object by using the *dot operator*.
Generically, the expression:

o.f()

means run method *f* on object *o*.
Using the *append* method, our *extractEvens* function becomes:

def extractEvens(items): evens = [] for i in range(0,len(items),1): if (isEven(items[i])): evens.append(items[i]) # method invocation return evens

We can see that the *append* method implements the procedure pattern
in that it modifies the *evens* array, not returning anything.
With this change,
the *extractEvens* function will run much faster^{24}.

*Mapping* is a task closely coupled with that
of filtering, but rather than collecting
certain items, as with the *filter* pattern, we
collect all the items. As we collect, however,
we transform each item as
we collect it. The basic pattern looks like this:

def map(f,items): result = [] for i in range(0,len(items),1): transformed = f(items[i]) result.append(transformed) return result

Here, function *f* is used to transform each item in the
before it is added to the growing result.

Suppose we wish to subtract one from each element in an array. First we need a transforming function that reduces its argument by one:

def decrement(x): return x - 1

Now we can "map" the *decrement* function over an array of numbers:

>>> map(decrement,[4,3,7,2,4,3,1]) [3, 2, 6, 1, 3, 2, 0]

Sometimes, we wish to combine two arrays into a third array,
This is easy to do with the concatenation operator, `+`

.

array3 = array1 + array2

This places the first element in the second array after the last
element in the first array.
However, many times we wish to intersperse the elements from the
first array with the elements in the second array. This is known
as a *shuffle*, so named since it is similar to shuffling a deck of
cards. When a deck of cards is shuffled,
the deck is divided in two halves (one half is akin to the first
array and the other half is akin to the second array). Next the
two halves are interleaved back into a single deck (akin to
the resulting third array).

We can use a loop to shuffle two arrays. If both arrays are exactly
the same length, a shuffling function is easy to implement
using the *accumulate* pattern.
Let's first assume the arrays are exactly the same size,
because that makes things easier:

def shuffle(array1,array2): array3 = [] for i in range(0,len(array1),1): array3.append(array1[i]) array3.append(array2[i]) return array3

Note how we initialized the resulting array *array3* to
the empty array. Then, as we walked the first array, we
pulled elements from both arrays, adding them into the
resulting array.

When we have walked past the end of *array1* is empty,
we know we have also walked past the end of *array2*, since the
two arrays have the same size.

If the incoming arrays do not have the same length, life gets more complicated:

def shuffle2(array1,array2): array3 = [] if (len(array1) < len(array2)): for i in range(0,len(array1),1): array3.append(array1[i]) array3.append(array2[i]) return array3 + array2[i+1:] else: for i in range(0,len(array2),1): array3.append(array1[i]) array3.append(array2[i]) return array3 + array1[i+1:]

Note the need to add the remaining elements in the longer array
to the items that made it into *array3*.

We can also use a *while* loop that goes until one of the arrays
is empty. This has the effect of removing the redundant code
in *shuffle2*:

def shuffle3(array1,array2): array3 = [] i = 0 while (i < len(array1) and i < len(array2)): array3.append(array1[i]) array3.append(array2[i]) i = i + 1 ...

When the loop ends, one or both of the arrays have been exhausted,
but we don't know which one or ones. A simple solution is to
add both remainders to *array3* and return.

def shuffle3(array1,array2): array3 = [] i = 0 while (i < len(array1) and i < len(array2)): array3.append(array1[i]) array3.append(array2[i]) i = i + 1 return array3 + array1[i:] + array2[i:]

Suppose *array1* is empty. Then the expression `array1[i:]` will
generate the empty array. Adding the empty array to *array3* will
have no effect, as desired. The same is true if *array2*
(or both *array1* and *array2* are empty).

Looking back at shuffle2, we see that the code would be much simpler if we could guarantee that one array was shorter than another. Suppose we write the code so that the assumption is that the first array is the shorter. Our code becomes:

def shuffle4(array1,array2): array3 = [] for i in range(0,len(array1),1): array3.append(array1[i]) array3.append(array2[i]) return array3 + array2[i+1:]

But what happens when the second array is shorter? The code will fail (how?) unless we handle it. Here's one way to handle it:

def shuffle4(array1,array2): if (len(array2) < len(array1)): return shuffle4(array2,array1) # arrays are flipped else: array3 = [] for i in range(0,len(array1),1): array3.append(array1[i]) array3.append(array2[i]) return array3 + array2[i+1:]

Note that we re-call *shuffle4* with *array2* as the first array
if the length of *array2* is less than the length of *array1*.
On this second call to *shuffle4*, we guarantee that the shorter array is
the first array.

Although it may seem, at first, rather strange to call *shuffle4* from
within *shuffle4*, Computer Scientists do this trick all the time.
It's called recursion and you will learn much more about recursion
in a later chapter.

With the *shuffle* pattern, we always took the head elements from both
arrays at each step in the shuffling process.
Sometimes, we wish to place a constraint of the choice of elements.
For example, suppose the two arrays to be combined are sorted
and we wish the resulting array to be sorted as well. The
following example shows that shuffling does not always work:

>>> a = [1,4,6,7,8] >>> b = [2,3,5,9] >>> c = shuffle2(a,b) [1, 2, 4, 3, 6, 5, 7, 9, 8]

The *merge* pattern is used to ensure the resulting array is
sorted and is based upon the *filtered-accumulate* pattern.
The twist is we only accumulate an item *if* it is the smallest item
in the two arrays that has not already been accumulated.
We start by keeping two index variables,
one pointing to the smallest element in *array1* and
one pointing to the smallest element in *array2*.
Since the arrays are ordered, we know the that the smallest
elements are at the head of the arrays:

i = 0 # index variable for array1 j = 0 # index variable for array2

Now, we loop, similar to *shuffle3*:

while (i < len(array1) and j < len(array2)):

Inside the loop, we test to see if the smallest element
in *array1* is smaller than the smallest element in *array2*:

if (array1[i] < array2[j]):

If it is, we add the element from *array1* to *array3* and increase
the index variable *i* for *array1* since we have "used up" the value
at index *i*.

array3.append(array1[i]) i = i + 1

Otherwise, *array2* must have the smaller element and we do likewise:

array3.append(array2[j]) j = j + 1

Finally, when the loop ends (*i* or *j* has gotten too large),
we add the remainders of both arrays to *array3* and return:

return array3 + array1[i:] + array2[j:]

In the case of merging, one of the arrays will be exhausted
and the other will not. As with *shuffle3*, we really don't
care which array was exhausted.

Putting it all together yields:

def merge(array1,array2): array3 = [] i = 0 j = 0 while (i < len(array1) and j < len(array2)): if (array1[i] < array2[j]): array3.append(array1[i]) i = i + 1 else: array3.append(array2[j]) j = j + 1 return array3 + array1[i:] + array2[j:]

Sometimes, a loop is so ill-specified that it never ends. This
is known as an *infinite loop*. Of the
two loops we are investigating, the *while* loop is the most
susceptible to infinite loop errors. One common mistake
is the *fossilized* pattern, in which the index variable never
changes so that the loop condition never becomes false:

i = 0 while (i < n): print(i)

This loop keeps printing until you terminate the program with
prejudice. The reason is that *i* never changes; presumably a
statement to increment *i* at the bottom of the loop body has
been omitted.

With the missed condition pattern, the index variable is updated, but it is updated in such a way that the loop condition never evaluates to false.

i = n while (i > 0): print(i) i += 1

Here, the index variable *i* needs to be decremented rather than
incremented. If *i* has an initial value greater than zero,
the increment pushes *i* further and further above zero.
Thus, the loop condition never fails and the loop
becomes infinite.

For Linux and Mac users, the code from this chapter can be found here

For Windows users, look here
(you will need to save the file as *loops.py*).

Contents |