如何在Python中编写foldr（右折叠）生成器？

Question

Python的reduce是一个左折叠，这意味着它是尾递归的，而且它的用法可以整洁地重写为循环。然而，Python没有内置函数来执行右折叠。由于右折叠最自然地用递归来编写（而Python并不像函数式语言那样喜欢递归），我想编写一个基于生成器的右折叠（foldr）。

怎样才能做到这一点？具体来说，在Python 2.7中如何做到这一点？

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

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

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

任何使用list/reversed等操作的Python变体，在输入中使用itertools.repeat(some_value)时会出现挂起的情况。

请注意，由于严格性问题，Python的reduce在相同的示例中也会出现问题。

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

- Elliot Cameron

---

我认为要做到这一点，你的生成器必须yield一个生成器，该生成器yield另一个生成器，以此类推...如果传递的参数是一个空列表，则yield初始值...老实说，这听起来有点令人头疼...Python对递归没有问题，只要它的深度合理，但我不完全确定递归和生成器是否能很好地配合使用... - twalberg

Haskell中foldr的定义就是reduce，而foldl在无限列表上会失败。 - AChampion

Python的reduce是一个左折叠，因此就像Haskell的foldl'（注意有一个撇号）。是的，foldl及其变体将无法处理无限列表，这就是为什么某些情况下可能需要使用右折叠。 - Elliot Cameron

很遗憾，在Python中函数调用不是惰性的，因此如果您将foldr实现为f(x, f(x, f(x, ....)))，那么所有函数都会立即被求值，即使该函数被定义为def lor(a,b): a or b，而or是惰性的，但b参数不是。 - AChampion

@achampion 谢谢。在解决这个问题/答案的过程中，我意识到了这一点。在选择答案之前，我会再多考虑一些时间。 - Elliot Cameron

你实际上需要一个右折叠还是一个短路左折叠可以吗？ - Veedrac

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

e.g.:

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

[编辑] 纯粹作为头脑锻炼，实际价值很小，只要在您正在折叠的函数之间存在一些协作，就可以推迟。例如：

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

只要该函数转换为正确的类型，您就可以推迟计算，但这对原生运算符无效，因此不确定这真的有多有用：

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

在无限列表上使用折叠或运算符，当找到 True 时返回。

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

- AChampion

---

如果lst是个生成器呢？ - Elliot Cameron

那么您需要操作可迭代对象...l = list(lst)。为了执行foldr，您需要展开完整的生成器。 - AChampion

Answer 2

你需要捕获适当的异常，但应该知道如何以迭代方式完成：

def foldr(a, b, l):
    if isinstance(l, Iterator):
        it = reversed(list(l))
    else:
        it = reversed(l)
    try:
       nxt = next(it)
    except StopIteration:
        return 
    c = a(nxt, b)  
    stop = object() 
    while nxt is not stop:
        yield c
        nxt = next(it, stop)
        c = a(nxt, c) if nxt is not stop else c



from operator import truediv
for c in (foldr(truediv, 1, [1, 2, 3, 4, 5, 6, 7, 8])):
    print(c)

- Padraic Cunningham

---

如果 l 本身就是一个生成器呢？ - Elliot Cameron

你能否添加一个如何在无限列表中工作的示例？ - Padraic Cunningham

@3noch，那么在输入无限的情况下会发生什么？foldr 在处理完 n 个元素后是间歇性返回还是短路呢？ - Padraic Cunningham

@3noch，我唯一能想到的复制方法就是使用某种形式的并行处理。一旦您使用itertools.repeat(False)，那么您就进入了一个无限循环。 - Padraic Cunningham

@PadraicCunningham 我认为我正在意识到 Haskell 的 foldr 处理无限列表的能力是由于输入的隐式惰性。Python 的严格语义将始终要求从无限列表中获取“下一个”项，除非您构建一个特殊的接口。 - Elliot Cameron

Answer 3

如果您要使用生成器定义函数，为什么不使用以下方法？

def foldr(op, lst):
    return reduce(op, reversed(lst))

- Sohail Si

Answer 4

我认为这就是你想要的东西：

def foldr(fn, seq, init):
    it = iter(seq)
    try:
        x = next(it)
    except StopIteration:
        try:
            for elem in init:
                yield elem
        except TypeError:
            yield init
    else:
        try:
            for elem in fn(x, foldr(fn, it, init)):
                yield elem
        except TypeError:
            yield fn(x, foldr(fn, it, init))

它并不完全适用于生产环境，因为它很快就会达到Python堆栈限制，并且由于对fn的双重调用，在存在副作用函数的情况下可能会出现意外结果，但这应该足以给你一个想法。

- rxg