Zii8roZi Zii8roZi - 1 year ago 48
Python Question

visit all elements in nested lists and dicts without recursion

I have a structure consisting of nested lists and dicts. I want to apply a
function to every element. How to do it without recursion.

def visit(data, func):
if isinstance(data, dict):
for k, v in data.items():
data[k] = visit(v, func)
return data
elif isinstance(data, list):
for i, v in enumerate(data):
data[i] = visit(v, func)
return data
return func(data)

The recursive version works for small data, but I hit the RecursionError
exception when the data is big.

I looked for general ways to eliminate recursion, the ones I found rely on
first transforming the recursive call to a tail call, my problem with this is
the recursive call in my example is inside a loop.

Answer Source

This approach will work. For the record, though, I agree with Sven Marnach that there is something definitely fishy going on with your data structures if you have nesting that is breaking the recursion limit. If as Sven conjectures,you have cycles in your data, this approach will also break. Although, I suppose if you had a list of ~1000 lists, that would also break the recursion limit...

data = [1,2, {'a':1, 'b':{'a':[1,2,3]}},3]

def apply(data, f):
    stack = []
    while stack:
        data = stack.pop()
        if isinstance(data, dict):
            for k,v in data.items():
                if isinstance(v, (dict,list)):
                    data[k] = f(v)
        if isinstance(data, list):
            for i,e in enumerate(data):
                if isinstance(e, (dict,list)):
                    data[i] = f(e)

In the interpreter shell:

$ python -i apply.py
>>> apply(data, lambda x: x + 1)
>>> data
[2, 3, {'a': 2, 'b': {'a': [2, 3, 4]}}, 4]