Introduction to Collections

Collection Types

Python has a surprisingly large number of built-in and auxiliary collection types. Collections are objects that contain zero or more member objects, often called elements. There are 3 main categories of collection: sequences, mappings, and sets.

Let's recap the types table from the Data Types chapter. We've reproduced a portion of the table below:

Type	Class	Category	Kind	Mutable
ranges	range	sequences	Non-primitive	No
tuples	tuple	sequences	Non-primitive	No
lists	list	sequences	Non-primitive	Yes
dictionaries	dict	mappings	Non-primitive	Yes
sets	set	sets	Non-primitive	Yes
frozen sets	frozenset	sets	Non-primitive	No

As you can see, the collections fall into several categories: sequences, mappings, and sets.

Some collections are mutable; others are immutable. Keeping them straight takes some practice; be patient. In particular, lists and tuples differ only in that lists are mutable; tuples are not. The set collections differ similarly: sets are mutable; frozen sets are not.

We've met all these types earlier in this book. In this lesson, we'll explore them in depth.

What are Sequences?

Sequences are types that maintain an ordered collection of objects (also: elements or values) that can be indexed by whole numbers. Ordered collections are collections organized in some sequence: a first element, a second element, a third element, and so on. Indexed sequences associate every object member with a whole number (0, 1, 2, etc.) that can be used to access or modify that object. The built-in sequences (ranges, lists, and tuples) always have the first object at index 0, the second at index 1, and so on.

letters = ['a', 'b', 'c']
print(letters[0])         # a (first element)
print(letters[1])         # b (second element)
print(letters[2])         # c (third element)

Lists and tuples are heterogeneous; they may contain different kinds of objects, including other sequences:

my_list = [
    'May',
    2.99,
    {None, True, False},
    [1, 2, 3],
]

Ranges are homogenous; they always contain integers.

Strings are a form of sequence called a text sequence. They differ from ordinary sequences in several ways:

1. Strings are homogenous; all characters in a string are, um, characters.
2. Characters are not a distinct kind of object; they are merely strings of length 1.
3. A string's individual characters are not separate strings until you reference a character.
4. Strings are not actual collections since the characters inside the string aren't objects.

Bullet 3 merits an example, but it requires using Unicode. The Greek letter theta (θ) is a fine choice. Let's look at two snippets, one using a list and the other a string:

letters = ['a', 'b', 'θ', 'd', 'e']
char = letters[2]
print(char is letters[2])     # True

letters = 'abθde'
char = letters[2]
print(char is letters[2])     # False

Example 1 shows that letters[2] returns the object at index 2 of the letters list. Both char and letters[2] reference the same object, as shown on line 3.

However, in Example 2, the two characters are not the same object. They have the same value but are distinct objects.

We used θ to avoid interning, a topic we discussed earlier. Python would have interned any character from the extended ASCII character set, and both snippets would have returned True. By switching to a non-ASCII character, we could show that characters in a string aren't objects.

While there are differences, we can usually treat strings as ordinary sequences.

What are Sets?

Sets are types that maintain an unordered collection of unique objects (also called elements or members). Unlike sequences, sets cannot be indexed. Unordered means no well-defined order exists for the objects in a set. In fact, the sets {1, 2, 3} and {3, 1, 2} are equal since the order doesn't matter. By unique, we mean a set can not have duplicate members.

Python has two main built-in set types: sets and frozen sets. Regular sets are mutable; frozen sets are immutable. This is the only significant difference between the two:

letters = {'a', 'b', 'c'}
letters.add('d')
print(letters)
# {'a', 'b', 'c', 'd'} (order may differ)

frozen_letters = frozenset(letters)
frozen_letters.add('e')
# AttributeError: 'frozenset' object has no
# attribute 'add'

Sets and frozen sets, like Lists and tuples, are heterogeneous; they may contain different kinds of objects, including other hashable collections:

my_set = {
    'May',
    2.99,
    (None, True, False),
    range(5),
}

Python will ignore any attempt to add duplicate members to a set:

letters = {'a', 'b', 'c', 'b', 'a'}
print(letters)
# {'a', 'c', 'b'} (order may differ)

letters.add('c')
print(letters)
# {'a', 'c', 'b'} (order may differ)

Since Python 3.7, sets of integers sometimes seem to be ordered. For instance:

numbers = { 1, 2, 3, 4, 5 }
print(numbers)      # { 1, 2, 3, 4, 5 }

numbers = { 5, 3, 1, 2, 4 }
print(numbers)      # { 1, 2, 3, 4, 5 }

No matter how often you run that code, it prints both sets with the same ordered values. It's an illusion, however, produced by an implementation detail. The behavior isn't guaranteed: it's easy to construct sets of integers that are clearly unordered:

numbers = { 1, 2, 37, 4, 5 }
print(numbers)      # {1, 2, 4, 37, 5}

The order of the numbers you see may not match ours, but you will likely see that the numbers are no longer predictably ordered.

What are Mappings?

Mappings are types that maintain an unordered collection of key/value pairs (also called elements or members). Unlike sequences, mappings are accessed by their keys, which usually are not numbers. While Python has several mapping types, the only one we'll meet in this book is the dictionary or dict type.

Dicts have the following characteristics:

• Dicts are mutable.
• The keys in a dict must be unique. Trying to add a duplicate key to a dict merely replaces the existing key's associated value.
• Keys must be "hashable" values. We won't define "hashable" right now. However, hashable values are usually (not always) immutable. All built-in immutable types (numbers, strings, booleans, tuples, frozen sets, and None) are hashable and can be dict keys.
• The values in each key/value pair may be any object.

d = {'a': 1, (1, 3): 3, 1: 'x'}
print(d)         # {'a': 1, (1, 3): 3, 1: 'x'}
print(d['a'])    # 1
print(d[(1, 3)]) # 3
print(d[1])      # 'x'

d['a'] = 'A'
print(d)        # {'a': 'A', (1, 3): 3, 1: 'x'}

Since version 3.7, Python dicts maintain the insertion order of the pairs. Python guarantees it. Thus, you can iterate over the pairs in the same order they were inserted into the dictionary. However, this behavior doesn't fundamentally alter whether dicts are unordered collections. In practice, you should mentally think of dicts as unordered collections, but it's OK to rely on the ordering in contexts where the insertion order matters.

d = {'a': 1, (1, 3): 3, 1: 'x'}

del d['a']      # Deletes key/value pair 'a': 1
print(d)        # {(1, 3): 3, 1: 'x'}

d['a'] = 42
print(d)        # {(1, 3): 3, 1: 'x', 'a': 42}

Sequence Constructors

Most built-in Python data types let the programmer create new objects using literal values. Literals are great. However, you can also use special functions called constructors to create new objects. In fact, sometimes you can't use literals; you must use constructors to create ranges, frozen sets, and empty sets.

Let's examine the constructors used with collections.

String Constructor

The string constructor, str, has two basic formats, str() and str(something), where something is any Python object. Regardless of what you pass to str, it returns a string. For instance:

str()            # returns '' (empty string)
str('abc')       # returns 'abc'
str(42)          # returns '42'
str(3.141592)    # returns '3.141592'
str(False)       # returns 'False'
str(None)        # returns 'None'
str(range(3, 7)) # returns 'range(3, 7)'
str([1, 2, 3])   # returns '[1, 2, 3]'
str(int)         # returns "<class 'int'>"
str(list)        # returns "<class 'list'>"

class Person: pass
str(Person())
# returns "<__main__.Person object at 0x1006d21e0>"

In most cases, the values returned by str give a good idea of the original value. However, the last 6 lines show that the return value isn't always helpful. This is especially true with custom types like the Person class above (we'll learn about custom types in the OO Python book). You can fix this issue with custom types, but we won't discuss that until later in the Core Curriculum.

Range Constructor

The range constructor comes in 3 forms:

• range(start, stop, step)

  This constructor generates a sequence of integers between start and stop - 1 with an increment of step between each consecutive integer. You can use a negative step to generate a sequence in reverse order. In this case, the range ends at stop + 1. For instance:

  r = range(5, 12, 2)
  print(list(r))            # [5, 7, 9, 11]
  
  r = range(12, 8, -1)
  print(list(r))            # [12, 11, 10, 9]
  
  r = range(12, 5, -2)
  print(list(r))            # [12, 10, 8, 6]
  

  You can create empty ranges by giving values where start >= stop when step is positive or start <= stop when step is negative. Empty ranges are often bugs.

  r = range(5, 5, 1)
  print(list(r))           # []
  
  r = range(5, 7, -1)
  print(list(r))            # []
  

• range(start, stop)

  When you omit the step argument, Python uses a default value of 1. Hence, range(start, stop) is identical to range(start, stop, 1).

• range(stop)

  When you omit the start argument, Python uses a default value of 0 for start. Hence, range(stop) is identical to range(0, stop, 1).

Ranges are lazy sequences: they don't create any element values until your program needs them. This is why we use list(r) above; without it, print(r) prints something like range(5, 12, 2), which may not be helpful. You can also use the tuple constructor to do the same thing. The set and frozenset constructors also work, but the sets may not be in the same order.

The List, Tuple, Set, and Frozen Set Constructors

Lists, tuples, sets, and frozen sets share two common constructor forms:

• list() or list(iterable)
• tuple() or tuple(iterable)
• set() or set(iterable)
• frozenset() or frozenset(iterable)

The constructors with no arguments create an empty list, tuple, set, or frozen set, as appropriate: a sequence or set with no members.

The constructors that take an iterable argument expect an object that Python can iterate: an iterable. From the built-in types, the iterables include all sequences, strings, sets, and mappings. (Note that iterating a mapping iterates the mapping's keys.) Thus, you can use these constructors to convert lists to tuples, tuples to sets, strings to lists, and so on:

my_str = 'Python'

my_list = list(my_str)
print(my_list)  # ['P', 'y', 't', 'h', 'o', 'n']

my_tuple = tuple(my_list)
print(my_tuple) # ('P', 'y', 't', 'h', 'o', 'n')

my_set = set(my_tuple)
print(my_set)   # {'t', 'o', 'n', 'h', 'P', 'y'}

You can also use these constructors to duplicate a collection:

my_list = [5, 12, 2]
another_list = list(my_list)

print(my_list)                          # [5, 12, 2]
print(another_list)                     # [5, 12, 2]

print(my_list == another_list)          # True
print(my_list is another_list)          # False

As you can see in lines 4, 5, and 7, the lists are identical. However, line 8 shows that the list objects are not the same object.

Let's look at a more complex example involving nested lists:

my_list = [[1, 2, 3], [4, 5, 6]]
another_list = list(my_list)

print(my_list)                          # [[1, 2, 3], [4, 5, 6]]
print(another_list)                     # [[1, 2, 3], [4, 5, 6]]

print(my_list == another_list)          # True
print(my_list is another_list)          # False
print(my_list[0] is another_list[0])    # True
print(my_list[1] is another_list[1])    # True

In this case, we can see from lines 4, 5, and 7 that the lists have the same values, and from line 8, we can see that they are different objects. Strangely, in lines 9 and 10, we can see that their elements are the same objects. That's because the list constructor performs what is known as a shallow copy. In a later chapter, we'll discuss shallow and deep copies and what is happening here. For now, remember that nested collections are subject to shallow copies. That's often fine. However, it can lead to problems that are difficult to diagnose.

Passing a string to any of these constructors causes it to iterate over the characters in the string. It places each character in a separate element of the resulting collection:

print(tuple('Python'))
# ('P', 'y', 't', 'h', 'o', 'n')

Summary

Python has a rich variety of collections for storing and manipulating data. You'll see collections in almost all real-world programs; nearly every useful program uses them. We'll continue to explore them in the next chapter.