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 isempty(left): return right if isempty(right): # Unnecessary clause (but can save time). return left else: return make_rlist(first(left), extend_rlist(rest(left), right)) def dextend_rlist(left, right): """Returns result of extending LEFT with RIGHT. May destroy original list LEFT.""" if isempty(left): return right if isempty(right): # Unnecessary clause (but can save time). return left else: set_rest(left, dextend_rlist(rest(left), right)) return left 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