Python是否有一个迭代递归生成器函数来处理一阶递推关系？

Question

是否有内置函数或标准库函数大致等同于

def recur_until(start, step_fu, stop_predicate=lambda _: False):
    current = start
    while not stop_predicate(current):
        yield current
        current = step_fu(current)

或者

def recur_while(start, step_fu, predicate=lambda _: True):
    current = start
    while predicate(current):
        yield current
        current = step_fu(current)

或者仅仅是

def recur(start, step_fu):
    current = start
    while True:
        yield current
        current = step_fu(current)

在任何版本的Python中都可以使用吗？（如果与itertools.takewhile结合使用，后者与前两者一样好。）

像这样的生成器函数可以允许迭代计算某些递归定义的序列，即一阶递推关系。

虽然这些不是太难实现，但我觉得像它们这样的东西应该是itertools或functools的一部分，但如果是的话，我还没有在文档中找到它。

---

使用示例：

list(recur_until(2, lambda x: x**2 - 1, lambda x: x > 1e4))
# [2, 3, 8, 63, 3968]

应该也适用于非数字元素：

list(recur_until('', lambda x: '[{}]({})'.format(x, len(x)), lambda x: len(x) > 30))
# ['',
#  '[](0)',
#  '[[](0)](5)',
#  '[[[](0)](5)](10)',
#  '[[[[](0)](5)](10)](16)',
#  '[[[[[](0)](5)](10)](16)](22)']

- das-g

---

即，与Haskell的iterate函数等效。 iterate（\ x-> x + 1）0 = 0,1,2,3,4,5，... - chepner

@chepner iterate 与 takeWhile 的组合。 - Sven Marnach

我经常遇到一些问题，它们仅仅是“X是否存在？”而我很有信心答案是否定的。除了提供你已经提供过的文档链接之外，我无法找到其他理由来证明我的答案。 - DSM

@DSM，是的，我知道存在性问题存在否定答案基本上是无法证明的问题。但是由于我特别关注标准库在这方面提供了什么，所以我不知道该如何用不同的方式提出我的问题。 - das-g

@SvenMarnach：为什么你删除了你的答案？在它消失之前我没有时间测试它，但它看起来很有前途。 - das-g

Answer 1

在Python 3.3及以上版本中，可以使用新的itertools.accumulate与其他itertools结合使用来实现此目的。

例如：

>>> from itertools import accumulate, repeat, takewhile
>>> fun = accumulate(range(2, 10), lambda x, _: x**2 - 1)
>>> list(fun)
[2, 3, 8, 63, 3968, 15745023, 247905749270528, 61457260521381894004129398783]
>>> fun = takewhile(lambda y: y < 1e4, accumulate(repeat(2), lambda x, _: x**2 - 1))
>>> list(fun)
[2, 3, 8, 63, 3968]

accumulate接受一个序列和一个带有两个参数的函数：第一个是累加值，第二个是序列中的下一个值。在这种情况下，我们只需要第一个参数，它将是传递给accumulate的序列的第一个元素，用于传递函数的第一次调用和该函数的返回值后续调用。

因此，我们只需要将传递序列的开头作为初始值 - 在本例中为2。其余序列的内容无关紧要，但我们可以使用它的长度来控制我们想要的元素数量（如第一个示例）或创建一个无限生成器（如第二个示例）。

- Copperfield

---

呵呵，我在看到你的回答之前，刚开启我的另一台电脑上装有 Python 3.4 版本，想要测试类似这样的东西。 - das-g

Answer 2

缺失的部分是你需要有一些东西将你的递归步进函数转换为生成器。一旦你拥有了这个，那么你就可以使用任何itertools方法。

def recur_to_gen(step_fu, current, sentinel=None):
    while current != sentinel:
        yield current
        current = step_fu(current)


matches = itertools.takewhile(predicate, recur_to_gen(step_fu, start))

recur_to_gen 可能是一个合理的建议，可以添加到 itertools 中。

- PaulMcG

---

不幸的是，我认为Python中的“迭代”与iter紧密相关，它更多地涉及遍历序列，而不是递归地应用步进函数以获取下一个项目。但无论如何，我认为itertools将是这样的东西的好去处。 - PaulMcG

@StefanPochmann 函数 recur_to_gen() 是一个生成器函数（因为它使用了 yield）。这里没有生成器表达式。 - Sven Marnach

@SvenMarnach：我认为SP是在引起注意PM的第一句话——OP的原始函数（虽然称为recur）是非递归的，并且已经是一个genfunc。 - DSM

已编辑，希望在术语精度方面有所改进。 - PaulMcG

@DSM - 非递归的意思不是调用自身，而是通过在当前项目上调用步进函数来迭代不一定连续的项目链以获取下一个项目。 - PaulMcG

Answer 3

functional包提供了模拟此过程所需的部件。

from functional import dropWhile, iterate    
recur = dropWhile(predicate, iterate(step_func, start))

例如，

>>> next(dropWhile(lambda x : x < 10, iterate(lambda x: x + 1, 2)))
10

（dropWhile 与 itertools.dropwhile 并没有什么不同。）

- chepner

---

最新可用的版本适用于Python 2.5。Python的一个更新的功能包：https://github.com/kachayev/fn.py - Sven Marnach

它仍然可以工作（通过pip安装，但我没有进行全面测试），但是是的，我认为functional是一次性的概念验证，从未得到真正的支持。 - chepner