# 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