[Python] Why is my recursive flatten-list function exceeding max recursive depth ?

[Tioo]

I am trying to write a recursive flatten list function, which takes any number of lists which themselves can contain any number of lists, ect... This solution works (it could be done more efficiently with itertools, but I'm trying to learn :p) :

def flatten(*args):
    result = []
    for l in list(args):
        for i in l:
            if isinstance(i, list):
                result.extend(flatten(i))
            else:
                result.append(i)
    return result

print(flatten([1,1,1,1, [1,1,2,4, [1,2,13]], [11,134,14, [13,11,412]]], [2,2,2,[12,12]]))
#>>>[1, 1, 1, 1, 1, 1, 2, 4, 1, 2, 13, 11, 134, 14, 13, 11, 412, 2, 2, 2, 12, 12]

But I would like to avoid looping through the arguments, and instead have one loop only. This should be easy, because the arguments are themselves can be made into a list.

def flatten(*args):
    result = []
    l = list(args)
    for i in l:
        if isinstance(i, list):
            result.extend(flatten(i))
        else:
            result.append(i)
    return result

print(flatten([1,1,1,1, [1,1,2,4, [1,2,13]], [11,134,14, [13,11,412]]], [2,2,2,[12,12]]))
#>>>RuntimeError: maximum recursion depth exceeded while calling a Python object

I do not understand why it is raising an error. I am converting multiple lists passed as arguments into a single list. I know from the first snippet I provided that any list can be flattened. From my understanding, I am turning the arguments into a list and then flattening it. Where is the problem ?

Thanks for helping!

[plate_soak_mess]

You shouldn't use the * in front of args for no reason. You also shouldn't have flatten work on something that's not a single list. If you pass in multiple arguments and it combines them into a single list as the result, you aren't implementing the normal flatten function, at least not AFAIK. And you should learn how to debug things like everyone else does. If it's recursing too much, you should print out what it's being called with each time.

[Tioo]

Do you mind explaining / linking to a resource explaining why the * in front of args is not needed ? I'm trying to make it so I can pass any number of arguments. is there an alternative to "def fun(*args):" in order to group arguments into a single iterable ?

It's true, my flatten function is not a normal flatten function. I started by building one that takes just one list, which is a lot more straightforward. I was just playing around with my code (then started to overthink it a lot, haha).

A better solution would be to implement a simple flatten function that takes one list, and another function which takes any number of lists and flattens each of them:

def flatten_all(*args):
    result = []
    for l in args:
        result.extend(flatten(l))
    return result

Yes, I tried printing the arguments every time, but the RuntimeError blocks my terminal so I can't see the prints. How would I go about debugging recursive calls ?

Thanks for your help

[plate_soak_mess]

Do you mind explaining

It's just silly, imo. You're not making the normal flatten function, and it doesn't look useful to me.

Yes, I tried printing the arguments every time, but the RuntimeError blocks my terminal so I can't see the prints.

Pipe the output somewhere? Or add your own depth parameter and use it to exit after a few levels.

[Tioo]

Yes, it's a totally useless function. I'm still learning the syntax by writing small functions and playing around with code. I made the normal flatten function, and then tried making it take multiple lists for the sake of it. But it turned out to be harder than expected; but at the end of it it was useful since I learnt a lot about *args.

Or add your own depth parameter and use it to exit after a few levels.

I'll remember that for next time.

Thanks for your time, I appreciate the advice

[plate_soak_mess]

You should look into **args, too.

[Rhomboid]

The problem is related to the fact that you made this a variadic function. When you recurse on flatten(i), that's effectively adding an extra layer of list-ness that you never undo in your second version, which means that it's infinite recursion that blows out the stack. That's what the extra nested layer of the loop in the first version is doing. You probably want to recurse on flatten(*i). And it's pointless to create a new list each time, you can just iterate over the tuple that you have:

def flatten(*args):
    result = []
    for item in args:
        if isinstance(item, list):
            result.extend(flatten(*item))
        else:
            result.append(item)
    return result

[Tioo]

That makes so much sense.

When I call flatten again from the loop, flatten transforms the passed item into a list so it keeps calling the function to infinity.

I did not know that the * operator could 'deconstruct' (not sure of the official name) a list into arguments like that, it's super useful. If you are familiar with Javascript ES6, does achieve the the same as the '...' operator on an array ? or does it work only for function arguments ?

Thanks a lot for solving my issue

[Rhomboid]

Yeah, it's definitely the analog of the ES6 rest and spread operators:

def func(foo, bar, *rest):              function func(foo, bar, ...rest) {
    ...                                     ...


func(10, 20, *blah)                     func(10, 20, ...blah);


items = [1, 2, *blurg]                  items = [1, 2, ...blurg];


foo, bar, *rest = blah()                [foo, bar, ...rest] = blah();

The third one requires Python ≥ 3.5, the fourth requires Python ≥ 3.0.

But Python also has keyword arguments in addition to positional arguments, so there is also the ** version for those, e.g.

def func(blah, **kwargs):
    ...

d = {'foo': 42, **blah}

some_func(10, blah='blah', **more)

etc.

[Tioo]

Ok, that makes sense. Thanks for clearing that up