List comprehension

A list comprehension is a construct available in some computer programming languages that allows the creation of lists from other lists. It uses set building notation to allow this functionality in an intuitive and elegant way.

Creating lists from other lists is useful in computer programming. This is espeically true when operating on, analyzing, or transforming data. You can take a list of data values and quickly output some modified version of that data.

Set building notation is a way of describing new sets as a relationship to an exisitng set. This relationship can have function by which the incoming set is changed and a predicate that filters the incoming set.

List comprehensions are used in a variety of languages. They are most often found in functional languages like Haskell and Scala and in scripting languages like Python and Perl. They are typically faster than other methods of building lists, such as for loops. Plus, they are more compact in their notation, typically easier to read, and more elegant.

An example of a list comprehension in Python:

1
2
3
4

>>> old_list = [1,2,3,4]
>>> new_list = [2*x for x in old_list if x >= 2]
>>> new_list
[4, 6, 8]

Here is an example of set builder notation:

\[S_{new} = \left\{ x^2 | \: x \: \epsilon \: S_{old} , x \gt 5\right\} .\]

Set builder notation takes in an old set, \(S_{old}\), to creates a new set, \(S_{new}\). This new set will take all numbers greater than 5 from the old set, square them, and add them to the new set.

There are four parts. The output expression, which here is \(x^2\), defines the function performed on the incoming element before it is added to the new set. The variable, \(x\), defines the variable name so that it can be notated in other parts. The input set, \(S_{old}\), defines where we are getting the elements from. The predicate, \(x \gt 5\), defines any logical parameter by which input elements are filtered, and it is typically optional. Any element from the input set that evaluates to true in the predicate will be included in the output set.

The above notation, translated into Python, looks like this

1
2
3
4

>>> old_list = [1, 5, 8, 10, -3, 14]
>>> new_list = [x^2 for x in old_list if x > 5]
>>> new_list
[10, 8, 12]

Let S be the open unit circle, i.e, the set of all points that are within a distance of one from the origin.

\[S = \left \{ (x,y) \mid (x,y) \in \mathbb{R}^2, x^2 + y^2 < 1 \right \}\]

Haskell is a popular functional programming language. Because Haskell is driven by mathematical inspirations, especially lambda calculus and category theory, a mathematician would be much more comfortable making list comprehensions in Haskell.

Generate a list of all names that are constructible as a combination of the following first names and surnames:

1 2	first_names = ["Calvin", "Krishna", "Kaboobly"] last_names = ["Lin", "Ar", "Do", "Carrots"]

---

The following code does the job pretty well:

1	[first_name ++ " " ++ last_name | first_name <- first_names, last_name <- last_names]

An added advantage is that, because Haskell use lazy evaluation, one can make infinite sets too. Lazy evaluation is a programming evaluation strategy that delays the evaluation of an expression until it is needed.

Write a Haskell representation for the set of all natural squares. Use take to get the first 10 elements of that list.

---

The following is a good definition of the set of natural squares:

1	squares = [x^2 | x<-[1..]]

Over here, [1..] represents the set of natural numbers.

We could use take to get the first few integers from it this way:

1	take 10 squares

Obviously, one can add one or more clauses seperated by commas for further filtering.

The following is a nice way to represent the list of cubes of odd natural numbers:

1	odd_cubes = [x^3 | x<-[1..], odd x]

List comprehensions in Python are also useful and efficient. They consist of an expression, followed by a for loop that iterates through the generator list followed by zero or more fors, followed by one or more boolean expressions, if necessary, for filtering.

Here is how one could evaluate the first 10 perfect squares using list comprehensions:

1	[x**2 for x in xrange(1,11)]

---

We could weed out the even squares this way:

1	[x**2 for x in xrange(1,11) if x%2]

---

Let us do the names example from the Haskell section in Python:

1 2 3 4 5

>>> first_names = ["Calvin", "Krishna", "Kaboobly"] >>> last_names = ["Lin", "Ar", "Do", "Carrots"] >>> combined_names = [ first_name + " " + last_name for first_name in first_names for last_name in last_names] >>> combined_names ['Calvin Lin', 'Calvin Ar', 'Calvin Do', 'Calvin Carrots', 'Krishna Lin', 'Krishna Ar', 'Krishna Do', 'Krishna Carrots', 'Kaboobly Lin', 'Kaboobly Ar', 'Kaboobly Do', 'Kaboobly Carrots']

In Python, list comprehensions are generally more desirable for list creation than other methods, such as loops. Here's how one one might make a list of numbers 1 through 10 if they are using loops in Python.

1
2
3
4
5
6

>>> nums = []
>>> for x in range(1, 11):
...   nums.append(x)
... 
>>> nums
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

And here's that same process using list comprehensions.

1
2
3

>>> nums = [x for x in range(1, 11)]
>>> nums
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Clearly, using list comprehensions uses less code (which is always a good thing). However, you may be surprised to learn that it's also faster.

Example Question

Write a list comprehension in Python that creates a list of numbers between 1 and 100 that are divisible by 7 or divisible by 9.

Show Answer

This can be done by chaining together a string of predicates using boolean logic in the list comprehension.

1 2	>>> [x for x in range(1, 101) if x % 7 == 0 or x % 9 == 0] [7, 9, 14, 18, 21, 27, 28, 35, 36, 42, 45, 49, 54, 56, 63, 70, 72, 77, 81, 84, 90, 91, 98, 99]

Some languages offer other sorts of comprehensions that apply to more data structures than just lists.

Python, for example, offers set comprehensions and dictionary comprehensions. These constructs perform the same operations on their respective data structures as list comprehensions.

Sets are a data structure that do not allow duplicate values. An example of a set comprehension in Python is below.

1
2
3
4

>>> old_set = {1, 3, 4, 7, 3, 9, 2}
>>> new_set = {x for x in old_set if x != 2}
>>> new_set
set([1, 3, 4, 9, 7])

Dictionaries are the mapping constructs of Python. They map a key to value using a hash table. An example of a dictionary comprehension in Python is below.

1
2
3
4

>>> old_list = ['a', 'b', 'c', 'd', 'e', 'f']
>>> new_dict = {key: value for key, value in enumerate(old_list) if key != 2}
>>> new_dict
{0: 'a', 1: 'b', 3: 'd', 4: 'e', 5: 'f'}

This is a multi-part problem in Python. First, create a list of lower case characters from 'a' to 'g' using a list comprehension.

Next, make a dictionary mapping a character in that list to a number. The mapping should be 'a': 0, 'b': 1, ... , 'g': 6.

Finally, make a new list that includes the (key, value) pair from the dictionary only if the value is even. If the value is not even, append ths string "ODD" to the list. This final list should be the same length as the initial list.

Hint 1:

Show Hint 1

You can make a list of characters in python by casting to the string type from the integer type.

1 2	>>> [chr(i) for i in xrange(97, 100)] ['a', 'b', 'c']

Hint 2:

Show Hint 2

You can string boolean expressions together in a list comprehension, and that includes if/else statements. So, you can write something like this in python

1 2 3

>>> nums = [1, 5, 9] >>> [x if x > 6 else x*2 for x in nums] [2, 10, 9]

---

Show Answer

1 2 3 4 5 6 7 8 9

>>> part1 = [chr(i) for i in xrange(97, 104)] >>> part1 ['a', 'b', 'c', 'd', 'e', 'f', 'g'] >>> part2 = {value: key for key, value in enumerate(part1)} >>> part2 {'a': 0, 'c': 2, 'b': 1, 'e': 4, 'd': 3, 'g': 6, 'f': 5} >>> part3 = [key if part2[key] % 2 == 0 else "ODD" for key in part2] >>> part3 ['a', 'c', 'ODD', 'e', 'ODD', 'g', 'ODD']