<jupyter_start><jupyter_text>List comprehensions in PythonPython offers a convenient way to handle iterative structures (such as lists, set or dictionaries).  It is considered good practice to be able to manipulate them fluently. Let's have a look why! Head-first into the topic!In Python 3, the `range` keyword does not provide a list but a different structure that can easily be transformed into a list.<jupyter_code>range(10)
type(range(10))  # this is not a list!
list(range(10))  # but you can make a list out of it<jupyter_output><empty_output><jupyter_text>The key point about this notation is performance: when you write `range(10000)`, you do not create a list of size 10000, but a structure that will give you a new integer each time you go through a loop.In that perspective, you may be comfortable with the following snippet of code:<jupyter_code>for i in range(10):
    print(i, end=" ")<jupyter_output><empty_output><jupyter_text>Now, let's say we want to compute $x \mapsto 2\cdot x$ for each element of a given list (resp. range).  Let us compare the two following ways of writing it.<jupyter_code>a = range(1000000)
%%time
new_list = [2 * x for x in a]
%%time
new_list = []
for x in a:
    new_list.append(x)<jupyter_output><empty_output><jupyter_text>Definition: Any syntax going like `[f(x) for x in array]` is referred to as list comprehension.  Important note: Besides being a more compact way to write things, list comprehension is also more efficient.The official [docs.python.org](https://docs.python.org/) mentions it quickly [here](https://docs.python.org/3/tutorial/datastructures.htmllist-comprehensions) but let's go through this more into details. List comprehensions are not only about listsList comprehensions are based on a Python specific data structure called a generator.  You can manipulate a generator with brackets (no bracket results in a `SyntaxError`).<jupyter_code>g = (str(i) for i in range(10))
type(g)<jupyter_output><empty_output><jupyter_text>You can construct any data structure that accept *iterable structures* with a generator.<jupyter_code>list(g)<jupyter_output><empty_output><jupyter_text>Note that the generator is now empty. You cannot build a second list from the same `g`:<jupyter_code>list(g)<jupyter_output><empty_output><jupyter_text>So let's go through different constructions: - the regular Python `list`:<jupyter_code># equivalent notations for lists
list(str(i) for i in range(10))
[str(i) for i in range(10)]<jupyter_output><empty_output><jupyter_text>- the regular Python `set`:<jupyter_code># equivalent notations for sets
set(str(i) for i in range(10))
{str(i) for i in range(10)}<jupyter_output><empty_output><jupyter_text>- even dictionaries (keyword `dict`) with the column character `:`<jupyter_code>dict((i, str(i)) for i in range(10))
{i: str(i) for i in range(10)}<jupyter_output><empty_output><jupyter_text>There are actually other useful constructions, e.g. `sorted` that builds a sorted list from a generator:<jupyter_code>[i * (-1) ** (i) for i in range(10)]
sorted(i * (-1) ** (i) for i in range(10))<jupyter_output><empty_output><jupyter_text>Building a `set` from the generator can also be useful as reflected on the following snippet:<jupyter_code>[i ** 2 for i in range(-5, 5)]
{i ** 2 for i in range(-5, 5)}<jupyter_output><empty_output><jupyter_text>You can also build there structures with more complex constructions.  Recall the `enumerate` and/or `zip` constructions:<jupyter_code>french = ["un", "deux", "trois", "cat", "sank"]
english = ["one", "two", "three", "four", "five"]

words = {i + 1: f for i, f in enumerate(zip(french, english))}
words<jupyter_output><empty_output><jupyter_text>Looping on a dictionary iterates on the keys:<jupyter_code>[str(s) for s in words]<jupyter_output><empty_output><jupyter_text>But you can also use the `dict.items()` method.  Here is an example to show there is “no” limit in how you can use list comprehensions.<jupyter_code>[
    [key, value[0], len(value[0]), value[1].upper(), len(value[1])]
    for key, value in words.items()
]<jupyter_output><empty_output><jupyter_text>Common loop patterns using list comprehensionsCheck the difference between a `zip` and a double loop construction:<jupyter_code>list(zip(french, english))
[[(x, y) for x in french] for y in english]
[(x, y) for x in french for y in english]<jupyter_output><empty_output><jupyter_text>Important note: Be aware of which of the two for loops iterates fasterYou can also add conditions within the list comprehension:<jupyter_code>[a for a in range(10) if a % 2 == 0]<jupyter_output><empty_output><jupyter_text>Exercice: Use list comprehension to generate a list of $(a, b, c)$ integers such that $a^2 + b^2 = c^2$.<jupyter_code>[
    (a, b, c)
    for a in range(1, 30)
    for b in range(a, 30)
    for c in range(b, 30)
    if a ** 2 + b ** 2 == c ** 2
]<jupyter_output><empty_output><jupyter_text>Similar functions in numpyPython loops are known to be expensive. List comprehensions help, but `numpy` takes a different approach by unfolding the loops using code written in C.<jupyter_code>import numpy as np
%%time
new_list = [2 * x for x in range(1000000)]
a = np.arange(1000000)
%%time
new_list = 2 * a<jupyter_output><empty_output><jupyter_text>Important note: Although you cannot write as much in numpy as you can with list comprehension (because of the combination with the if construct), numpy remains the faster option. * Nested comprehension may remind you the `meshgrid` function:<jupyter_code>z = [[(x + y) for x in range(10)] for y in range(5)]
z
a, b = np.meshgrid(np.arange(10), np.arange(5))
c = a + b
c<jupyter_output><empty_output><jupyter_text>* You can go through elements of a 2D array with the following constructs:<jupyter_code>[col[1] for col in z]
c[:, 1]<jupyter_output><empty_output><jupyter_text>Be careful though that `numpy` does not provide you a fresh copy of the array even if you create intermediate references.<jupyter_code>d = c[:, 0]
d *= 0
c<jupyter_output><empty_output><jupyter_text>Yet another implementation for this old academic problemSay we want to get all the prime numbers lesser than n.  List comprehension can be a comfortable way to compute the sieve of Eratosthenes.<jupyter_code>%%timeit
# First compute the non prime numbers
nope = [j for i in range(2, 8) for j in range(i * 2, 50, i)]
# Then build a new list not containing prime numbers
[x for x in range(2, 50) if x not in nope]<jupyter_output><empty_output><jupyter_text>Actually the following implementation with `sets` may be more space and time efficient:<jupyter_code>%%timeit
sieve = set(range(2, 50))
for i in range(2, 8):
    sieve -= set(range(2 * i, 50, i))
sieve<jupyter_output><empty_output><jupyter_text>Another way to build your own generatorsLet's recall the types of the structures we mentioned:<jupyter_code>type(range(10))
type(i for i in range(10))<jupyter_output><empty_output><jupyter_text>Python provides a `yield` keyword in order to let you write your own generator objects.  When the program hits a yield keyword:1. it *yields* the current value,2. then waits for the next iteration in a loop (see the `__next__` keyword),3. then re-enters the program where it was last interrupted. The [Syracuse suite](https://en.wikipedia.org/wiki/Collatz_conjecture) is a good study case for this programming style.  See in the `doctest` how we build the suite using the `list` constructor on a `generator` structure.<jupyter_code>def syracuse(n):
    """Computes the Syracuse suite.

    >>> list(p for p in syracuse(28))
    [28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
    """
    assert n > 0
    yield n
    while n != 1:
        if n & 1 == 0:
            n = n // 2
        else:
            n = 3 * n + 1
        yield n<jupyter_output><empty_output><jupyter_text>An interesting plot to draw is the length of the Syracuse list for all integers within a certain range.  See how confortable it can be to write it.<jupyter_code>import matplotlib.pyplot as plt
def length(iterable):
    """Length of a generator.

    The `len` keyword does not apply on generators.
    This makes the trick without expanding the list!
    """
    return sum(1 for _ in iterable)


# Note how we can pass a range to `plt.plot`, not necessarily a list
# Note the multi-level generator in the second part of the array
interval = range(1, 1000)
plt.plot(interval, [length(syracuse(i)) for i in interval], "r.")
[i for i in range(1, 50) if length(syracuse(i)) > 100]<jupyter_output><empty_output><jupyter_text>27 is the first integer when the Syracuse suite length exceeds 100.  We can pretty-print the suite with another kind of list comprehension.<jupyter_code>print(" ⇢ ".join(str(i) for i in syracuse(27)))
plt.plot(list(syracuse(27)))<jupyter_output><empty_output><jupyter_text>We can see the suite goes up to 9232 (!) before coming back (quite fast) down to `[4, 2, 1]`.  Another interesting plot shows the *height* of the suite for each integer. Important note: `max` is also a construction that accepts a generator as parameter!<jupyter_code>ax = plt.axes()
ax.set_yscale("log")
ax.set_yticks([1 << i for i in range(1, 17)])
ax.set_yticklabels([1 << i for i in range(1, 17)])

interval = range(1, 500)
ax.plot(interval, [max(syracuse(i)) for i in interval], "r.")<jupyter_output><empty_output><jupyter_text>A last interesting graph plots the height of a suite depending on its length.<jupyter_code>ax = plt.axes()
ax.set_yscale("log")
ax.set_yticks([1 << i for i in range(1, 17)])
ax.set_yticklabels([1 << i for i in range(1, 17)])

interval = range(1, 500)
ax.plot(
    [length(syracuse(i)) for i in interval], [max(syracuse(i)) for i in interval], "r."
)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.10887221137041225, 'fraction_numerical': 0.022617456564202734, 'mean_word_length': 5.20012746972594, 'pattern_counts': {'":': 0, '<': 125, '<?xml version=': 0, '>': 122, 'https://': 3, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '29', 'dir': 'jupyter-structured-clean-dedup', 'id': '157790', 'license': 'MIT', 'n_tokens_mistral': 3385, 'n_tokens_neox': 3145, 'n_words': 1228, 'path': 'notebooks/list_comprehensions.ipynb', 'repo_name': 'AntoineStevan/pyseminar', 'size': '9727'}