CODEWITHSUNDEEP
pythonrecursionfunctional-programmingiteratorgenerator
Xander Dunn
Xander Dunn

Reputation: 2402

Python: Functionally Merging Two Iterators Where One is Recursive

The related question 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:

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.

Upvotes: 2

Views: 543

Answers (1)

user2357112
user2357112

Reputation: 281538

As Peter Wood suggests in the comments, this is exactly what the built-in function reduce does:

result = reduce(update_theta, stuff, some_initial_theta)

In Python 3, reduce has been moved to 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.

Upvotes: 4

Related Questions