Python 函数式迭代算法？

Question

Haskell 中有一个简单的列表函数可用

iterate :: (a -> a) -> a -> [a]
iterate f x =  x : iterate f (f x)

在Python中可以按如下方式实现：

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

我有点惊讶像这样的基本东西不是 functools/itertools 模块的一部分。是否可以使用这些库中提供的工具以函数式风格（即没有循环）简单地构建它？（主要是代码高尔夫，试图了解 Python 中的函数式风格。）

Answer 1

您可以使用以下中的一些函数来完成此操作itertools：

from itertools import accumulate, repeat

def iterate(func, initial):
    return accumulate(repeat(None), func=lambda tot, _: func(tot), initial=initial)

虽然它显然不是很干净。Itertools 缺少一些构建流的基本功能，例如unfoldr. 大多数itertools函数都可以用 来定义unfoldr，但无论如何，函数式编程在 Python 中有点不舒服，所以这可能没有多大好处。

Answer 2

itertools该模块有一个第三方“扩展” more-iterools，其中包括（除许多其他内容外）一个iterate与您观察到的完全相同定义的函数：

# Exact definition, minus the doc string...
def iterate(func, start):
    while True:
        yield start
        start = func(start)

Python 缺乏进行递归定义所需的优化，例如

def iterate(func, start):
    yield from chain([start], iterate(func, func(start))

可行的。

如果您好奇，Coconut是 Python 的超集，它确实可以执行尾部调用优化等操作。在https://cs121-team-panda.github.io/coconut-interpreter/尝试以下代码：

@recursive_iterator
def iterate(f, s) = (s,) :: iterate(f, f(s))

for x in iterate(x -> x + 1, 0)$[1000:1010]:
    print(x)

（我不完全确定recursive_iterator装饰器是必要的。我认为迭代切片表明，这避免了类似 Python 代码会产生的递归深度错误。）