使用itertools进行递归函数的应用

Question

我需要一个Python函数iterate(f, x)，它创建一个迭代器，返回值x, f(x)， f(f(x))， f(f(f(x)))等(例如Clojure的iterate)。首先，我想知道:这是否已经存在于标准库的某个地方，而我只是缺少它?当然，这很容易用一个生成器实现:

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

只是出于好奇:在Python中是否有更实用的方法来实现这一点，例如使用一些itertools或functools魔法?

在Python 3.3中可以

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

但对我来说像是一种虐待。我能做得更好吗?

Answer 1

在itertools中似乎没有你想要的东西，但是itertools是一个很深的宝箱，所以我可能错过了一些东西。

你的生成器代码看起来很棒。我不知道你为什么要用accumulate来写它，除非你在玩一个荒谬的代码高尔夫游戏，或者你想给Haskell的势利者留下深刻印象。编写您的函数，使其易于阅读、理解和维护。没必要太聪明

Answer 2

您可以使用变形(或展开)来简化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

用ana实现iterate然后看起来像这样:

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

没有itertools，但是…我同意这不是最具可读性的变体。事实上，它是相当神秘的。

---

更新:有一个更简单的版本，甚至看起来相当不错。从这里开始:

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

这给了你:

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