Storing elements in a sequence (Part 3)

Example: searching a sequence

Just like while loops were useful in writing functions for strings, we'll use them a lot for functions on sequences. As a first example, suppose we wish to write a function that produces the position of the first occurrence of an item in a sequence, or the length of the sequence if the item cannot be found.

In this example, if the input is the number 1, the function should produce 2, the first position where 1 occurs. If instead the input is 20, which does not appear in the sequence, the output will be 11, the length of the sequence. Notice that there is no item in position 11, so the meaning is clear.

Writing the function

While loop recipe

Express the task as iteration.
Write a condition.
Ensure initial values of variables checked in the condition.
Ensure the condition can change in the loop body.

define search(sequence, item) counter ← 0 while counter < length(sequence) if sequence[counter] == item return counter counter ← counter + 1 return counter

We use the recipe to write the function, where we use iteration to search for the item in each of the positions in turn. We'll use a counter that goes through possible positions, which we initialize to zero outside the loop. To ensure that the condition can change, in the loop we increment the counter. Inside the loop, the current item in the sequence is compared to the one we wish to find and we return the position if it is found. The last line is only reached if the item is not found, returning the length of the sequence.

Example: swapping the first and middle element

Changing the sequence by exchanging the first element and the middle element. — Image: baltasarr/iStock/Thinkstock

We had a function that exchanged the first and middle elements of string creating a new string. What if we wanted to change a sequence in this way? As before, we can think of the sequence in parts. However, we're not making a new sequence. To modify the sequence, we follow the steps given below:

We first move the middle element to temporary storage so that we don't "lose it" when we put the first element in the middle.
We can now give a new value, namely the first element, as the middle element.
Now we can give a new value for the first element, that is, what was the previous middle element.

Writing the function

How would we write this in pseudocode?

define swap(sequence) if length(sequence) > 0 middle ← floor(length(sequence) / 2) temp ← sequence[middle] sequence[middle] ← sequence[0] sequence[0] ← temp return sequence

We first determine the position of the middle element. Next, we make the three assignments that we listed on the blackboard, in the same order as we listed them. We use the name "temp" for the variable that temporarily stores the middle element.

Caution

Never forget the empty sequence.

Finally, we make sure to handle the case in which the sequence is empty. Since we do nothing in that case, we do not need to have an else case for a second set of steps. We may omit the return statement without generating an error.

Caution

Omitting the return statement results in a side effect, not an output.

The goal here is to change the input as a side effect. If we wish to add a return statement, we can do so. If we place it within the if statement, a value will only be returned when the condition is true, that is, when the sequence is nonempty. To ensure that a value is returned in all case, we put the return statement after the if statement, at the same level of indentation as the line checking the condition.

Example: giving raises (change the sequence)

In our next example, we are going to use a while loop to modify the input sequence. The sequence is a list of salaries, each of which is to be multiplied by a value booster to modify the original sequence.

For example, modifying the sequence [40, 10, 25, 6, 15, 8], shown below,

by multiplying each salary by booster, which we equate to 2 in this case, gives the sequence [80, 20, 50, 12, 30, 16]:

Writing the function

While loop recipe

Express the task as iteration.
Write a condition.
Ensure initial values of variables checked in the condition.
Ensure the condition can change in the loop body.

define change(salaries, booster) counter ← 0 while counter < length(salaries) salaries[counter] ← salaries[counter] * booster counter ← counter + 1

The condition for the while ensures that we iterate over all elements in the list where counter is initialized to 0. As usual, we increment the counter in the loop. How do we update an element? Remember, we can use the index on the left side of the assignment, treating it like any other variable. So this indicates that the new value assigned to the item is the old value multiplied by booster.

Example: giving raises (create a new sequence)

define change(salaries, booster) new = [] counter ← 0 while counter < length(salaries) new ← new + [salaries[counter] * booster] counter ← counter + 1 return new

What if instead we wanted to create a new sequence? The condition, initialization, and change to the counter are the same as before. This time, each time an item is processed, a new value is created, made into a sequence, and concatenated with the new sequence that has been created so far. Here we need a return statement since we are creating output, not a side effect. All that remains is to ensure, at the very beginning of the function body, that we initialize the new sequence.

Tricky parts about using sequences

Remember to count from zero.
Watch out for aliasing.
Know whether a function makes a new sequence or alters the input.
Exclude or handle the empty case.
Process each element using a loop.

In using sequences, we need to remember, as for strings, that we count from zero. Unlike in using strings, we need to be aware of when aliasing might take place, and in particular to know whether a function returns a new sequence or alters the input. The empty case needs to be excluded by the preconditions or handled in the code. If each element is to be examined, use a loop.