Accumulate function from its own output

user_1874170 0
Viewed 97

I've got the following generator, it's a bit like itertools.accumulate, except that it takes the next input from the function's own output rather from than an iterable:

def turboaccumulate(f, initial):
    x = initial
    while True:
        x = f(x)
        yield x

Is anything like this contained in the standard library, or does the Python documentation contain a recommended recipe for this? I was unable to find one in about 20 minutes of searching.

Or, at the very least: what is this operation called? (I highly doubt "turbo-accumulate" is the recognized name for it.)

The context of this was an effort to parse the inscrutable lisp behemoth here into something understandable by mortals, which I got down to:

def blum_blum_shub(p, q, s):
    #assert coprime(p, q)
    M = p * q
    return turboaccumulate(lambda x: pow(x, 2, M), s)

However, that final function call just looks absolutely goofy, so I'm wondering if it's present in the standard library or at least has a more recognized name.

accumulate iterator python
2 Answers

Python doesn't have such a built-in as far as I know unfortunately. If you require this functionality, your generator function is probably as clean as you'll get.

iter's less-known second-form almost does what you want, but unfortunately, they made it purely side-effectual, which breaks the pattern. To make use of it, you'd need a wrapper similar to this:

def fp_iter(f, initial):
    acc = initial
    def wrapper():
        nonlocal acc
        return (acc := f(acc))

    return iter(wrapper, object())

>>> i = fp_iter(lambda n: n + 1, 0)
>>> next(i)
1
>>> next(i)
2
>>> next(i)
3

And at that point, I'd just use your generator.

It terms of the name of this, I know this as the iterate function due to my time using Clojure. This resembles iteration in math, so I think that's about as appropriate name as you'll get:

In mathematics, iteration may refer to the process of iterating a function, i.e. applying a function repeatedly, using the output from one iteration as the input to the next.

user_30002060

You can use accumulate to achieve this in some sort of non-standard way:

from itertools import accumulate, count

def turboaccumulate(f, initial):
    return accumulate(count(), lambda x, y: f(x), initial=initial)

You can use any infinite iterator instead of count as its values are ignored (y is never used).

user_23901820
Related