######################################################
# Compute whether sqrt(51) - 4 < pi using generators #
######################################################

def sqrt(a):
    """Yield approximations that converge to the square root of a.

    >>> print_iterator(sqrt(51))
    [1, 26.0, 13.98076923076923, 8.81431859062533, 7.300179298823895, ...]
    """
    x = 1
    while True:
        yield x
        x = (x + a/x)/2

def pi():
    """Yield approximations that converge to pi.

    >>> print_iterator(pi())
    [0, 2.6666666666666665, 2.895238095238095, 2.976046176046176, 3.017071817071817, ...]
    """
    total, k = 0, 1
    while True:
        yield total
        total += 8/((4*k-3)*(4*k-1))
        k += 1

def four():
    while True:
        yield 4

def subtract(x, y):
    while True:
        yield next(x)-next(y)

def print_iterator(iterator, k=5):
    elements = []
    for _ in range(k):
        elements.append(next(iterator))
    print(str(elements)[:-1] + ', ...]')

def less_than_0(s):
    """Return True if iterator s converges to a number less than 0.

    >>> a = subtract(sqrt(51), four())
    >>> less_than_0(subtract(a, pi()))
    True
    """
    current = next(s)
    while True:
        last, current = current, next(s)
        if last < 0 and current < last:
            return True

###################################################
# Compute whether sqrt(51) - 4 < pi using streams #
###################################################

def sqrt_stream(a, x=1):
    """Compute a stream of approximations to sqrt(a), starting with x.

    >>> sqrt_of_2_approximations = sqrt_stream(2)
    >>> first_k(sqrt_of_2_approximations, 5)
    [1, 1.5, 1.4166666666666665, 1.4142156862745097, 1.4142135623746899]
    """
    def compute_rest():
        next_x = (x + a/x)/2
        return sqrt_stream(a, next_x)
    return Stream(x, compute_rest)

def pi_stream(total=0, k=1):
    """Compute a stream of approximations to pi, starting at total.

    >>> first_k(pi_stream(), 5)
    [0, 2.6666666666666665, 2.895238095238095, 2.976046176046176, 3.017071817071817]
    """
    def compute_rest():
        term = 8/(4*k-3)/(4*k-1)
        return pi_stream(total+term, k+1)
    return Stream(total, compute_rest)

def subtract_streams(s1, s2):
    """Return the difference of two streams as a stream."""
    first = s1.first - s2.first
    def compute_rest():
        return
    return Stream(first, lambda: subtract_streams(s1.rest, s2.rest))

def stream_less_than_0(s):
    """Return True if stream s converges to a number less than 0.

    >>> pi = pi_stream()
    >>> fours = Stream(4, lambda: fours)
    >>> a = subtract_streams(sqrt_stream(51), fours)
    >>> stream_less_than_0(subtract_streams(a, pi))
    True
    """
    while True:
        if s.first < 0 and s.rest.first < s.first:
            return True
        s = s.rest

########################
# Streams (Lecture 30) #
########################

class Stream:
    """A lazily computed recursive list.

    >>> s = Stream(1, lambda: Stream(6-2, lambda: Stream(9)))
    >>> s.first
    1
    >>> s.rest.first
    4
    >>> s.rest
    Stream(4, <...>)
    >>> s.rest.rest.first
    9
    """

    class empty:
        def __repr__(self):
            return 'Stream.empty'

    empty = empty()

    def __init__(self, first, compute_rest=lambda: Stream.empty):
        assert callable(compute_rest), 'compute_rest must be callable.'
        self.first = first
        self._compute_rest = compute_rest

    @property
    def rest(self):
        """Return the rest of the stream, computing it if necessary."""
        if self._compute_rest is not None:
            self._rest = self._compute_rest()
            self._compute_rest = None
        return self._rest

    def __repr__(self):
        return 'Stream({0}, <...>)'.format(repr(self.first))

def first_k(s, k):
    """Return up to k elements of stream s as a list.

    >>> s = Stream(1, lambda: Stream(4, lambda: Stream(9)))
    >>> first_k(s, 2)
    [1, 4]
    >>> first_k(s, 5)
    [1, 4, 9]
    """
    elements = []
    while s is not Stream.empty and k > 0:
        elements.append(s.first)
        s, k = s.rest, k-1
    return elements