Python: Functionally Merging Two Iterators Where One is Recursive
Question: The related question [How do I merge two python
iterators?](http://stackoverflow.com/questions/243865/how-do-i-merge-two-
python-iterators) works well for two independent iterators. However, I haven't
been able to find or think of the tools necessary for merging two iterators
where one is recursive and takes the other as an input. I have iterator
`stuff` that is a simple list. Then I have iterator `theta` that takes a
function `func` and yields x, func(x), func(func(x)), where one of the inputs
to `func` is an element of `stuff`. I've solved this with mutable state as
follows:

    
    
    theta = some_initial_theta
    for thing in stuff:
        theta = update_theta(theta, thing)
    return theta
    

A concrete example in this format:

    
    
    def update_theta(theta, thing):
        return thing * 2 + theta
    
    stuff = [100, 200, 300, 400]
    
    
    def my_iteration():
        theta = 0
        for thing in stuff:
            theta = update_theta(theta, thing)
        print(theta)
    # This prints 2000
    

I'm sure there's an elegant way of doing this without the mutable state and
the for loop. A simple zip doesn't do it for me because the `theta` iterator
uses its previous element as an input to the next element.

One elegant way of expressing theta is using the `iterate` method available in
the [more_itertools package](https://pythonhosted.org/more-
itertools/api.html#more_itertools.iterate):

    
    
    iterate(lambda theta: update_theta(theta, thing), some_initial_theta)
    

However, the problem with this is that `thing` will be fixed throughout the
iteration. It would be possible to deal with this by passing in the entire
list `stuff` and then return the remainder of it from the update_theta method:

    
    
    iterate(lambda theta: update_theta(theta[0], theta[1]), (some_initial_theta, stuff))
    

However, I'd really rather not modify the `update_theta` method to take an
entire list it's not interested in and deal with the mechanics of returning
the tail of that list. While it's programmatically not difficult, it's poor
separation of concerns. `update_theta` shouldn't know anything about or care
about the entire list `stuff`.


Answer: As Peter Wood suggests in the comments, this is **exactly** what the built-in
function [`reduce`](https://docs.python.org/2/library/functions.html#reduce)
does:

    
    
    result = reduce(update_theta, stuff, some_initial_theta)
    

In Python 3, `reduce` has been moved to
[`functools.reduce`](https://docs.python.org/3/library/functools.html#functools.reduce),
so you'd need to import that:

    
    
    from functools import reduce
    

If you want an iterator of all the intermediate values, Python 3 provides
`itertools.accumulate`. There's no argument to specify an initial value, so
you'd need to put the initial value in the iterator:

    
    
    from itertools import accumulate, chain
    result_iterator = accumulate(chain([some_initial_theta], stuff), update_theta)
    

Python 2 doesn't have `itertools.accumulate`, but you could copy the
equivalent code from the Python 3 documentation. There's no easy way to
formulate it in terms of the Python 2 standard tools, which is why people
wanted it added to Python 3 in the first place.

