# CS111 Lecture: List Processing Patterns & List Comprehension¶

## 1. Review: Early Return¶

Which of the following functions works for determining if val is an element in aList?

In [1]:
def isElementOf1(val, aList):
for elt in aList:
if elt==val:
return True
else:
return False

def isElementOf2(val, aList):
for elt in aList:
if elt==val:
return True
return False

def isElementOf3(val, aList):
for elt in aList:
if elt==val:
return True
return False


YOUR TURN: Predict which functions above will work for checking if 'mouse' is in the animal list. Verify this with someone sitting near you. Then, in the cell below, test your prediction.

In [2]:
animals = ["cat", "mouse", "dog", "rabbit"]

# Predict which of these will work before executing this cell
print("isElementOf1('mouse', animals) =>", isElementOf1('mouse', animals))
print("isElementOf2('mouse', animals) =>", isElementOf2('mouse', animals))
print("isElementOf3('mouse', animals) =>", isElementOf3('mouse', animals))

isElementOf1('mouse', animals) => False
isElementOf2('mouse', animals) => False
isElementOf3('mouse', animals) => True


## 2. List membership¶

Here are some lists from the lecture slides that we have seen before:

In [3]:
primes = [2, 3, 5, 7, 11, 13, 17, 19] # List of primes less than 20
bools   = [1<2, 1==2, 1>2]
houses  = ['Gryffindor', 'Hufflepuff', 'Ravenclaw', 'Slytherin']
strings = ['ab' + 'cd', 'ma'*4]
people = ['Hermione Granger', 'Harry Potter',
'Ron Weasley', 'Luna Lovegood']

# A list of string lists
animalLists = [['duck', 'raccoon'],
['fox', 'raven', 'gosling'], [], ['turkey']]

# A heterogeneous list
stuff = [17, True, 'foo', None, [42, False, 'bar']]
empty = [] # An empty list


### The built-in operators in and not in¶

We will use Python's built-in in and not in operators rather than isElementOf.
The in operator simplifies functions such as isVowel and isValidGesture that we have covered before:

In [4]:
def isVowel(char):
return char.lower() in 'aeiou'              # an example of using 'in' with a string

def isValidGesture(g):
return g in ['rock', 'paper', 'scissors']   # an example of using 'in' with a list

for c in 'ABcde':
print(c, ':', isVowel(c))

for g in ['rock', 'paper', 'scissors', 'Spock', 'paepr', 'sissors']:
print(g, ':', isValidGesture(g))

A : True
B : False
c : False
d : False
e : True
rock : True
paper : True
scissors : True
Spock : False
paepr : False
sissors : False


### YOUR TURN: Using in¶

Use in with lists and to check for substrings in strings.

Predict what each of the calls to testIn will do

In [5]:
def testIn(thing, collection):
print(thing, 'in', collection, '=>', thing in collection)

In [6]:
testIn('Ravenclaw', houses)

Ravenclaw in ['Gryffindor', 'Hufflepuff', 'Ravenclaw', 'Slytherin'] => True

In [7]:
testIn('Munger', houses)

Munger in ['Gryffindor', 'Hufflepuff', 'Ravenclaw', 'Slytherin'] => False

In [8]:
testIn('Hermione Granger', people)

Hermione Granger in ['Hermione Granger', 'Harry Potter', 'Ron Weasley', 'Luna Lovegood'] => True

In [9]:
testIn('Hermione', people)

Hermione in ['Hermione Granger', 'Harry Potter', 'Ron Weasley', 'Luna Lovegood'] => False

In [10]:
testIn('m', 'Hermione Granger')

m in Hermione Granger => True

In [11]:
testIn('x', 'Hermione Granger')

x in Hermione Granger => False

In [12]:
testIn('anger', 'Hermione Granger')

anger in Hermione Granger => True

In [13]:
testIn('oneG', 'Hermione Granger')

oneG in Hermione Granger => False

In [14]:
testIn('one G', 'Hermione Granger')

one G in Hermione Granger => True

In [15]:
testIn([2, 3], [1, 2, 3, 4])

[2, 3] in [1, 2, 3, 4] => False


Look at this concise way of testing for multiple substrings at once

In [16]:
for string in ['e', 'x', 'Hermione', 'oneG', 'one G']:
print(string, ':', string in 'Hermione Granger')

e : True
x : False
Hermione : True
oneG : False
one G : True


## 3. 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.

In [17]:
def sumList(nums):
sumSoFar = 0         # initialize accumulator variable
for n in nums:
sumSoFar += n
return sumSoFar

sumList([8, 3, 10, 4, 5])

Out[17]:
30

### Accumulation in lists¶

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

In [18]:
def halves(n):
"""Returns a list of successive halves created from n."""
result = []           # 1. initialize accumulator
while (n > 0):
result.append(n)  # 2. update accumulator
n = n//2           # 3. make n smaller
return result         # 4. return accumulator

In [19]:
# Test halves in this cell
halves(22)

Out[19]:
[22, 11, 5, 2, 1]

### Double accumulation¶

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

In [20]:
def partialSums(nums):
"""Returns a list of partial sums from a given list."""
# initialize accumulators
sumSoFar = 0
partials = []

# continously update the accumulators
for n in nums:
sumSoFar += n
partials.append(sumSoFar)

return partials

partialSums([8, 3, 10, 4, 5])

Out[20]:
[8, 11, 21, 25, 30]

## 4. 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']

In [21]:
def prefixes(phrase):
"""Given a string, returns a list of nonempty prefixes of the string,
ordered from shortest to longest.
"""
# Flesh out this function body
prefixList = []            # accumulator to hold final result as a list
prefixSoFar = ''           # accumulator to hold string value
for char in phrase:
prefixSoFar += char
prefixList.append(prefixSoFar)

return prefixList


In [22]:
prefixes('Python')

Out[22]:
['P', 'Py', 'Pyt', 'Pyth', 'Pytho', 'Python']
In [23]:
prefixes('Constantinople')

Out[23]:
['C',
'Co',
'Con',
'Cons',
'Const',
'Consta',
'Constan',
'Constant',
'Constanti',
'Constantin',
'Constantino',
'Constantinop',
'Constantinopl',
'Constantinople']
In [24]:
prefixes('oh')

Out[24]:
['o', 'oh']

## 5. The Mapping Pattern¶

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

In [25]:
def mapDouble(nums):
"""Given a list of numbers, returns a *new* list,
in which each element is twice the corresponding
element in the input list.
"""
result = []
for n in nums:
result.append(2*n)
return result

mapDouble([22, 33, 44, 55, 66, 77, 88])

Out[25]:
[44, 66, 88, 110, 132, 154, 176]

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

In [26]:
# define mapSquare by modifying mapDouble
def mapSquare(nums):
"""Given a list of numbers, returns a *new* list,
in which each element is the square of the corresponding
element in the input list.
"""
# Flesh out this function body
result = []
for n in nums:
result.append(n**2)
return result

In [27]:
# test mapSquare with the list of numbers from 1 to 10 inclusive, use range to generate the list
mapSquare(list(range(1, 11)))

Out[27]:
[1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

## 6. Exercise 2: mapLumos¶

Write a function named mapLumos, which takes a list of strings and returns a new list in which 'Lumos' is added to the end of each string

Example 1: mapLumos (people) returns ['Hermione GrangerLumos', 'Harry PotterLumos', 'Ron WeasleyLumos', 'Luna LovegoodLumos']

Example 2: mapLumos (['Shikha', 'Andy', 'Lyn', 'Peter', 'Sohie']) returns ['ShikhaLumos', 'AndyLumos', 'LynLumos', 'PeterLumos', 'SohieLumos']

Example 3: mapLumos([]) returns [] (the empty list)

In [28]:
def mapLumos(theList):
"""Given a list of strings, returns a new list in which
'Lumos' is added to the end of each string
"""
# Flesh out this function body
newWordsList = []
for word in theList:
newWordsList.append(word + 'Lumos')

return newWordsList

In [29]:
# Test mapLumos here with the lists above
mapLumos (people)

Out[29]:
['Hermione GrangerLumos',
'Harry PotterLumos',
'Ron WeasleyLumos',
'Luna LovegoodLumos']
In [30]:
mapLumos (['Shikha', 'Andy', 'Lyn', 'Peter', 'Sohie'])

Out[30]:
['ShikhaLumos', 'AndyLumos', 'LynLumos', 'PeterLumos', 'SohieLumos']
In [31]:
mapLumos([])

Out[31]:
[]

## 7. Exercise 3: 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.

In [32]:
def mapFirstWord(strings):
""" Given a list of (possibly multiword) strings,
returns a new list in which each element is the first word
of the corresponding string in the input list.
"""
# Flesh out this function body
firstWords = []
for word in strings:
first = word.split()[0]
firstWords.append(first)

return firstWords

In [33]:
mapFirstWord(people)

Out[33]:
['Hermione', 'Harry', 'Ron', 'Luna']
In [34]:
mapFirstWord (['feisty smelly dog', 'furry white bunny', 'orange clown fish'])

Out[34]:
['feisty', 'furry', 'orange']
In [35]:
mapFirstWord (['Shikha', 'Andy', 'Lyn', 'Peter', 'Sohie'])

Out[35]:
['Shikha', 'Andy', 'Lyn', 'Peter', 'Sohie']

## 8. 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.

In [36]:
def filterEvens(nums):
"""Given a list of numbers, returns a *new* list of all
numbers in the input list that are divisible by 2.
"""
result = []
for n in nums:
if n%2 == 0:
result.append(n)
return result


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

In [37]:
filterEvens([100, 21, 32, 44, 55, 71, 91, 23, 56])

Out[37]:
[100, 32, 44, 56]
In [38]:
filterEvens([2, 4, 6, 8])

Out[38]:
[2, 4, 6, 8]
In [39]:
filterEvens([11, 13, 15, 17, 19])

Out[39]:
[]

## 9. Exercise 4: filterElementsContaining¶

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

In [40]:
def filterElementsContaining(val, aList):
"""Return a new list whose elements are all the
elements of aList that contain val.
"""
# Flesh out this function body
newList = []
for item in aList:
if val in item:
newList.append(item)
return newList

In [41]:
filterElementsContaining('er', people)

Out[41]:
['Hermione Granger', 'Harry Potter']
In [42]:
filterElementsContaining('Harry', people)

Out[42]:
['Harry Potter']
In [43]:
filterElementsContaining('Voldemort', people)

Out[43]:
[]
In [44]:
filterElementsContaining('y',['hairy smelly dog', 'furry white bunny', 'orange clown fish'])

Out[44]:
['hairy smelly dog', 'furry white bunny']

## 10. Optional: List Comprehension¶

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

In [45]:
# The old way of doing mapping

nums = [17, 42, 6]
result = []
for x in nums:
result.append(x*2)
print(result)

[34, 84, 12]

In [46]:
# The new way of doing mapping

result = [x*2 for x in nums]
print(result)

[34, 84, 12]

In [47]:
# The old way of doing filtering

nums = [17, 42, 6]
result = []
for n in nums:
if n%2 == 0:
result.append(n)
print(result)

[42, 6]

In [48]:
# The new way of doing filtering

result = [n for n in nums if n%2 == 0]
print(result)

[42, 6]


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

In [49]:
# Example 1: mapping with list comprehension
# generate the list of squares for range(1, 6)
# it should show [1, 4, 9, 16, 25]

[el*el for el in range(1, 6)]

Out[49]:
[1, 4, 9, 16, 25]
In [50]:
# Example 2: mapping with list comprehension
# add the ending 'th' to all words in a phrase
phrase = "mine dog ate your shoe"
# expected phrase: ["mineth", "dogth", "ateth", "yourth", "shoeth"]

[item + 'th' for item in phrase.split()]

Out[50]:
['mineth', 'dogth', 'ateth', 'yourth', 'shoeth']
In [51]:
# Example 3: filtering with list comprehension
# keep all words that do not end with a vowel
phrase = "what books are on sale"
# expected result: ['what', 'books', 'on']

def isVowel(char):
return char.lower() in 'aeiou'

[word for word in phrase.split() if not isVowel(word[-1])]

Out[51]:
['what', 'books', 'on']
In [52]:
# Example 4: mapping *and* filtering with list comprehension
# return list of squares of only the odd numbers in a list
numbers = [6, 3, 2, 8, 7, 1, 5, 4]
# expected result: [9, 49, 1, 25]

[n*n for n in numbers if n % 2 == 1]

Out[52]:
[9, 49, 1, 25]

### 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!

In [53]:
def makeSquarePairs(num):
# flesh out the body of this function
# you only need ONE line of code
return [(n, n*n) for n in range(1, num+1)]

In [54]:
makeSquarePairs(5)

Out[54]:
[(1, 1), (2, 4), (3, 9), (4, 16), (5, 25)]

## 11. 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.

In [55]:
[(x**2) for x in range(10) if x % 2 == 0]

Out[55]:
[0, 4, 16, 36, 64]

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.

In [56]:
newList = []
for x in range(10):
if x % 2 == 0:
newList.append(x**2)
newList

Out[56]:
[0, 4, 16, 36, 64]

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

In [57]:
# Example 1: Write a list comprehension that filters the vowels from a word
# such as beauteous and returns a list of its capitalized vowels.
word = "beauteous"

[letter.upper() for letter in word if isVowel(letter)]

Out[57]:
['E', 'A', 'U', 'E', 'O', 'U']
In [58]:
# Example 2: Write a list comprehension that filters a list of proper nouns by length.
# It should extract nouns of length greater than 4 but less than 8 and return a list
# where the first letter is properly capitalized.
# This is a challenge!
properNouns = ["cher", "bjork", "sting", "beethoven", "prince", "madonna"]


['Bjork', 'Sting', 'Prince', 'Madonna']