Geek asks and answers

Using itertools to apply recursive functions

I need a Python function iterate(f, x)that creates an iterator that returns the values ​​x, f (x), f (f (x)), f (f (f (x))), etc. (e.g. Clojureiterate ). First of all, I was wondering: does this already exist somewhere in the standard library, and will I just skip it? Of course, it's easy enough to implement with a generator:

def iterate(f, x):
    while True:
        yield x
        x = f(x)

Just out of curiosity: is there a more efficient way to do this in Python, for example. with some kind of magic itertools or functools?

In Python 3.3, this will work

def iterate(f, x):
    return accumulate(repeat(x), lambda acc, _ : f(acc))

but it looks like abuse to me. Can I make it more beautiful?

+5
source share
2 answers

, itertools -, , , itertools - , - .

. , , - . , , . .

+4

anamorphism ( ), iterate . , - , :

def ana(build, predicate):
    def h(x):
        if predicate(x):
            return
        else:
            a, b = build(x)
            yield a
            for i in h(b):
                yield i
            # with newer syntax: 
            # yield from h(b)
    return h

iterate ana :

def iterate(f, x):
    return ana(lambda x: (x, f(x)), lambda _: False)(x)

, itertools... , . .

UPDATE: , . :

def unfold(f, x):
    while True:
        w, x = f(x)
        yield w

:

def iterate(f, x):
    return unfold(lambda y: (y, f(y)), x)
+3

More articles:


All Articles