The most important thing to remember about lists is that a non-empty list s can be split into its first element s[0] and the rest of the list s[1:].

>>> s = [2, 3, 6, 4]
>>> s[0]
2
>>> s[1:]
[3, 6, 4]

There are two forms:

[<expression> for <element> in <sequence>]
[<expression> for <element> in <sequence> if <conditional>]

Here's an example that starts with [1, 2, 3, 4], picks out the even elements 2 and 4 using if i % 2 == 0, then squares each of these using i*i. The purpose of for i is to give a name to each element in [1, 2, 3, 4].

>>> [i*i for i in [1, 2, 3, 4] if i % 2 == 0]
[4, 16]

This list comprehension evaluates to a list of:

• The value of i*i
• For each element i in the sequence [1, 2, 3, 4]
• For which i % 2 == 0

In other words, this list comprehension will create a new list that contains the square of every even element of the original list [1, 2, 3, 4].

We can also rewrite a list comprehension as an equivalent for statement, such as for the example above:

>>> result = []
>>> for i in [1, 2, 3, 4]:
...     if i % 2 == 0:
...         result = result + [i*i]
>>> result
[4, 16]

A dictionary is a Python data structure that maps keys to values. For a dictionary d:

• Each key maps to exactly one value, which you can access with d[<key>].
• If you try d[<key>] but <key> is not a valid key in d, you'll get an error.
• You can use <key> in d to test (True or False) whether a key is in d.
• d.get(<key>, <default>) will return the value that <key> maps to in d, or <default> if <key> is not a key in d.
• The sequence of keys or values or key-value pairs can be accessed using d.keys() or d.values() or d.items(), respectively.
• Keys can be of any immutable type (like strings, numbers, and tuples) but not mutable types (like lists).
• You can use a d in a for loop (such as for k in d). Doing so will iterate through the keys in d.

As you can see, unlike trees in nature, the tree abstract data type is drawn with the root at the top and the leaves at the bottom.

For a tree t:

• Its root label can be any value, and label(t) returns it.
• Its branches are trees, and branches(t) returns a list of branches.
• An identical tree can be constructed with tree(label(t), branches(t)).
• You can call functions that take trees as arguments, such as is_leaf(t).
• That's how you work with trees. No t == x or t[0] or x in t or list(t), etc.
• There's no way to change a tree (that doesn't violate an abstraction barrier).

Here's an example tree t1, for which its branch branches(t1)[1] is t2.

t2 = tree(5, [tree(6), tree(7)])
t1 = tree(3, [tree(4), t2])

A path is a sequence of trees in which each is the parent of the next.

You don't need to know how tree, label, and branches are implemented in order to use them correctly, but here is the implementation from lecture.

def tree(label, branches=[]):
    for branch in branches:
        assert is_tree(branch), 'branches must be trees'
    return [label] + list(branches)

def label(tree):
    return tree[0]

def branches(tree):
    return tree[1:]

def is_leaf(tree):
    return not branches(tree)

def is_tree(tree):
    if type(tree) != list or len(tree) < 1:
        return False
    for branch in branches(tree):
        if not is_tree(branch):
            return False
    return True