Pythonic way for recursive reduction in python

Question

While reducing a list in python, I have thought about creating a multiple list reduction and wrote the following snippet.

def multiply(a, b): return a * b

def recursive_reduce(reduce_func, *args):
     ret_val = reduce(reduce_func, *args)
     if type(ret_val) == list:
         ret_val = recursive_reduce(reduce_func, ret_val)
     return ret_val

a = [1, 1, 3]
b = [4, 5, 6]

recursive_reduce(multiply, a, b)

This works. However I would like to know whether defining the logic for iteration based on the type of the return value is pythonic or not.

Do we have any other way which accomplishes recursive reduction in more elegant way?

Answer 1

I think what you're trying to do is do a recursive version of reduce.

def rreduce(f, init, default=None):                     
    if default is None:
        default = init[0]
        init = init[1:]
    if len(init) == 0:
         return default
    return rreduce(f, init[1:], f(default, init[0]))


>>> rreduce(lambda a, b: a*b, range(1,10))
362880
>>> rreduce(lambda a, b: a+b, ['t', 'a', 'c', 'o'])
'taco'

While recursion is great, this is not the preferred way in Python for reduce type functions because it is slow and you will hit a STACK OVERFLOW (HAA)

>>> rreduce(lambda a, b: a + [b], list(range(1, 10000)), [])
---------------------------------------------------------------------------
RecursionError                            Traceback (most recent call last)
<ipython-input-41-7dc07c5d9246> in <module>()
----> 1 rreduce(lambda a, b: a + [b], list(range(1, 10000)), [])

<ipython-input-33-37206eb8e39f> in rreduce(f, init, default)
      5     if len(init) == 0:
      6         return default
----> 7     return rreduce(f, init[1:], f(default, init[0]))

... last 1 frames repeated, from the frame below ...

<ipython-input-33-37206eb8e39f> in rreduce(f, init, default)
      5     if len(init) == 0:
      6         return default
----> 7     return rreduce(f, init[1:], f(default, init[0]))

RecursionError: maximum recursion depth exceeded in comparison

To answer your ACTUAL question...

def lreduce(f, init, default=None):
        if default is None:
            return reduce(lambda x, a: x + [reduce(f, a)], init, [])
        else:
            return reduce(lambda x, a: x + [reduce(f, a, default)], init, [])

will reduce a list of lists.

>>> lreduce(lambda a, b: a + b, [range(10), range(10), range(10)])
[45, 45, 45]

The reason the if/else is necessary is because reduce as a builtin does not accept keyword arguments:

In [56]: reduce(function=lambda a, b: a + b, sequence=range(10), initial=0)
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-56-9fa3ed177831> in <module>()
----> 1 reduce(function=lambda a, b: a + b, sequence=range(10), initial=0)

TypeError: reduce() takes no keyword arguments

and then if you wanted to do one step further...

def lreduceall(f, init, default=None):
    if default is None:
        return reduce(f, reduce(lambda x, a: x + [reduce(f, a)], init, []))
    else:
        return reduce(f, reduce(lambda x, a: x + [reduce(f, a, default)], init, []), default)

finally:

>>> lreduceall(lambda a, b: a + b, [range(10), range(10), range(10)])
135