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