Worked lesson: traversing a list

A traversal visits the elements of a list one at a time. In AP CSP pseudocode, FOR EACH r IN readings sets r to the first element, runs the block, then sets r to the second element, and so on until the list runs out. List indexes start at 1, so the first element is readings[1].

Most traversals keep an accumulator, a variable that holds the answer so far. It is given a starting value before the loop, updated inside it, and returned after it ends. The four errors later in this lesson are mistakes in exactly those three places.

A school weather club records daily rainfall in millimetres. This procedure counts the days with at least a threshold amount of rain.

1PROCEDURE CountAtLeast(readings, threshold)2{3  count ← 04  FOR EACH r IN readings5  {6    IF (r ≥ threshold)7    {8      count ← count + 19    }10  }11  RETURN count12}

Trace CountAtLeast([3, 8, 5, 1], 5). Before the loop, count is 0. Each row is one pass through the loop body:

After the fourth element the loop ends and the procedure returns 2. Notice element 3: 5 is not greater than 5, but it is at least 5, so it counts.

The accumulator does not have to be a count. Here it holds the largest reading seen so far.

1PROCEDURE Largest(readings)2{3  largest ← readings[1]4  FOR EACH r IN readings5  {6    IF (r > largest)7    {8      largest ← r9    }10  }11  RETURN largest12}

It returns 22. Starting from readings[1] guarantees the starting value is a real reading. The first comparison is wasted (14 > 14), but it is harmless. Here > and ≥ give the same answer, because replacing 22 with 22 changes nothing.

Largest has a precondition: readings must contain at least one element. On an empty list there is no readings[1], and accessing an index outside the list is an error that stops the program, so Largest([ ]) has no valid result. Compare CountAtLeast([ ], 5), which safely returns 0: the loop body never runs and count keeps its starting value. Whenever a procedure reads a specific element, state that the list must be non-empty, or check it first.

Change ≥ to > in CountAtLeast and the 5 in our worked example is no longer counted: it returns 1 instead of 2. The two versions only disagree when a reading equals the threshold.

1PROCEDURE CountAtLeast(readings, threshold)2{3  count ← 04  FOR EACH r IN readings5  {6    IF (r > threshold)7    {8      count ← count + 19    }10  }11  RETURN count12}

How to catch it: always include a test value exactly on the boundary. Read the task carefully. “At least”, “or more” and “no fewer than” mean ≥. “More than” and “over” mean >.

Here count ← 0 has moved inside the loop. It now runs once per element and erases every earlier match. The result can only ever be 0 or 1, depending only on the last element.

1PROCEDURE CountAtLeast(readings, threshold)2{3  count ← 04  FOR EACH r IN readings5  {6    count ← 07    IF (r ≥ threshold)8    {9      count ← count + 110    }11  }12  RETURN count13}

How to catch it: test a list where several elements match but the last one does not, such as [8, 6, 9, 1]. The correct answer is 3; this version returns 0.

Here a RETURN sits inside the loop. RETURN ends the whole procedure immediately, so this version only ever looks at the first element.

1PROCEDURE CountAtLeast(readings, threshold)2{3  count ← 04  FOR EACH r IN readings5  {6    IF (r ≥ threshold)7    {8      count ← count + 19    }10    RETURN count11  }12  RETURN count13}

How to catch it: test a list whose first element does not match but a later one does, such as [1, 8, 8]. Single-element lists and empty lists will not catch it.

For a count, 0 is the right starting value. For the largest value it is a trap. If largest starts at 0 and every reading is negative (winter temperatures, say), nothing is ever greater than 0. The procedure returns 0, a value that is not in the list.

How to catch it: ask what your starting value means if the loop body never changes it. Start from the first element (only when the list is guaranteed to be non-empty), or from a value you can justify for every possible list. Then test a list where every value is below that starting value.

A RETURN inside a loop is not always a bug. When the question is about the first match, or about whether any element matches, stopping early is the point. That is a deliberate partial traversal.

1PROCEDURE FirstDayOver(readings, threshold)2{3  day ← 14  FOR EACH r IN readings5  {6    IF (r > threshold)7    {8      RETURN day9    }10    day ← day + 111  }12  RETURN -113}

A partial traversal can stop early, but only if a match exists. With readings [3, 7, 9] and threshold 5, it returns 2 at the second element and never looks at 9. With [3, 4, 1] there is no match, so it still checks every element, and RETURN -1 runs only once the loop finishes. Ask yourself: does the answer depend on every element (complete traversal), or can one element settle it (partial traversal)?

A test exposes a bug when the buggy version and a correct version return different values. A random test often passes by luck. Instead, aim each test at one line:

• The comparison: include a value exactly equal to the threshold.
• The accumulator reset: several matches, then a non-match at the end.
• The RETURN position: a non-match first, a match later.
• The starting value: a list where every value is below it.
• The empty list: does the procedure still return something sensible?

You will practise exactly this in the investigation.