Python Data Abstractions

Python Data Abstractions

Collection - An Object identifying a group of elements, which may be ordered and unordered.
Iterable - An ordered collection used often in for loops, capable of returning one element at time.
Sequence - An iterable, ordered collection, with fast access to next elements.

Collections are either:
Mutable (identities changeable in place)
Immutable (identities unchangeable)


Builtin Examples:
Lists (sequence, ordered, iterable, mutable)
Tuples (sequence, ordered, iterable, immutable)
Dictionaries (non-sequence, unordered, iterable, mutable)
Strings (sequence, ordered, iterable, immutable)


Dictionaries
• Unordered, Iterable, Mutable Collection
• Keys in dictionaries and elements in sets:
• Keys can’t be mutable values, such as lists and dictionaries - they mush be 'hashable' like strings.
• Must be unique, i.e., no duplicates
• If you want to associate multiple values with a key, store them all in a sequence (list) value, e.g.:
parity = {'odds': [1, 3, 5], 'evens': [2, 4, 6]}

Dictionary as a collection of counters
Dictionaries are used as lookup tables since the efficiently map keys to values. A popular use is when keys are mapped to counter values. We call such a dictionary a 'histogram'.
Here is what the code might look like to create a histogrm, when given an iterable collection s:

def histogram(s):
    d = dict()
    for c in s:
        if c not in d:
            d[c] = 1
        else:
            d[c] += 1
    return d

Here’s how it works:

>>> h = histogram('brontosaurus')
>>> h
{'a': 1, 'b': 1, 'o': 2, 'n': 1, 's': 2, 'r': 2, 'u': 2, 't': 1}


The Changing Identity of Data
Programs often exhibit brittleness when data models change over time. Programmers need to carefully consider whether and how a data model is affected over time. Consider Suits in Playing Cards: Playing cards were invented in China, perhaps around the 9th century, and have evolved over time. An early deck had three suits, which corresponded to denominations of money.

>>> chinese = ['coin', 'string', 'myriad']  # A list literal
>>> suits = chinese                         # Two names refer to the same list

As cards migrated to Europe (perhaps through Egypt), only the suit of coins remained in Spanish decks (oro).

>>> suits.pop()             # Remove and return the final element
'myriad'
>>> suits.remove('string')  # Remove the first element that equals the argument

Three more suits were added (they evolved in name and design over time),

>>> suits.append('cup')              # Add an element to the end
>>> suits.extend(['sword', 'club'])  # Add all elements of a sequence to the end
and Italians called swords spades.

>>> suits[2] = 'spade'  # Replace an element
giving the suits of a traditional Italian deck of cards.

>>> suits
['coin', 'cup', 'spade', 'club']

The French variant used today in the U.S. changes the first two suits:

>>> suits[0:2] = ['heart', 'diamond']  # Replace a slice
>>> suits
['heart', 'diamond', 'spade', 'club']
Methods also exist for inserting, sorting, and reversing lists. All of these mutation operations change the value of the list; they do not create new list objects.

Sharing and Identity. Because we have been changing a single list rather than creating new lists, the object bound to the name chinese has also changed, because it is the same list object that was bound to suits!

>>> chinese  # This name co-refers with "suits" to the same changing list
['heart', 'diamond', 'spade', 'club']
This behavior is new. Previously, if a name did not appear in a statement, then its value would not be affected by that statement. With mutable data, methods called on one name can affect another name at the same time.

Lists can be copied using the list constructor function. Changes to one list do not affect another, unless they share structure.

>>> nest = list(suits)  # Bind "nest" to a second list with the same elements
>>> nest[0] = suits     # Create a nested list
According to this environment, changing the list referenced by suits will affect the nested list that is the first element of nest, but not the other elements.

>>> suits.insert(2, 'Joker')  # Insert an element at index 2, shifting the rest
>>> nest
[['heart', 'diamond', 'Joker', 'spade', 'club'], 'diamond', 'spade', 'club']
And likewise, undoing this change in the first element of nest will change suit as well.

>>> nest[0].pop(2)
'Joker'
>>> suits
['heart', 'diamond', 'spade', 'club']

Mutation through Function Calls
A function can change the value of any object in its scope
A function’s scope also includes parent frames
>>> four = [1, 2, 3, 4]
>>> len(four)
4
>>> mystery(four)
>>> len(four)
2

def mystery(s):
    s.pop()
    s.pop()
#OR
def mystery(s):
    s[2:] = []

>>> four = [1, 2, 3, 4]
>>> len(four)
4
>>> another_mystery()   # No arguments!
>>> len(four)
2

def another_mystery():
    four.pop()
    four.pop()

Identity vs Equality
• Because mutable values can change, the notion of equality is not as strong anymore
• Two immutable values are always equal or always unequal to each other
• Two mutable values can be sometimes equal and sometimes unequal to each other
• Each value also has an identity, which cannot change
• A list still has the same identity even if we change its contents
• Conversely, two lists, even if they contain the same
elements, never have the same identity

Identity vs Equality
Identity
<exp0> is <exp1>
evaluates to True if both <exp0> and <exp1> evaluate to the same object

Equality
<exp0> == <exp1>
evaluates to True if both <exp0> and <exp1> evaluate to equal values
Identical objects are always equal values


>>> def f(s=[]):
...    s.append(3)
...    return len(s)
...
>>> f()
1
>>> f()
2
>>> f()
3

Summary
• Mutable values such as lists and dictionaries have state and can be changed
• This can be useful in writing programs that are more efficient and more understandable
• Immutable values cannot be changed after they are created
• This is simpler and safer: immutable values that are equal (or unequal) will always be equal (or unequal)
• Knowing when and where to use both types of values is an important part of being a good programmer!

Quiz Question 1

Define if_this_not_that, which takes a list of integers i_list, and an integer this, and for each element in i_list if the element is larger than this then print the element, otherwise print that.

def if_this_not_that(i_list, this):
    """
    >>> original_list = [1, 2, 3, 4, 5]
    >>> if_this_not_that(original_list, 3)
    that
    that
    that
    4
    5
    """

Quiz Question 2: Replace All

Given a dictionary d, replace all occurrences of x as a value (not a key) with y.

def replace_all(d, x, y):
    """
    >>> d = {'foo': 2, 'bar': 3, 'garply': 3, 'xyzzy': 99}
    >>> replace_all(d, 3, 'poof')

    >>> d == {'foo': 2, 'bar': 'poof', 'garply': 'poof', 'xyzzy': 99}
    True
    """