python - 如何在 Python 中编写 foldr(右折叠)生成器？

Question

Python 的 reduce 是左折叠，这意味着它是尾递归的，它的用法可以巧妙地重写为循环。但是，Python 没有用于进行右折叠的内置函数。由于右折叠最自然地用递归编写(Python 不像函数式语言那样喜欢递归)，所以我有兴趣根据生成器编写右折叠 (foldr)。

如何做到这一点？非常具体地说，如何在 Python 2.7 中完成？

编辑:我应该提到 foldr 的好处之一是您有时可以在无限列表上折叠而不会有吃掉堆栈的风险。我希望看到保留此属性的答案。

例如，Haskell 的 foldr 在输入和输出上都是惰性的，并且可以允许短路“step”函数以处理长/无限输入:

foldr (&&) True (repeat False)  -- gives False

任何使用 list/reversed/etc 的 Python 变体。如果给定 itertools.repeat(some_value)，输入将挂起。

请注意，Python 的 reduce 由于严格性而在同一示例中阻塞:

reduce(lambda x, y: x and y, itertools.repeat(False), True) # hangs

Answer 1

一个简单的 python 生成器(没有适当的错误检查):

def foldr(op, lst):
    l, x = reversed(list(lst)), None
    for i in l:
        if not x:
            x = i
            continue
        x = op(x, i)
        yield x

例如:

>>> from operator import mul
>>> for i in foldr(mul, [1,2,3,4]):
...     print i
24
24
12

与文档中 reduce 的“大致等效”实现几乎相同:

def foldr(function, iterable, initializer=None):
    it = reversed(list(iterable))
    if initializer is None:
        try:
            initializer = next(it)
        except StopIteration:
            raise TypeError('foldr() of empty sequence with no initial value')
    accum_value = initializer
    for x in it:
        accum_value = function(accum_value, x)
        yield accum_value

[编辑]因此，纯粹作为一种思维练习并且几乎没有实用值(value)，只要您折叠的功能之间存在某种合作，就可以推迟......例如:

class Defer(object):
    def __init__(self, func, *args):
        self.func = func
        self.args = args
    def __bool__(self):
        return self.func(*self.args)
    def __int__(self):
        return self.func(*self.args)

def foldr(function, iterable, initializer):
    it = iter(iterable)
    try:
        return function(next(it), Defer(foldr, function, it, initializer))
    except StopIteration:
        return initializer

然后只要函数转换为正确的类型，您就可以延迟计算，但是这不适用于 native 运算符，所以不确定这到底有多大用处:

>>> print(foldr(lambda a, b: int(a)*int(b), [1,2,3,4], 1))
24

定义一个永久生成器:

from itertools import repeat
def forever():
    yield False
    yield True
    for i in repeat(False):
        yield i

在无限列表中折叠 or，找到 True 时返回

>>> print(foldr(lambda a, b: bool(a) or bool(b), forever(), False))
True