Using itertools for recursive function application

Question

I need a Python function iterate(f, x) that creates an iterator returning the values x, f(x), f(f(x)), f(f(f(x))), etc (like, e.g., Clojure's iterate). First of all, I was wondering: Does this already exist somewhere in the standard library and I'm only missing 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 functional way to do this in Python, e.g. with some itertools or functools magic?

In Python 3.3 this would work

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

but looks like an abuse to me. Can I do this more nicely?

I'd say the `accumulate()` version is just fine. *Both* versions are just fine. — Martijn Pieters, Mar 26 '13 at 12:07
What I really find strange about the `accumulate()` version is the need for `repeat(x)` or something similar, because x is really only needed *once* as a seed for the computation. — embee, Mar 26 '13 at 12:36
@embee Now that you mention it, I find that weird as well. Prob best as the first solution — jamylak, Mar 26 '13 at 12:38
As one of the Haskell snobs mentioned by @Ned, I'd just like to say that there is a nice way of producing `iterate` from a _single_ initial value: by using an [anamorphism](http://en.wikipedia.org/wiki/Anamorphism) (which is essentially the opposite of `reduce`). — phipsgabler, Mar 27 '13 at 16:57
That was essentially what I was looking for, @phg, that's why I used the word 'recursive'. But how would you express it in Python? — embee, Mar 27 '13 at 17:15

score 6 · Accepted Answer · answered Mar 26 '13 at 12:09

6

There doesn't seem to be something in itertools that does what you want, but itertools is a deep treasure chest, so I could have missed something.

Your generator code looks great. I don't know why you'd write it with accumulate unless you were playing an absurd game of code golf, or you were trying to impress Haskell snobs. Write your function so that it is readable, understandable, and maintainable. No need to be overly clever.

answered Mar 26 '13 at 12:09

Ned Batchelder

364,293
75
561
662

You're absolutely right and I would never even have thought about the bizarre `accumulate` version before writing up this post. I was genuinely wondering if I was missing a nice, succinct way to use itertools. I find myself turning functions into iterators (like here or in the `tabulate` example from the [itertools recipes](http://docs.python.org/2/library/itertools.html#recipes) from time to time and wondered what the most pythonic way to do it would be. – embee Mar 26 '13 at 12:26

phipsgabler · Answer 2 · 2013-03-27T17:53:30.520

You can use an anamorphism (or unfold) to simplify the definition of iterate, and to use only one starting value. Here's an implementation I once used, based on a quite well-known paper:

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

Implementing iterate with ana then looks like this:

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

No itertools, though... And I agree that this isn't the most readable variant. In fact, it is rather cryptic.

UPDATE: There's an easier version, which even looks quite nice. It's taken from here:

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

And that gives you:

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

I like this one. Interestingly, this `unfold` is structured exactly as my original `iterate` generator, but gains a whole new level of abstraction and generality because f now returns pairs instead of a single value. Nice. — embee, Mar 27 '13 at 19:11

Using itertools for recursive function application

2 Answers2

Linked