How To Write Foldr (right Fold) Generator In Python?

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 f

Solution 1:

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

deffoldr(op, lst):
    l, x = reversed(list(lst)), Nonefor i in l:
        ifnot 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

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

deffoldr(function, iterable, initializer=None):
    it = reversed(list(iterable))
    if initializer isNone:
        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

[Edit] 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.:

classDefer(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)

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

Defining a forever generator:

from itertools import repeat
defforever():
    yieldFalseyieldTruefor i in repeat(False):
        yield i

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

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

Solution 2:

You will have to catch appropriate exceptions but should be an idea of how to do it iteratively:

deffoldr(a, b, l):
    ifisinstance(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 isnot stop:
        yield c
        nxt = next(it, stop)
        c = a(nxt, c) if nxt isnot stop else c



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

Solution 3:

If you are going to define a function using generators, why not use the following?

deffoldr(op, lst):
    return reduce(op, reversed(lst))

Solution 4:

I think something like this is what you want:

deffoldr(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))

It's not exactly production-ready since it will hit the Python stack limit pretty quickly and it will be surprising in the presence of side-effecting functions due to the double call to fn, but it should be enough to give you an idea.