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