CS111 Lecture: While Loops, Early Return, List Accumulation

1. Introducing while loops

for loops iterate over a pre-determined sequence and stop at the end of the sequence.

while loops are useful when we don't know in advance when to stop.

Example of a while loop that depends on user input

Example of a while loop that depends on argument value

2. Gotcha: infinite loop

We sometimes might wrongly write an infinite loop, one that never ends. In these cases, use Ctrl+C to break out of the loop.

NOTE: In the Notebook, it might not be possible sometimes to break the loop, even with Kernel|Interrupt. In this case, close the tab and open it again.

3. The Accumulating Pattern

It is common to use a while loop in conjunction with one or more accumulators = variables that accumulate results from processing the elements of a sequence.

Here is a sumHalves function that takes an nonnegative integer and returns the sum of the values printed by printHalves.

4. Exercise 1: define sumBetween

Define a function sumBetween that takes two integer parameters lo and hi and returns the sum of the integers between lo and hi (inclusive).

sumBetween(4, 8) returns 30 (4 + 5 + 6 + 7 + 8)

5. Exercise 2: accumulate string elements

Define a function concatAll that takes a list of strings and returns a single string that is the result of concatenating all the strings in the list.

It will be very similar to the sumListFor function above.

NOTE: Think carefully about the initial value of the accumulator. It cannot be an integer value.

beatles = ['John','Paul','George', 'Ringo']
concatAll(beatles)
'JohnPaulGeorgeRingo'

Test your concatAll function below:

6. Exercise 3: count occurrences in a list

Define a function that returns the number of occurrences of a string in a list of strings. Here are some examples of how the function behaves:

sentence = 'the cat that ate the mouse liked the dog that played with the ball'
print countOf('the', sentence.split())
print countOf('that', sentence.split())
print countOf('jerry', sentence.split())

4
2
0

As you can see the word the occurs 4 times in the sentence, that occurs 2 times, and jerry 0 times.

ASIDE: What is split? This is a method that operates on string values. It takes a big string and slits it at the space characters.

7. Returning early from a loop

Sometimes, you do not need to iterate through all elements to determine your result.
When a loop is in a function, return can be used to exit the loop early (e.g., before it visits all the elements in a list).

And now test the predicate isElementOf:

When using early return, it's easy to make a mistake and return earlier than you want. Below are two examples of early return done wrong.

8. Exercise 4: containsDigits

Define a function containsDigits that takes a string and returns True if there is at least one digit in the string; otherwise it returns False.

containsDigit('The answer is 42')               True  
containsDigit('pi is 3.14159...')               True  
containsDigit('76 trombones')                   True  
containsDigit('the cat ate the mouse')          False  
containsDigit('one two three')                  False

Use the isdigit string method to determine if a character is a digit.

9. Exercise 5: areAllPositive

Define a function areAllPositive that takes a list of numbers and returns True if all the numbers in the list are positive; otherwise it returns False.

areAllPositive([17, 5, -42, 16, 31])         False
areAllPositive([])                           True
areAllPositive([-17, 5, -42, -16, 31])       False
areAllPositive([17, 5, 42, 16, 31])          True

10. Exercise 6: indexOf

Define a function indexOf that takes two arguments, a value val and a list elts, and returns the first index in elts at which val appears. If val does not appear in elts, it returns -1.

indexOf(8, [8,3,6,7,2,4])       0
indexOf(7, [8,3,6,7,2,4])       3
indexOf(5, [8,3,6,7,2,4])       -1

There are two different approaches to this problem. Try to implement them both.

  1. using a for loop with an index i and range
  2. using a while loop with an accumulator variable i

11. Accumulation for values and lists

In previous lectures we have seen that it is common to use loops in conjunction with accumulating variables that accumulate results from processing elements within the loop. Here is the definition of a sumList function that takes a list of numbers and returns the sum of the numbers.

The accumulator in this case is a number.

Accumulation in lists

We can create new lists through accumulation, for example, a list of a number and its halves (see slide 5).

Double accumulation

We can have more than one accumulations happening at the same time, as shown in the function below:

12. Exercise 1: prefixes

Write a function named prefixes() that, given a string, returns a list of nonempty prefixes of the string,
ordered from shortest to longest.

prefixes('Python') --> ['P','Py','Pyt','Pyth','Pytho','Python']

13. The Mapping Pattern

We can generate a new list by performing an operation on every element in a given list. This is called mapping.

YOUR TURN: Modify the function mapDouble to become mapSquare, and generate the list of squares for the numbers 1 to 10 (inclusive).

15. Exercise 2: mapFirstWord

Write a function named mapFirstWord, which takes a list of strings in which each string has words separated by spaces. It returns a new list of the first words in each string.

16. The Filtering Pattern

Another common way to produce a new list is to filter an existing list, keeping only those elements that satisfy a certain predicate.

NOTE: Before executing these cells, try to hypothesize what the output will be, then verify.

17. Exercise 3: filterMultiplesOfThree

Write a function that takes a list of numbers and returns a new list of all the numbers that are multiples of three.

18. Exercise 4: filterElementsContaining

Write a function that takes a value and a list and returns a new list of all elements containing the value.

19. Optional: List Comprehension

We can simplify the mapping/filtering patterns with a syntactic device called list comprehension.

YOUR TURN: Try to write the following list comprehension examples:

Challenge Exercise

Write the function makeSquarePairs that given a single integer num returns a list of tuples containing all numbers from 1 to the num inclusive and their square values. An example is shown below:

makeSquarePairs(5)
[(1, 1), (2, 4), (3, 9), (4, 16), (5, 25)]

Use list comprehension!

20. Optional: List Comprehensions with Mapping and Filtering

It is possible to do both mapping and filtering in a single list comprehension. Examine the example below which filters a list by even numbers and creates a new list of their squares.

Note that our expression for mapping still comes before the "for" and our filtering with "if" still comes after our sequence. Below is the equivalent code without list comprehensions.

YOUR TURN: Try to write the following list comprehension examples: