# Rlists # The empty rlist (unique). empty_rlist = None def 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: the sequence consisting of items 1, 2,..., renumbered from 0.""" return r[1] # The sequence 1, 3, 0, 4 L = rlist(1, rlist(3, rlist(0, rlist(4, empty_rlist)))) # The sequence containing sequences (0, 1) and (2, 3) L = rlist(rlist(0, rlist(1, empty_list)), rlist(rlist(2, rlist(3, empty_list)), empty_rlist)) # Length def len_rlist(s): # A sequence is: """The length of rlist S.""" if s == empty_rlist: # * Empty or... return 0 else: return 1 + len_rlist(rest(s)) # A first element and # the rest of the list # Tail-recursive version def len_rlist(s): """The length of rlist S.""" def len(sofar, s): """Return SOFAR + the length of rlist S.""" if s == empty_rlist: return sofar else: return len(sofar + 1, rest(s)) len(0, s) # Iterative version def len_rlist(s): sofar = 0 while s != empty_rlist: sofar, s = sofar+1, rest(s) return sofar # getitem def getitem_rlist(s, k): """Return the element at index K of recursive list S. Assumes K >= 0. >>> getitem_rlist(rlist(2, rlist(3, rlist (4))), 1) 3""" if k == 0: return first(s) else: return getitem_rlist(rest(s), k-1) # Iterative version def getitem_rlist(s, k): """Return the element at index K of recursive list S. Assumes K >= 0.""" while k != 0: s, k = rest(s), k-1 return first(s) # Map def square_rlist(s): """The list of squares of the elements of rlist S.""" if s == empty_rlist: return empty_rlist else: return rlist(first(s)**2, square_rlist(rest(s))) def map_rlist(f, s): """The list of values F(x) for each element x of S in order.""" if s == empty_rlist: return empty_rlist else: return rlist(f(first(s)), map_rlist(f, rest(s))) # Alternative definition def square_rlist2(s): return map_rlist(lambda x: x*x, s) # Extend def extend_rlist(left, right): """The sequence of items of rlist `left' followed by the items of `right'.""" if left == empty_rlist: return right else: return rlist(first(left), extend_rlist(rest(left), right)) # Reverse def reverse_rlist(L): def reverse_extend(to_do, already_done): """The result of extending ALREADY_DONE with the reverse of TO_DO.""" if to_do == empty_rlist: return empty_rlist else: return reverse_extend(rest(to_do), rlist(first(to_do), already_done)) reverse_extend(L, empty_rlist)