使用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

你可以使用一种叫做反演（或者说是展开）的方法来简化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)

Answer 2

在itertools这个库里，似乎没有直接能满足你需求的东西，不过这个库的功能非常丰富，我可能会漏掉一些东西。

你的生成器代码写得很好。我不太明白你为什么要用accumulate来写，除非你是在玩一种很奇怪的代码挑战，或者是想让一些喜欢Haskell的人刮目相看。写代码的时候，应该让它易读、易懂、好维护，不用太过于追求聪明的写法。