reverse method mutating input

Question

For an assignment we were asked to create a function that would reverse all the elements in an arbitrarily nested list. So inputs to the function should return something like this:

>>> seq = [1,[2,[3]]]
>>> print arb_reverse(seq)
[[[3],2],1]
>>> seq = [9,[[],[0,1,[[],[2,[[],3]]]],[],[[[4],5]]]]
>>> print arb_reverse(seq)
[[[[5,[4]]],[],[[[[3,[]],2],[]],1,0],[]],9]

I came up with a recursive solution which works well:

def arb_reverse(seq):
    result = []
    for element in reversed(seq):
        if not is_list(element):
            result.append(element)
        else:
            result.append(arb_reverse(element))
    return result

But for a bit of a personal challenge I wanted to create a solution without the use of recursion. One version of this attempt resulted in some curious behavior which I am not understanding. For clarification, I was NOT expecting this version to work properly but the resulting input mutation does not make sense. Here is the iterative version in question:

def arb_reverse(seq):
    elements = list(seq)   #so input is not mutated, also tried seq[:] just to be thorough
    result = []
    while elements:
        item = elements.pop()
        if isinstance(item, list):
            item.reverse() #this operation seems to be the culprit
            elements += item 
        else:
            result.append(item)
    return result

This returns a flattened semi-reversed list (somewhat expected), but the interesting part is what it does to the input (not expected)...

>>> a = [1, [2, [3]]]
>>> arb_reverse(a)
[2, 3, 1]
>>> a
[1, [[3], 2]]
>>> p = [1, [2, 3, [4, [5, 6]]]]
>>> print arb_reverse(p)
[2, 3, 4, 5, 6, 1]
>>> print p
[1, [[[6, 5], 4], 3, 2]]

I was under the impression that by passing the values contained in the input to a variable using list() or input[:] as i did with elements, that I would avoid mutating the input. However, a few print statements later revealed that the reverse method had a hand in mutating the original list. Why is that?

Answer 1

The list() call is making a new list with shallow-copied lists from the original.

Try this (stolen from here):

from copy import deepcopy
listB = deepcopy(listA)

Answer 2

Try running the following code through this tool http://people.csail.mit.edu/pgbovine/python/tutor.html

o1 = [1, 2, 3]
o2 = [4, 5, 6]

l1 = [o1, o2]

l2 = list(l1)

l2[0].reverse()

print l2
print l1

Specifically look at what happens when l2[0].reverse() is called.

You'll see that when you call list() to create a copy of the list, the lists still reference the same objects.