2015-03-31 52 views
3

Python的reduce是一个左边的折叠,这意味着它是尾递归的,它的使用可以整齐地重写为一个循环。但是,Python没有内置函数来执行正确的折叠。由于右褶最自然地用递归方式编写(而且Python不像函数式语言那样喜欢递归),所以我有兴趣根据生成器编写正确的折叠(foldr)。如何在Python中编写foldr(右对齐)生成器?

这怎么办?具体而言,Python 2.7如何实现?

编辑:我应该提到foldr的好处之一是,你有时可以在无限列表上折叠,而没有吃死你的栈的风险。我想看到保留此属性的答案。

例如,Haskell的foldr是在两个输入和输出懒惰并且可以允许短路“步骤”的功能,以在长/无限输入工作:

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

我认为为了做到这一点,你的发电机必须“产生”一个发电机,它产生一个发电机......如果传递的参数是一个空列表,那么yield就是初始值...这听起来有点令人头痛,坦率地说...... Python在递归方面很好,只要它具有合理的深度,但我不完全确定递归和生成器在一起很好地发挥了... – twalberg 2015-03-31 16:58:30

+0

haskell foldr的定义只是简化,foldl将在无限列表中失败。 – AChampion 2015-03-31 17:57:23

+0

Python的'reduce'是左对齐的,所以它就像Haskell的'foldl'(注意素数)。是的,'foldl'及其变体将在无限的列表上失败,这就是为什么人们可能希望使用正确的折叠。 – 2015-03-31 18:04:35

回答

2

因此,一个简单的发电机在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 i n个文件:

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 

跨越无限列表折叠or,返回时,发现一个真正的

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

如果'lst'是一个发电机? – 2015-03-31 17:31:56

+0

然后,您需要对迭代操作...'l = list(lst)'。您将需要扩展完整的生成器才能执行foldr。 – AChampion 2015-03-31 17:33:40

+0

对不起,请参阅编辑。 – 2015-03-31 17:35:12

1

你必须抓住适当的例外,但应该是怎样的想法迭代执行:

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) 
+0

如果'l'本身就是一个发电机? – 2015-03-31 17:31:35

+0

@ 3noch,你不能反转一个生成器/迭代器,所以它将取决于你认为是一个可接受的替代 – 2015-03-31 17:34:13

+0

道歉:请参阅编辑 – 2015-03-31 17:35:35

0

如果您要使用生成器定义函数,为什么n不要使用以下内容?

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