Recursively emptying a nested list while preserving its structure

Question

I was trying to write a function that reads a list with lists in it and gives back the same list structure but without elements.

def remove_from_list(l):
    for e in l:
        if isinstance(e, list):
            remove_from_list(e)
        else:
            l.remove(e)
    return l

So for input like this:

[1, 2, [], [3,[4]], 5]

I should get something like this:

[[], [[]]]

I tried with these inputs:

[1, 2, [], [3,[4]], 5]
[1, 2, [], [2,[3]], 2]

And got these outputs:

[2, [], [[4]]]
[[], [[3]], 2]

Which is very confusing because the structure of both lists is the same; only the elements differ. So not only do I get a mistake, but I get a different one. Help with the function and explanation of my mistake would be very appreciated.

Answer 1

The key issue here is the fact that the for loop has a set number of iterations, but when you remove lists inside the loop, you're shrinking them. So, the loop pointer remains fixed while the list becomes smaller. At one point, the loop does not get the opportunity to finish iteration.

Option 1
As an easy fix, you can just create a new list inside the function. This should be simpler, and does not mutate your original list.

def remove_from_list(l):
    r = []
    for e in l:
        if isinstance(e, list):
            r.append(remove_from_list(e))
    return r

>>> remove_from_list([1, 2, [], [3,[4]], 5])
[[], [[]]]

Furthermore, since you're only appending empty structures, this should be faster than creating copies of your data and subsequent remove calls.

---

Option 2
Building on wim's idea, iterate in reverse and use del if you want to mutate the list in place.

def remove_from_list(l):
    r = []
    for i in range(len(l) - 1, -1, -1):
        if isinstance(l[i], list):
            remove_from_list(l[i])
        else:
            del l[i]

>>> l = [1, 2, [], [3,[4]], 5]
>>> remove_from_list(l)
>>> l
[[], [[]]]

I would recommend, from the perspective of good practice, to either return a copy, or modify in place without returning, but not both.

---

You can perform a timeit comparison to determine which method works faster on your data.

First, the setup -

def remove_from_list(l):
    r = []
    for e in l:
        if isinstance(e, list):
            r.append(remove_from_list(e))
    return r

def remove_from_list_reverse_del(l):
    r = []
    for i in range(len(l) - 1, -1, -1):
        if isinstance(l[i], list):
            remove_from_list(l[i])
        else:
            del l[i]


def remove_from_list_copy(l):
    for e in l[:]: # make a copy by slicing
        if isinstance(e, list):
            remove_from_list_copy(e)
        else:
            l.remove(e)
    return l

y = [1, 2, [], [3,[4]], 5]
z = copy.deepcopy(y  * 10000)

Next, the timings -

%timeit remove_from_list(z)
19.3 ms ± 334 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

%%timeit
z2 = copy.deepcopy(z)    # copying because this function mutates the original
remove_from_list_reverse_del(z2)

78.6 ms ± 157 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

Although a big chunk of time is wasted in creating z2.

Answer 2

What happened to good old fashioned recursion? (By the way, this answer also handles lists that contain references to themselves.)

def f(l, i, ids):
  if i >= len(l):
    return l
  if isinstance(l[i], list):
    if not id(l[i]) in ids:
      ids.add(id(l[i]))
      f(l[i], 0, ids)
    return f(l, i + 1, ids)
  else:
    del l[i]
    return f(l, i, ids)

a = [1, 2, [], [3,[4]], 5]
a.append(a)
a[3].append(a[3])

print a # [1, 2, [], [3, [4], [...]], 5, [...]]
print f(a, 0, set([id(a)])) # [[], [[], [...]], [...]]

(As for your misunderstanding - as cᴏʟᴅsᴘᴇᴇᴅ mentioned, deleting parts of a list during the for loop can cause unexpected results since the range of iteration is set before it starts, yet the list gets modified partway through.)