Storing elements in a sequence in Python (Part 3)

Using loops on sequences

Let's look at the use of loops on lists.

def count_chars(entry, char):
    count = 0
    pos = 0
    while pos < len(entry):
        if entry[pos] == char:
            count = count + 1
        pos = pos + 1
    return count

As usual, we can start with strings as a starting point. count_chars is a function that consumes a string and a character and returns the number of times the character appears in the string.

---

def count_items(entry, item):
    count = 0
    pos = 0
    while pos < len(entry):
        if entry[pos] == item:
            count = count + 1
        pos = pos + 1
    return count

To change it into a function on lists, we don't need to change anything at all. Here I've changed the name of the function count_chars to count_items and I've change the name of the parameter char to item, but even that wasn't really necessary.

This is one of the built-in functions, count. Can we write other built-in functions using loops?

---

Example: deconstructing in

The function in determines whether an item is in a list.

def is_in(sequence, value):
    """Docstring
    """

We leave out the docstring for sake of space - not that that is what you should be doing!

---

    pos = 0 
    while pos < len(sequence):


        pos = pos + 1

We iterate through positions in the list, starting at 0, and incrementing the value in the loop.

---

        if sequence[pos] == value:
            return True

We check to see if the element at our current position is equal to value, and return True if there is a match.

---

    return False

If we haven't found a match and returned True, when we exit the loop we return False.

---

Putting all of this code together in the correct order gives the following:

def is_in(sequence, value):
    """Docstring
    """
    pos = 0 
    while pos < len(sequence):
        if sequence[pos] == value:
            return True
        pos = pos + 1
    return False

---

def test_is_in():
    """Tests correctness of is_in
    """
    assert is_in([0, 1, 2, 3], 2) == True  
    assert is_in([0, 1, 2, 3], 4) == False
    assert is_in([],  4) == False

test_is_in()

We test our function and see that it works.

---

There was nothing about this function that required that the input be a list, especially since we left out the docstring.

def test_is_in():
    """Tests correctness of is_in
    """
    assert is_in([0, 1, 2, 3], 2) == True  
    assert is_in([0, 1, 2, 3], 4) == False
    assert is_in([],  4) == False
    assert is_in("caterpillar", "a") == True  
    assert is_in("caterpillar", "f") == False
    assert is_in("",  "a") == False

test_is_in()

We can add tests for strings to test_is_in and see that the function still works.

---

Example: deconstructing max

What about the built-in function max? Consider the sequence of numbers shown:

3

0

6

1

5

2

2

3

7

4

4

5

10

6

1

7

3

8

9

9

How might we figure out the maximum value by looking at all the values?

We can look through the values, keeping track of the best so far. When we've only looked at one value, it is by default the best.

---

We now compare 6 to the best, and see that 6 is bigger.

---

So we replace 6 as best, and now compare 5 to the best. Since best is bigger, we go on to the next element.

---

2 is not bigger than best, so we move along.

---

7 is bigger than 6.

---

We update best to 7. Now we compare 4 to best.

---

Then we compare 10 to best, which results in another update.

---

Since 1, 3, and 9 are all smaller than 10, the final value is 10.

---

Writing the function

def seq_max(sequence):
    """Determines the maximum element.

       Preconditions:
       sequence: length at least one
    """

As usual, we start with the function header. This time we'll have a partial docstring to make sure that our sequence is of length at least one.

---

    counter = 1
    while counter < len(sequence):


        counter = counter + 1

We put in the condition, initial value, and change to the value.

---

    best = sequence[0]

We start with our candidate maximum as the first value.

---

        if best < sequence[counter]:
            best = sequence[counter]

We then compare each subsequent value, updating the best value as we go.

---

    return best

We return the winner at the end.

---

Putting all of this code together in the correct order gives the following:

def seq_max(sequence):
    """Determines the maximum element.

       Preconditions:
       sequence: length at least one
    """

    best = sequence[0]
    counter = 1
    while counter < len(sequence):
        if best < sequence[counter]:
            best = sequence[counter]
        counter = counter + 1
    return best

---

def test_seq_max():
    """Tests correctness of seq_max
    """
    assert seq_max([0, 1, 5, 2, 1]) == 5  
    assert seq_max([0]) == 0
    assert seq_max('caterpillar') == 't'  
    assert seq_max(['c']) == 'c'    

test_seq_max()

We can test this with both lists and strings.

---

Example: finding the position of a minimum element

Let's modify the previous function to determine the minimum instead of the maximum, and return the position of one of the elements of minimum value. There could be more than one.

def pos_min(sequence):

        if best < sequence[counter]:

Let's change the name of the function and the comparison, so that we obtain the minimum instead of the maximum.

---

    pos = 0

            pos = counter

    return pos

To keep track of the position, each time we update best, we also update the position, which we initialize to zero, and return its final value. This will give us the minimum value that is closest to the end.

---

The new function is now as shown:

def pos_min(sequence):
    best = sequence[0]
    pos = 0
    counter = 1
    while counter < len(sequence):
        if best > sequence[counter]:
            best = sequence[counter]
            pos = counter
        counter = counter + 1
    return pos

---

def test_pos_min():
    """Tests correctness of pos_min
    """
    assert pos_min([6, 1, 5, -2, 1]) == 3  
    assert pos_min([0]) == 0

test_pos_min()

We test our function, and see that it works.

---

Example: giving raises (change the sequence)

Let's look at an example with mutation. We have a list of salaries, all of which we want to multiply by a booster.

def change(salaries, booster):
    counter = 0
    while counter < len(salaries):

        counter = counter + 1

We put in the condition, initialize the value of counter, and increment it in the loop.

---

def change(salaries, booster):
    counter = 0
    while counter < len(salaries):
        salaries[counter] = salaries[counter] * booster
        counter = counter + 1

To update an individual salary, we use the index of the element on the left side of the assignment to multiply the old value by booster.

---

def test_change():
    the_list = [4, 3, 5, 2, 1]
    change(the_list, 2)
    assert the_list == [8, 6, 10, 4, 2]

test_change()

We then test the function to see that the input has been changed.

---

Example: giving raises (create a new sequence)

def change(salaries, booster):
    new_list = []
    counter = 0
    while counter < len(salaries):
        new_list = new_list + \
        [salaries[counter] * booster]
        counter = counter + 1
    return new_list

To modify our function to instead create a new sequence, we create a new list, and at each iteration add a new salary using concatenation. We then return the new list.

---

def test_change():
    the_list = [0, 1, 2, 3, 4, 5]
    assert change(the_list, 2) == [0, 2, 4, 6, 8, 10]
    assert the_list == [0, 1, 2, 3, 4, 5]

test_change()

These statements show that a new list is created without the old one having been changed.

---

def change(salaries, booster):
    new_list = list(salaries)
    counter = 0
    while counter < len(new_list):
        new_list[counter] = \
        new_list[counter] * booster
        counter = counter + 1
    return new_list

Another way to write the function is to create a new list with all the old values, and then to update a value at each iteration.

---

def test_change():
    the_list = [0, 1, 2, 3, 4, 5]
    assert change(the_list, 2) == [0, 2, 4, 6, 8, 10]
    assert the_list == [0, 1, 2, 3, 4, 5]

test_change()

Again, we can see that the list has not changed.

---