如何在Python中编写foldr(正确折叠)生成器? [英] How to write foldr (right fold) generator in Python?

问题描述

Python的 reduce 是向左折叠的，这意味着它是尾递归的，并且其用法可以整齐地重写为循环.但是，Python没有内置的函数可以进行正确的折叠.由于右折最自然地是用递归编写的(Python不像函数语言那样喜欢递归)，所以我对用生成器编写右折( folder )感兴趣.

Python's reduce is a left-fold, which means it is tail-recursive and its uses can be neatly rewritten as a loop. However, Python does not have a built-in function for doing right folds. Since right-folds are most naturally written with recursion (and Python doesn't like recursion as much as functional languages), I'm interested in writing a right fold (foldr) in terms of a generator.

这怎么办?而且非常具体地讲，如何在Python 2.7中完成?

How can this be done? And very specifically, how can it be done in Python 2.7?

我应该提到 folder 的好处之一是，您有时可以在无限列表上进行折叠，而不会冒着吞噬您的堆栈的风险.我希望看到保留此属性的答案.

I should have mentioned that one of the benefits to foldr is that you can sometimes fold on infinite lists without risk of eating your stack alive. I would like to see answers that preserve this property.

例如，Haskell的 folder 在输入和输出上都是惰性的，并且可以使短路的步进"功能在长/无限输入上起作用:

For example, Haskell's foldr is lazy on both input and output and can allow for short-circuiting "step" functions to work on long/infinite inputs:

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

任何使用 list / reversed /etc的Python变体.如果指定了 itertools.repeat(some_value)，则输入中的内容将挂起.

Any Python variant that uses list/reversed/etc. on the input will hang if given itertools.repeat(some_value).

请注意，由于严格性，在同一示例中Python的 reduce 令人窒息:

Note that Python's reduce chokes in the same example because of strictness:

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

推荐答案

所以是python中的简单生成器(没有适当的错误检查):

So a simple generator in python (without appropriate error checking):

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的大致等效"实现几乎相同:

Almost identical to the 'roughly equivalent' implementation of reduce in the documentation:

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

因此，纯粹是一种锻炼，几乎没有实用价值，只要您折叠的功能之间存在某种协作，就可以推迟...例如:

So purely as an exercise of the mind and with very little practical value, it is possible to defer as long as there is some cooperation between the function that you a folding over... e.g.:

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

然后，只要函数转换为正确的类型，您就可以推迟计算，但是这不适用于本机运算符，因此不确定此函数的实际用途是什么:

Then as long as the function converts to the right type you can defer the calculation, however this will not work with native operators, so not sure how useful this really is:

>>> 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时返回

Folding or across an infinite list, returns when it finds a True

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

这篇关于如何在Python中编写foldr(正确折叠)生成器?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！