Every Python value has a class that determines its type of value
Same class, same behavior
Native data types: integers (int), real numbers (float), complex numbers
(complex)
Literals: expressions that evaluate to values of native types
There are built-in functions and operators to manipulate values of native
types
Floats are represented in Python as a “floating point”
int objects represent integers exactly
float objects represent a wide range of fractional numbers, but not all
can be represented exactly, and there are minimum and maximum values →
float values should be treated as approximations
Programmers must define most values’ types other than native ones through
means of combination and abstraction
Reading Ch. 2.3: Sequences (15-16, 21, 23/06/22)
Sequence: an ordered collection of values
A fundamental abstraction in computer science
A collection of behaviors that are shared among several different types of
data
Length
len(<sequence>)
Element selection
<sequence>[index]
Membership
in/not in operator
Slicing
<sequence>[<starting index>: <ending index >: <step size>]
Addition and multiplication do not add or multiply elements, but instead,
combine and replicate the sequences
List: native data type, sequence, arbitrary length
Iteration through a sequence
for <name> in <expression>:
<suite>
Evaluate <expression>, must yield an iterable value
Bind <name> to corresponding value
Execute <suite>
As such, <name> will be bound to the last element after the for
statement has been executed
Sequences are iterable values
Sequence unpacking: the pattern of binding multiple names to multiple
values in a fixed-length sequence
Range: a built-in sequence that represents a range of integer
range(1, 10) # Includes 1, not 10
Calling the list constructor on a range evaluates to a list
list(range(x, y))
for _ in range(3): # _ does not appear in the suite, runs from 0 → 2
Sequence processing operations:
List comprehensions: evaluate a fixed expression for each element in a
sequence and store the values in a result sequence or select a subset of
values that satisfy some condition
[<map expression> for <name> in <sequence expression> if <filter
expression>]
Aggregation: aggregate all values in a sequence into a single value
(sum, min, max, all)
The richness of an abstraction (how many behaviors) has consequences.
Additional behaviors can be helpful, but satisfying the requirements of a
rich abstraction with a new data type becomes harder. They also take users
longer to learn
Most user-defined abstractions should be kept as simple as possible
Strings: sequences of characters
Unlike other programming languages, Python characters do not have a
separate type, they are strings of length 1
String coercion: a string can be created from any Python object by calling
the str constructor on an object value → constructing descriptive strings
from objects of various types
Closure property of a data type: The result of the combination of data
values can be combined using the same method → create hierarchical
structures
Trees: A tree has a root label and a list of branches
Each branch is a tree
A tree with zero branches is called a leaf
Each location in a tree is called a node, each has a label
One node can be the parent/child of another
A tree constructor, label and branches selectors, is_tree and is_leaf
validators
Binary trees have two branches
Linked Lists: a sequence constructed from nested pairs
A pair contains the first element of the sequence and the rest. The second
element is also a linked list
A linked list can be ‘empty’
A linked list constructor, first and rest selectors, and is_link validator
Data abstraction: A methodology by which functions enforce an
abstraction barrier between representation and use. These two parts are
connected by a set of functions that implement abstract data in terms of the
concrete representation
Example: Implement rational numbers (abstract data) using the built-in
list type (concrete representation)
Wishful thinking: assume that we already have some functions with known
input and output, we can use those function names in the implementation of
other functions before even actually implementing them
Abstraction barriers: functions are called by a higher level and
implemented using a lower level of abstraction. A violation occurs when part
of the program that can use a higher-level function instead uses a function
in a lower level.
Make programs easier to maintain and modify
In general, abstract data can be expressed using a collection of selectors,
constructors, and some behavior conditions.
Lecture 12: Data Abstraction (21/06/22)
Data abstraction uses selectors and constructors to define behavior
If behavior conditions are met, then the representation is valid
Dictionaries: unordered collections of key-value pairs
{<key>: <value>,…}
<dictionary name>[<key>] → <value>
<dictionary name>.keys()
<dictionary name>.values()
<dictionary name>.items()
dict() → Constructor constructs a dictionary
<dictionary name>.get(<key>, <default value>) → Returns <default
value> if there is no value associated with <key>
{<key map expression>:<value map expression> for <name> in
<sequence expression> if <filter expression>} → Dictionary
comprehension
Cannot use list and dictionary as keys or any mutable type
Two keys cannot be equal, there can be at most one value for a key
Lecture 13: Trees (23/06/22)
Tree processing uses recursion
Processing a leaf is often the base case of a tree processing function
Examples: Function that counts leaves, functions that act based on the
leaves’ labels,…
The recursive case typically makes a recursive call on each branch,
then aggregates
A function that creates a tree from another tree is typically recursive
Discussion 04: Python Lists, Tree Recursion (15/07/22)
Guerrilla 01: Python Lists, Recursion, Tree Recursion (15/07/22)