Traverse a nested list

Question

I'm trying to use recursion to traverse a list and append all its non-list elements and the elemnents of the sublists to a unique list.

def refr(a_list):
    loo = []
    for item in a_list:
        if isinstance(item, list):
            refr(item)
        else:
            loo.append(item)
    return loo

print(refr([1, ['no', 'ok'], 'dang', 0]))

When I define loo as a local variable it only contains the elements of the input list that are not representing a list.

# output

[1, 'dang', 0]

But when defined it as globlal the output is correct

# output

[1, 'no', 'ok', 'dang', 0]

Why so?

Does this answer your question? [Flatten an irregular list of lists](https://stackoverflow.com/questions/2158395/flatten-an-irregular-list-of-lists) — user2390182, Sep 01 '21 at 07:02
@schwobaseggl If there is a duplicate, it should be more along the lines of "why value of recursive call is discarded?"; the error here is that the return value of the recursive call `refr(item)` is not used. Apart from that, the OP appears to have understood the basic idea of how to traverse an irregular list of lists, and closing their question to refer them to that one won' be any help. — Stef, Sep 01 '21 at 08:31
@Stef True, hence my answer. Btw, you can add better duplicates. There are literally dozens of questions like "why does recursive function return None" and it's always this very issue. — user2390182, Sep 01 '21 at 08:34
@schwobaseggl Yes, I did upvote your answer. "Why is recursive function returning None" was my first instinct, but actually, the OP's function doesn't return None. It always returns a list; the list just omits some values that were computed during the recursive call. — Stef, Sep 01 '21 at 08:41
Yeah, dupes don't have to be that exact. Both the answers to my linked dupe and those to any of the "recursive None" questions will hold all the information needed for the OP to solve their problem. — user2390182, Sep 01 '21 at 08:45

user2390182 · Answer 1 · 2021-09-01T08:15:45.847

You are not using the return value of your recursive call:

def refr(a_list):
    loo = []
    for item in a_list:
        if isinstance(item, list):
            loo += refr(item)
        else:
            loo.append(item)
    return loo

Or, using a generator function, which is often sufficient, allows short-circuiting and can easily be turned into a list:

def refr(a_list):
    for item in a_list:
        if isinstance(item, list):
            yield from refr(item)
        else:
            yield item

From here, it is not far to a one-liner, using itertools.chain:

from itertools import chain

def refr(a_list):
    return chain.from_iterable(refr(x) if isinstance(x, list) else [x] for x in a_list)

[*refr([1, ['no', 'ok', [1, 2, [3]]], 'dang', 0])]
# [1, 'no', 'ok', 1, 2, 3, 'dang', 0]

I'mahdi · Answer 2 · 2021-09-02T05:33:25.860

use extend(item) from document:

list.extend(iterable) Extend the list by appending all the items from the iterable. Equivalent to a[len(a):] = iterable.

try this:

def refr(a_list):
    loo = []
    for item in a_list:
        if isinstance(item, list):
            loo.extend(refr(item))
            # OR
            # loo += refr(item)
        else:
            loo.append(item)
    return loo

print(refr([1, ['no', 'ok'], 'dang', 0]))

output:

[1, 'no', 'ok', 'dang', 0]

for this input get correct output:

print(refr([1, [['no', 'ok'], ['dang', 0]]]))
# [1, 'no', 'ok', 'dang', 0]

Jan Wilamowski · Answer 3 · 2021-09-01T08:01:16.500

1

Because the scope of the local (!) loo variable is the refr function for that specific invocation. That means when you call refr recursively, it will create a new stack frame with another empty list that has nothing to do with the first one (it just happens to have the same name). One way to solve this is to add an accumulator parameter to your function call that serves as the combined state:

def refr(a_list, acc=None):
    if acc is None:
        acc = []
    for item in a_list:
        if isinstance(item, list):
            refr(item, acc)
        else:
            acc.append(item)
    return acc

refr([1, ['no', 'ok'], 'dang', 0])

gives

[1, 'no', 'ok', 'dang', 0]

edited Sep 01 '21 at 08:01

answered Sep 01 '21 at 06:53

Jan Wilamowski

3,308
2
10
23

1

The function will fail when called for the second time. Please read: https://stackoverflow.com/questions/1132941/least-astonishment-and-the-mutable-default-argument – blhsing Sep 01 '21 at 07:47
1

@blhsing you're right of course, I was sloppy. Fixed it. Thanks for pointing it out. – Jan Wilamowski Sep 01 '21 at 08:01

Traverse a nested list

3 Answers3