# Recursive list abstract data type
empty_rlist = None
def rlist(first, rest):
"""Return a recursive list from its first element and the rest."""
return (first, rest)
def first(s):
"""Return the first element of a recursive list s."""
return s[0]
def rest(s):
"""Return the rest of the elements of a recursive list s."""
return s[1]
# Some recursive lists
counts = rlist(1, rlist(2, rlist(3, rlist(4, empty_rlist))))
alts = rlist(1, rlist(2, rlist(1, rlist(2, rlist(1, empty_rlist)))))
# Implementing the sequence abstraction
def len_rlist(s):
"""Return the length of recursive list s."""
length = 0
while s != empty_rlist:
s, length = rest(s), length + 1
return length
def getitem_rlist(s, i):
"""Return the element at index i of recursive list s."""
while i > 0:
s, i = rest(s), i - 1
return first(s)
# Sequence iteration
from operator import getitem
def count_while(s, value, getitem=getitem, len=len):
"""Count the number of occurrences of value in sequence s."""
total, index = 0, 0
while index < len(s):
if getitem(s, index) == value:
total = total + 1
index = index + 1
return total
def count(s, value):
"""Count the number of occurrences of value in sequence s."""
total = 0
for elem in s:
if elem == value:
total = total + 1
return total