Tuples and Lists¶

A collection that a for loop can step through, one element at a time, is called an iterable. The list and the NumPy array (np.ndarray) are both iterables. In this lab, we introduce the tuple, set, and dict iterables and describe which tasks each type of iterable is best suited for.

Tuples¶

A tuple, similar to a list, is an ordered collection of items. Tuples are usually created with parentheses with items separated by commas. Tuples support indexing and slicing with the same syntax as lists.

x = (3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5)

print(x)
print(x[2])    # Extract a single item.
print(x[3:7])  # Extract several items as a tuple.

(3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5)
4
(1, 5, 9, 2)

Unlike lists, tuples are immutable, meaning they cannot be changed after they are created.

x[4] = 100

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[2], line 1
----> 1 x[4] = 100

TypeError: 'tuple' object does not support item assignment

An iterable can be transformed into a tuple by calling tuple() like a function.

y = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
print(y)

z = tuple(y)  # Make a new tuple containing each item of `y`.
print(z)

[3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
(3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5)

# Strings are iterables, and so can be converted to tuples.
print(tuple("hello, world!"))

('h', 'e', 'l', 'l', 'o', ',', ' ', 'w', 'o', 'r', 'l', 'd', '!')

Tuples are also created by comma-separated expression lists, even when the expressions are not surrounded by parentheses. This means that a function with multiple return values is really just returning a single tuple.

w = 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5
print(w)

(3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5)

def pm1(a):
    return a - 1, a + 1  # Same as `return (a - 1, a + 1)`.


print(pm1(5))

(4, 6)

Parentheses

Parentheses have three common uses in Python:

Calling functions, as in f(2, 3). This is the meaning when parentheses follow a callable expression (f in this case).
Grouping tuple items, as in (2, 3). This is the meaning when parentheses do not follow a callable expression and have at least one comma between them.
Grouping expressions, as in (2 * (4 - 1)), which evaluates to 6. The parentheses do not follow a name and do not have any commas between them.

This means that (2 + 3) evaluates to the number 5, while (2 + 3,) is the single-entry tuple (5,). The exception is that () creates an empty (zero-item) tuple.

Quick Check

Consider the following line of code. What indexing syntax can be used to extract the 4 from x?

x = ((1 + 2, (4,), 8),)

Lists¶

So far, we have only created lists by writing comma-separated values explicitly within square brackets.

squares = [0, 1, 4, 9, 16]
print(squares)

[0, 1, 4, 9, 16]

Other iterables can be transformed into lists by calling list() like a function.

x = (3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5)
print(x)

y = list(x)  # Make a new list containing each item of `x`.
print(y)

(3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5)
[3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]

The built-in function sorted() transforms an iterable into a list and sorts it.

y = sorted(x)
print(y)

[1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

Lists are often built iteratively, adding one item at a time, or by otherwise modifying an existing list one operation at a time. The list data type makes this possible through its methods.

List Methods¶

A method is a function that is attached to a particular object or type of object. Given an object x, the syntax x.method() calls the method method() defined for the object x, if such a method exists. Methods are often used to modify the objects to which they are attached or to report characteristics of those objects. The type of object determines which methods are available.

The list class has the following methods. In this table, x represents a list.

Method	Description
`x.append(item)`	Append `item` to the end of `x`.
`x.clear()`	Remove all items from `x`.
`x.copy()`	Copy `x` into a new list.
`x.count(item)`	Return the number of times `item` occurs in `x`.
`x.extend(other)`	Append every item of the iterable `other` to the end of `x`.
`x.index(item)`	Return the first index of `item` in `x`.
`x.insert(index, item)`	Insert `item` into `x` at position `index`, shifting later elements over.
`x.remove(value)`	Remove the first occurrence of `value` from `x`.
`x.pop()`	Remove and return the last item in `x`.
`x.pop(index)`	Remove and return the item in `x` at position `index`.
`x.reverse()`	Reverse `x` in place.
`x.sort()`	Sort `x` in place, from smallest value to largest.

# Start with an empty list.
x = []
print(x)

[]

# Append a few items.
x.append(7)
x.append(-3.14)
print(x)

[7, -3.14]

# Insert an item at the front of the list.
x.insert(0, 4000)  # "Make 4000 the item at index 0"
print(x)

[4000, 7, -3.14]

# Sort the list in place.
x.sort()
print(x)

[-3.14, 7, 4000]

# Remove a specified item.
x.remove(7)
print(x)

[-3.14, 4000]

# Remove the item at the front of the list.
x.pop(0)
print(x)

[4000]

In Place Operations

Many of the list methods in the above table modify the list “in place” without creating a copy, then return None. A common mistake is writing x = x.append(...), which throws away the list and replaces it with None.

x = [3, 1, 4, 1, 5, 9]
x = x.append(2)
print(x)

None

Constructing Lists Sequentially¶

A common pattern for constructing lists is to start with an empty list, then use append() or insert() within the body of a loop.

squares = []
for i in range(10):
    squares.append(i**2)

print(squares)

[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

Quick Check

What is the output of the following code? What does the output represent mathematically?

total = 0
cumsum = []
for k in range(19):
    total += k
    cumsum.append(total)

print(cumsum)

Problem 1

This is a continuation of Lab 3 Problem 6.

Consider the sequence of numbers defined through the following iteration:

\[\begin{split} x_{k+1} = \begin{cases} \frac{1}{2}x_k &\text{if}~x_k~\text{is even,} \\ 1 + 3x_k &\text{if}~x_k~\text{is odd.} \end{cases} \end{split}\]

For example, if \(x_0 = 3\), then the sequence is \((3, 10, 5, 16, 8, 4, 2, 1)\). The Collatz conjecture is the claim that no matter which positive integer is chosen as the starting point \(x_0\), the sequence will always reach \(1\) eventually. No one has proven that this is always the case, but a counterexample has yet to be discovered.

Write a function named collatz_sequence() that accepts a positive integer \(x_0\) and returns a list containing every term of the Collatz sequence \((x_0,x_1,x_2,\ldots,x_n)\), in order, starting at \(x_0\) and ending at \(x_n = 1\), where \(x_n\) is the first occurrence of \(1\) in the sequence.

Reminder: In the even case, use integer division //, not float division /.

Test Cases

print(collatz_sequence(1))
print(collatz_sequence(3))
print(collatz_sequence(27))

[1]
[3, 10, 5, 16, 8, 4, 2, 1]
[27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1]

Problem 2

The Fibonacci sequence is defined by the iteration

\[\begin{split} x_k = \begin{cases} 1 &\text{if}~k = 0~\text{or}~k=1,\\ x_{k-1} + x_{k-2} &\text{if}~k \ge 2. \end{cases} % x_0 = x_1 = 1, % \qquad\textrm{and for}~k\ge 1,\quad % x_{k+1} = x_{k} + x_{k-1}. \end{split}\]

In other words, after the first two terms, every term in the sequence is the sum of the two terms that immediately precede it.

Write a function named fibonacci() that accepts a positive integer \(n\) and returns a list containing the first \(n\) terms of the Fibonacci sequence, in order.

Test Cases

print(fibonacci(4))
print(fibonacci(14))
print(len(fibonacci(150)))

[1, 1, 2, 3]
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
150

List Comprehensions¶

The pattern of starting with an empty list, entering a loop, and appending an item on every pass is so common that Python has a dedicated shorthand for it, called a list comprehension. The syntax is [expression for item in iterable], where expression typically depends on item.

# Full for loop.
squares = []
for i in range(10):
    squares.append(i**2)
print(squares)

# Equivalent list comprehension.
print([i**2 for i in range(10)])

[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

print([2 * s for s in squares])

[0, 2, 8, 18, 32, 50, 72, 98, 128, 162]

A list comprehension can also filter which items are included by adding an if clause at the end.

# Full for loop.
even_squares = []
for i in range(10):
    if i % 2 == 0:
        even_squares.append(i**2)
print(even_squares)

# List comprehension: only include items that satisfy the `if` conditions.
print([i**2 for i in range(10) if i % 2 == 0])

[0, 4, 16, 36, 64]
[0, 4, 16, 36, 64]

Comprehension or Loop?

Anything written as a list comprehension can also be written as an explicit loop with append(). The reverse is true for loops that follow this pattern. Use whichever is easier to read; a comprehension with a long expression or several conditions can become harder to follow than the equivalent loop.

Problem 3

For \(0 < x \le 2\), the natural logarithm \(\ln(x)\) can be written as the infinite series

\[\begin{split} \begin{aligned} \ln(x) &= \sum_{k=1}^{\infty} \frac{(-1)^{k-1}}{k}(x - 1)^k \\ &= (x - 1) - \frac{1}{2}(x - 1)^2 + \frac{1}{3}(x - 1)^3 - \frac{1}{4}(x - 1)^4 + \cdots \end{aligned} \end{split}\]

This is called the Taylor series for \(\ln(x)\) centered around \(x = 1\). Although a computer cannot add up infinitely many numbers (it would take infinitely many computations), the sum can be approximated by adding together the first several terms.

Write a function named natural_log() that accepts a number \(x\) and a positive integer \(n\) and returns an estimate for \(\ln(x)\) using the first \(n\) terms of the above series. That is, compute the number

\[ \sum_{k=1}^{n} \frac{(-1)^{k-1}}{k}(x - 1)^k = (x - 1) - \frac{1}{2}(x - 1)^2 + \cdots + \frac{(-1)^{n-1}}{n}(x - 1)^n, \]

which will be close to the true value of \(\ln(x)\) if \(x\) is near \(1\).

Test Cases

This test case prints the value of natural_log(x, n) and compares it to NumPy’s np.log(x).

import numpy as np

x = 1.2
for n in [5, 10, 20, 25]:
    lnx = natural_log(x, n)
    print(lnx, abs(np.log(x) - lnx))

18233066666666664 9.109872712048661e-06
18232155522031743 1.5736371650199033e-09
1823215567939545 8.326672684688674e-17
1823215567939546 0.0

As \(n\) increases, the approximation approaches and eventually agrees (up to machine precision) with np.log(x).