from operator import add, mul
from math import sqrt, e

# Recursive lists using pairs
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]

counts = rlist(1, rlist(2, rlist(3, rlist(4, empty_rlist))))

# Implementing the sequence abstraction using recursion
def len_rlist(s):
    """Return the length of a recursive list s.
    
    >>> len_rlist(counts)
    4
    """
    if s == empty_rlist:
        return 0
    return 1 + len_rlist(rest(s))

def getitem_rlist(s, i):
    """Return the element at index i of recursive list s.

    >>> getitem_rlist(counts, 2)
    3
    """
    if i == 0:
        return first(s)
    return getitem_rlist(rest(s), i - 1)

# Implementing the sequence abstraction using iteration
def len_rlist_iterative(s):
    """Return the length of a recursive list s.
    
    >>> len_rlist_iterative(counts)
    4
    """
    length = 0
    while s != empty_rlist:
        s, length = rest(s), length + 1
    return length

def getitem_rlist_iterative(s, i):
    """Return the element at index i of recursive list s.

    >>> getitem_rlist_iterative(counts, 2)
    3
    """
    while i > 0:
        s, i = rest(s), i - 1
    return first(s)

# Python sequence abstraction

a = (1, 2, 3)
b = tuple([4, 5, 6, 7])

len(a), len(b)

a[1], b[-1]

a[1:3], b[1:1], a[:2], b[1:]

2 in a, 4 in a, 4 not in b

# For statement
def count(s, value):
    total = 0
    for elem in s:
        if elem == value:
            total += 1
    return total

# Sequence unpacking
pairs = ((1, 2), (2, 2), (2, 3), (4, 4))

def count_same(pairs):
    same_count = 0
    for x, y in pairs:
        if x == y:
            same_count += + 1

count_same(pairs)

# Ranges
tuple(range(-2, 3))
tuple(range(4))

# String literals
'I am string!'
"I've got an apostrophe"
'您好'
"""The Zen of Python
claims, Readability counts.
Read more: import this."""

# Strings are sequences
city = 'Berkeley'
len(city)
city[3]
'here' in "Where's Waldo?"

# Sequence arithmetic
city + ', CA'
"Don't repeat yourself! " * 2
(1, 2, 3) * 3
(1, 2, 3) + (4, 5, 6, 7)

# Sequences as conventional interfaces
def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    return fib(n - 1) + fib(n - 2)

is_even = lambda x: x % 2 == 0

fibs = tuple(map(fib, range(8)))
even_fibs = tuple(filter(is_even, fibs))
sum(even_fibs)

# Generator expressions
even_fibs2 = tuple(fib(n) for n in range(8) if is_even(fib(n)))

# Reducing a sequence
from operator import mul
from functools import reduce
reduce(mul, (1, 2, 3, 4, 5), 1)

def accumulate(combiner, start, n, term):
    """Accumulate a sequence of n terms with the given combiner and
    initial value.

    >>> accumulate(mul, 1, 4, lambda x: x * x)
    576
    """
    return reduce(combiner, map(term, range(1, n + 1)), start)

# More functions on iterables (bonus)
a, b = (1, 2, 3), (4, 5, 6, 7)
for x, y in zip(a, b):
    print(x + y)

from itertools import product, combinations
tuple(product(a, b[:2]))
tuple(combinations(a, 2))