CS 111 Lecture: Sorting, map & filter

Table of Contents

  1. HOF: map and filter
  2. Exercises: map
  3. More on map
  4. Exercises: filter
  5. More on filter

1. HOFs: map and filter

map for the mapping pattern

Recall that the mapping pattern creates an output list by calculating the result of a given function on every element of an input list.

We have seen how the mapping pattern can be expressed with list comprehensions:

In [1]:
[n*2 for n in [7, 2, 5, 1]]
Out[1]:
[14, 4, 10, 2]

Python also has a higher-order map function that takes two arguments:

  1. the mapping function and
  2. the input list

and returns a map object.

In [2]:
def double(n):
    return n*2
    
map(double, [7, 2, 5, 1])
Out[2]:
<map at 0x105963160>

To see the contents of a map object, use the built-in function list() to convert the map object to a list object.

In [3]:
list(map(double, [7, 2, 5, 1]))
Out[3]:
[14, 4, 10, 2]

filter for the filtering pattern

Recall that the filtering pattern creates an output list by keeping all elements in the list that return True for a given predicate function.

We have seen how the filtering pattern can expressed with list comprehensions:

In [4]:
[n for n in [8, -3, -4, 5, 1, -3, 2] if n > 0] # Keep only the positive numbers in list
Out[4]:
[8, 5, 1, 2]

Python also has a higher-order filter function that takes two parameters:

  1. the filtering function (this is a predicate that returns True or False.
  2. the input list

and returns the sequence of elements for which the predicate returns True as a filter object. For example:

In [5]:
def isPositive(n):
    return n > 0

filter(isPositive, [8, -3, -4, 5, 1, -3, 2])
Out[5]:
<filter at 0x1059630f0>

Similar to map(), pass the filter object into list() to convert the filter object to a list object and see its contents.

In [6]:
list(filter(isPositive, [8, -3, -4, 5, 1, -3, 2]))
Out[6]:
[8, 5, 1, 2]

2. Exercises: map

Replace the ?s in the following map expressions with an appropriate function (and define that function) to generate the indicated output.

In [7]:
#define function here
def exp2(n):
    return n*n
In [8]:
mapObject = map(exp2, [8, 3, 6, 7, 2, 4]) # to give [64, 9, 36, 49, 4, 16]
list(mapObject)
Out[8]:
[64, 9, 36, 49, 4, 16]
In [9]:
#define function here
def pluralize(word):
    return word+'s'
In [10]:
mapObject = map(pluralize, ['donut','muffin','bagel']) # to give ['donuts','muffins','bagels']
list(mapObject)
Out[10]:
['donuts', 'muffins', 'bagels']
In [11]:
#define function here
def lastLetter(word):
    return word[-1]
In [12]:
mapObject = map(lastLetter, ['donut','muffin','bagel'])    # to give ['t', 'n', 'l']
list(mapObject)
Out[12]:
['t', 'n', 'l']
In [13]:
#define function here
def double(word):
    return 2*word
In [14]:
mapObject = map(double, ['can','foo','wiki'])    # to give ['cancan', 'foofoo', 'wikiwiki']
list(mapObject)
Out[14]:
['cancan', 'foofoo', 'wikiwiki']
In [15]:
#define function here
def greaterThanFive(n):
    return n>5
In [16]:
mapObject = map(greaterThanFive, [8, 3, 6, 7, 2, 4])   # to give [True, False, True, True, False, False]
list(mapObject)
Out[16]:
[True, False, True, True, False, False]
In [17]:
#define function here
def only17(word):
    return 17
In [18]:
mapObject = map(only17, ['a', 'be', 'cat', 'dodo'])   # to give [17, 17, 17, 17]
list(mapObject)
Out[18]:
[17, 17, 17, 17]

3. More on map

map on non-list sequences

The map function can be used on any sequence and always returns a map object.

In [19]:
def upperCase(s):
    return s.upper()
In [20]:
mapObject = map(upperCase, 'cat') # test map on a string
list(mapObject)
Out[20]:
['C', 'A', 'T']
In [21]:
mapObject = map(upperCase, ('ant','bat','cat')) # test map on a tuple
list(mapObject)
Out[21]:
['ANT', 'BAT', 'CAT']

The method join can be used to combine lists of strings into a single string. Join actually takes any iterable and can be used in conjunction with mapping:

In [22]:
', '.join(map(upperCase, ('ant','bat','cat')))
Out[22]:
'ANT, BAT, CAT'
In [23]:
''.join(map(upperCase, 'cat')) # use join to combine letters back into a string
Out[23]:
'CAT'

You don't really need map and .join in the second example, because upper does this by default:

In [24]:
'cat'.upper()
Out[24]:
'CAT'

map with multiple lists

map allows any number of list arguments as long as the supplied function takes a number of arguments (expressed as a tuple) that's the same as the number of lists.

In [25]:
def sumify(a,b):
    return a+b

def makeTuple(a,b):
    return (a,b)
In [26]:
mapObject = map(sumify, [8, 3, 5], [10, 20, 30]) 
list(mapObject)
Out[26]:
[18, 23, 35]
In [27]:
mapObject = map(makeTuple, [8, 3, 5], [10, 20, 30])
list(mapObject)
Out[27]:
[(8, 10), (3, 20), (5, 30)]

Q: What is the above expression equivalent to? (which Python function?)

Here we're using a functions with three parameters, and passing three lists:

In [28]:
def sum3(a,b,c):
    return a+b+c

mapObject = map(sum3, [8,3], [10,20], [7,2])
list(mapObject)
Out[28]:
[25, 25]

If the sequences are not the same size, map() will stop once the shortest sequence has been exhausted.

In [29]:
mapObject = map(sumify, [8,3,5,6], [10,20,30])   # what happens here?
list(mapObject)
Out[29]:
[18, 23, 35]

Defining functions with map

Below are some functions written using list comprehensions with the mapping pattern. Express them instead in terms of map and helper functions.

Define: mapPreConcat

mapPreConcat('com', ['puter','pile','mute']) --> ['computer','compile','commute']

In [30]:
# Definition using list comprehension
def mapPreConcatComp(prefix, wordList):
    return [prefix+word for word in wordList]
In [31]:
# test
mapPreConcatComp('com', ['puter', 'pile', 'mute'])
Out[31]:
['computer', 'compile', 'commute']
In [32]:
# Definition using map.  Note you will need to wrap your result with list() to match the type of the list comprehension.
def concat(word1, word2):
    return word1+word2

def mapPreConcat(prefix, word):
    prefixList = ((prefix+' ')*len(word)).split()
    mapObject = map(concat, prefixList, word)
    return list(mapObject)
In [33]:
# test
mapPreConcat('com', ['puter', 'pile', 'mute'])
Out[33]:
['computer', 'compile', 'commute']

Define: suffixes

mapSuffixes(’python') --> ['python', 'ython', 'thon', 'hon', 'on', 'n']

In [34]:
# Definition using list comprehension
def mapSuffixes(word):
    return [word[i:] for i in range(len(word))]
In [35]:
# test 
mapSuffixes('python')
Out[35]:
['python', 'ython', 'thon', 'hon', 'on', 'n']
In [36]:
# Definition using map.  Note you will need to wrap your result with list() to match the type of the list comprehension.
def suffixI(i, word):
    return word[i:]

def mapSuffixes(word):
    wordList = (len(word)*(word+' ')).split()
    mapObject = map(suffixI, range(len(word)), wordList)
    return list(mapObject)
In [37]:
# test 
mapSuffixes('python')
Out[37]:
['python', 'ython', 'thon', 'hon', 'on', 'n']

4. Exercises: filter

Replace the ?s in the following filter expressions with functions (which you define) to give the indicated results:

In [38]:
# define function here
def isPositive(n):
    return n > 0
In [39]:
filterObject = filter(isPositive, [8, -3, 6, 7, -2, -4, 5])   # to give [8, 6, 7, 5]
list(filterObject)
Out[39]:
[8, 6, 7, 5]
In [40]:
# define function here
def startsWithA(word):
    return 'a' == word[0]
In [41]:
# to give ['a', 'at', 'ant, ‘aardvark’]
filterObject = filter(startsWithA, ['a', 'be', 'at', 'bat', 'ant', 'cat', 'dog', 'aardvark']) 
list(filterObject)
Out[41]:
['a', 'at', 'ant', 'aardvark']

5. More on filter

filter on non-list sequences

filter can be applied to non-list sequences.

In [42]:
def notVowel(c):
    return c not in 'aeiou'
In [43]:
filterObject = filter(notVowel,'facetiously') # test filter on a string
list(filterObject)
Out[43]:
['f', 'c', 't', 's', 'l', 'y']
In [44]:
def isEven(n):
    return n % 2 == 0
In [45]:
filterObject = filter(isEven, (1,2,3,4,5)) # test filter on a tuple
list(filterObject)
Out[45]:
[2, 4]