# Recursive lists as nested pairs

def double(s):
    """Double each element of a tuple-based rlist.

    >>> t = (1, (2, (3, (4, None))))
    >>> double(t)
    (2, (4, (6, (8, None))))
    >>> len(t)
    2
    >>> t[1]
    (2, (3, (4, None)))
    """
    if s is None:
        return None
    first, rest = s
    return (2 * first, double(rest))

def map_tuple_rlist(s, fn):
    """Apply fn to each element in tuple-based rlist s.

    >>> t = (1, (2, (3, (4, None))))
    >>> map_tuple_rlist(t, lambda x: x*x)
    (1, (4, (9, (16, None))))
    """
    if s is None:
        return None
    first, rest = s
    return (fn(first), map_tuple_rlist(rest, fn))

# Recursive list class

class Rlist(object):
    """A recursive list consisting of a first element and the rest.

    >>> s.rest
    Rlist(2, Rlist(3))
    >>> len(s)
    3
    >>> s[1]
    2
    """
    class EmptyList(object):
        def __repr__(self):
            return '<empty>'
        def __len__(self):
            return 0

    empty = EmptyList()

    def __init__(self, first, rest=empty):
        self.first = first
        self.rest = rest

    def __repr__(self):
        args = repr(self.first)
        if self.rest is not Rlist.empty:
            args += ', {0}'.format(repr(self.rest))
        return 'Rlist({0})'.format(args)

    def __str__(self):
        return '({0}, {1})'.format(self.first, self.rest)

    def __len__(self):
        return 1 + len(self.rest)

    def __getitem__(self, i):
        if i == 0:
            return self.first
        return self.rest[i-1]

s = Rlist(1, Rlist(2, Rlist(3)))

def extend_rlist(s1, s2):
    """Return a list containing the elements of s1 followed by those of s2.

    >>> extend_rlist(s.rest, s)
    Rlist(2, Rlist(3, Rlist(1, Rlist(2, Rlist(3)))))
    """
    if s1 is Rlist.empty:
        return s2
    return Rlist(s1.first, extend_rlist(s1.rest, s2))

def range_rlist(start, end):
    """Return a recursive list representing a range from start to end.

    >>> range_rlist(2, 6)
    Rlist(2, Rlist(3, Rlist(4, Rlist(5))))
    """
    if start >= end:
        return Rlist.empty
    return Rlist(start, range_rlist(start+1, end))

def map_rlist(s, fn):
    """Return a list resulting from mapping fn over the elements of s.

    >>> map_rlist(s, lambda x: x*x)
    Rlist(1, Rlist(4, Rlist(9)))
    """
    if s is Rlist.empty:
        return s
    return Rlist(fn(s.first), map_rlist(s.rest, fn))

def filter_rlist(s, fn):
    """Filter the elemenst of s by predicate fn.

    >>> filter_rlist(s, lambda x: x % 2 == 1)
    Rlist(1, Rlist(3))
    """
    if s is Rlist.empty:
        return s
    rest = filter_rlist(s.rest, fn)
    if fn(s.first):
        return Rlist(s.first, rest)
    return rest

# Trees as nested tuples

t = ((1, 2), (3, 4), 5)

def count_leaves(tree):
    """Return the number of leaves in a tree.

    >>> count_leaves(t)
    5
    """
    if type(tree) != tuple:
        return 1
    return sum(map(count_leaves, tree))

def map_tree(tree, fn):
    """Return a tree with fn mapped to the leaves of tree.

    >>> map_tree(t, lambda x: x*x)
    ((1, 4), (9, 16), 25)
    """
    if type(tree) != tuple:
        return fn(tree)
    return tuple(map_tree(branch, fn) for branch in tree)

# Tree class (binary trees with internal values)

class Tree(object):
    """A tree with internal values."""

    def __init__(self, entry, left=None, right=None):
        self.entry = entry
        self.left = left
        self.right = right

    def __repr__(self):
        args = repr(self.entry)
        if self.left or self.right:
            args += ', {0}, {1}'.format(repr(self.left), repr(self.right))
        return 'Tree({0})'.format(args)

def fib_tree(n):
    """Return a Tree that represents a recursive Fibonacci calculation.

    >>> fib_tree(3)
    Tree(1, Tree(0), Tree(1))
    """
    if n == 1:
        return Tree(0)
    if n == 2:
        return Tree(1)
    left = fib_tree(n-2)
    right = fib_tree(n-1)
    return Tree(left.entry + right.entry, left, right)

def count_entries(tree):
    """Return the number of entries in a Tree.

    >>> count_entries(fib_tree(6))
    15
    """
    if tree is None:
        return 0
    return 1 + count_entries(tree.left) + count_entries(tree.right)


def big_tree(left, right):
    """Return a tree of elements between left and right.

    >>> big_tree(0, 12)
    Tree(6, Tree(2, Tree(0), Tree(4)), Tree(10, Tree(8), Tree(12)))
    """
    if left > right:
        return None
    split = left + (right - left)//2
    return Tree(split, big_tree(left, split-2), big_tree(split+2, right))