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