def make_tree(label, kids = [])
    """A (sub)tree with given LABEL at its root, whose children
    are KIDS."""
    return [ label ] + kids

def label(tree):
    """The label on TREE."""
    return tree[0]

def children(tree):
    """The immediate descendants of TREE (each a tree)."""
    return tree[1:]

def isleaf(tree):
    """True if TREE is a leaf node."""
    return len(tree) == 1


def leaf_labels(tree):
    """A list of the labels of all leaves in TREE."""




def eval(expr):
    """The value yielded by the computation represented by
    expression tree EXPR.  Assumes all leaves are numbers
    and all inner-node labels are operators."""


empty_rlist = None

def make_rlist(first, rest = empty_rlist):
    """A recursive list, r, such that first(r) is FIRST and 
    rest(r) is REST,  which must be an rlist."""
    return [first, rest]

def first(r):
    """The first item in R."""
    return r[0]

def rest(r):
    """The tail of R."""
    return r[1]

def isempty(r):
    """True iff R is the empty sequence"""
    return r is None

def set_first(r, v):
    r[0] = v

def set_rest(r, v):
    r[1] = v

def map_rlist(f, s):
    """The rlist of values F(x) for each element x of rlist S in order."""
    if isempty(s):
        return empty_rlist
    else:  
        return make_rlist(f(first(s)), map_rlist(f, rest(s)))

def filter_rlist(cond, seq):
    """The rlist consisting of the subsequence of rlist SEQ for which
    the 1-argument function COND returns a true value."""

    if isempty(seq): 
	 return empty_rlist
    elif cond(first(seq)): 
	 return make_rlist(first(seq), 
			   filter_rlist(cond, rest(seq)))
    else:
	 return filter_rlist(cond, rest(seq))


def extend_rlist(left, right):
    """The sequence of items of rlist `left'
    followed by the items of `right'."""
    if _______________________:
         return ___________________
    else:
         return ___________________


def map_tree(f, T):
    """The tree T with each label, lab, replaced by F(lab)."""

    return _______________________________________________________
    # Hint: Use the map operation on sequences!\}

def dmap_rlist(f, S):
    """The rlist of values F(x) for each element x of rlist S in
    order.  May modify S."""
    if isempty(s):
        return empty_rlist  # This case doesn't change
    else:
        _______________________________
        _______________________________
        return ________________________



def dmap_rlist2(f, s):
    """The rlist of values F(x) for each element x of rlist S in
    order.  May modify S."""
    p = s
    while not isempty(p):
       ______________________________________________
       ______________________________________________
    return ________________________________













def extend_rlist(left, right):
    """The sequence of items of rlist `left'
    followed by the items of `right'."""
    if isempty(left):
         return right
    else:
         return make_rlist(first(left), 
                           extend_rlist(rest(left), right))

def map_tree(f, T):
    """The tree T with each label, lab, replaced by F(lab)."""

    return make_tree(label(T), map(f, children(T)))


def dmap_rlist(f, s):
    """The rlist of values F(x) for each element x of rlist S in
    order.  May modify S."""
    if isempty(s):
        return empty_rlist  # This case doesn't change
    else:
        set_first(s, f(first(s)))
        dmap_rlist(f, rest(s))
        return s

def dmap_rlist2(f, s):
    """The rlist of values F(x) for each element x of rlist S in
    order.  May modify S."""
    p = s
    while not isempty(p):
       set_first(p, f(first(p)))
       p = rest(p)
    return s