1

I'm working on a question that requires me to define a function copy_tree that takes an argument tree (tuple that may contain tuples) and return a copy of the tree (ie. stored in a different memory location).

My current code is:

def copy_tree(tree):
    new_tree = ()
    for i in tree:
        new_i = (i,) + ()
        new_tree = new_tree + new_i
    return new_tree

However, this does not work for the nested tuples, as the tuples inside are not "copied" but rather referred to.

e.g. if I run

a = ((3, 2), 1, (4,), 5)
b = copy_tree(a)
print(a[0] is b[0])

the output has to be False.

How do I make the tuples copies?

Edit: I am not allowed to use the deepcopy module.

Ryan Chng
  • 117
  • 4
  • 10
  • Are you aware of the ``copy`` module? – MisterMiyagi Sep 18 '18 at 08:06
  • 1
    your code does not run. `TypeError: unsupported operand type(s) for +: 'int' and 'tuple'` – rocksportrocker Sep 18 '18 at 08:07
  • 3
    You can use `copy.deepcopy` or `tuple(map(tuple, tree))` if all are tuples, but why do you want to copy the tuples at all? Tuples are immutable. – tobias_k Sep 18 '18 at 08:08
  • you need to do `a[0]==b[0]`, i think, to compare the values. Here is more on that : https://stackoverflow.com/questions/132988/is-there-a-difference-between-and-is-in-python – jkhadka Sep 18 '18 at 08:09
  • @hadik that wouldn't work in this case, since a copied value will still compare equal to itself even if it's in a different memory address. – roganjosh Sep 18 '18 at 08:10
  • 1
    In fact, even `copy.deepcopy` will _not_ create a copy of the tuples (`is` same returns `True`) because it makes no real sense. – tobias_k Sep 18 '18 at 08:11
  • @hadik @roganjosh yeah, the question specifically wants me to write the code such that using the `is` operator will return `False`. No issue if `==` returns `True`. – Ryan Chng Sep 18 '18 at 08:11
  • I mostly agree with what tobias said. One of the benefits of using immutable objects is that it's safe for them to share references. OTOH, a tuple _can_ contain mutable objects, so this deep-copying operation isn't totally useless. ;) – PM 2Ring Sep 18 '18 at 08:12
  • @rocksportrocker you are right. Sorry, I copied the wrong code. Updated it with my latest code which runs and produces a visually correct result but does not pass the `is` test. – Ryan Chng Sep 18 '18 at 08:13
  • @PM2Ring Right, but since OP's code does neither create copies of the inner objects nor attempty to work recursively I assumed this not to be the case. – tobias_k Sep 18 '18 at 08:14
  • @tobias_k tuples are not completely immutable if their contents are immutable. eg. `([1], [2])`. If you wanted a deep copy of that tuple you would need to copy both it and its contents. – Dunes Sep 18 '18 at 08:14
  • @RyanChng it does pass the test on my computer, which python version are you using? – toti08 Sep 18 '18 at 08:15
  • 2
    @Dunes I am aware of that, but OP explicitly only attempty to copy the tuples, not their contents. See my above comment. – tobias_k Sep 18 '18 at 08:16
  • @toti08 it passes that test on mine too, but fails a bunch of private tests on the autograder website I use. I think the private cases involve more layers of nesting. – Ryan Chng Sep 18 '18 at 08:19
  • So you should write a recursive test function that compares two trees, applying the `is` test at every level. That way you can guarantee that `copy_tree` behaves correctly. – PM 2Ring Sep 18 '18 at 08:22

6 Answers6

3

Here is a recursive solution that deep copies (nested) tuples, leaves other objects unchanged, and doesn't use the copy module:

def copy_tree(tree):
    if isinstance(tree, tuple):
        return tuple(map(copy_tree, tree))
        # or, maybe more readable
        # return tuple(copy_tree(x) for x in tree)
    return tree

Recursion is definitely the most elegant approach if you do not know nesting levels in advance.

user2390182
  • 72,016
  • 6
  • 67
  • 89
1

Simply passing an existing tuple to the tuple constructor will not create a new copy of the constructor. Instead, you should pass an equivalent list to the tuple constructor to make a copy of a tuple:

def copy_tuple(t):
    output = []
    for i in t:
        if isinstance(i, tuple):
            output.append(copy_tuple(i))
        else:
            output.append(i)
    return tuple(output)

so that:

a = ((3, 2), 1, (4,), 5)
b = copy_tuple(a)
print(a)
print(b)
print(a[0] is b[0])

would output:

((3, 2), (4,), 5)
((3, 2), (4,), 5)
False
blhsing
  • 91,368
  • 6
  • 71
  • 106
  • Converting to `list` is a clever "hack" to prevent `tuple` from just returning the input, but you might add _why_ tuple behaves like this in the first place. – tobias_k Sep 18 '18 at 08:22
1

Your code is missing the recursive step - you only copy the top-level tuple.

def copy_tree(tree):
  new_tree = ()
  for i in tree:
    # i is not copied
    new_i = (i,) + ()
    new_tree = new_tree + new_i
  return new_tree

Adding recursion produces copies of every layer of the tree. Note that you may copy only tuples:

def copy_tree(tree):
  new_tree = ()
  for i in tree:
    # recursively copy i *if it is a tuple*
    if isinstance(i, tuple):
      new_i = (copy_tree(i),)
    else:
      new_i = (i,)
    new_tree = new_tree + new_i
  return new_tree

Recursion fixes the result, but the approach you have taken is inefficient - there are many transient tuples created and thrown away. Every time a tuple is "extended" via +, the old one is thrown away and a new one created.

A first step is to delay creation of the tuple until all children are converted:

def copy_tree(tree):
    children = []
    for child in tree:
        # we *always* preserve a child, so ternary if expresses this better
        child = copy_tree(child) if isinstance(child, tuple) else child
        children.append(child)
    # create a new tuple including all children
    return tuple(children)

Since that list only exists to be turned into a tuple, we can get rid of that as well: a generator expression allows to feed the converted children directly to the tuple constructor.

def copy_tree(tree):
    # generator expression - only run when consumed by tuple later on
    children = (
        copy_tree(child) if isinstance(child, tuple) else child
        for child in tree
    )
    return tuple(children)

Of course, you can also directly put the generator expression inside the tuple.

MisterMiyagi
  • 44,374
  • 10
  • 104
  • 119
  • 1
    This actually worked, thanks! I haven't learned isinstance yet, but I substituted that line with `if type(i) == tuple`. I'm still learning at an introductory level, so I don't think they are looking for the following solutions you posted - but the first one aids in my understanding well. Thanks so much! – Ryan Chng Sep 18 '18 at 08:32
  • 1
    @RyanChng `isinstance` is generally preferred over `type` for this sort of thing. It doesn't matter here, but `isinstance` is more flexible, since it can test multiple types in one go, and `isinstance(obj, cls)` will return True if `obj` is an instance of `cls` or any child class of `cls`. – PM 2Ring Sep 18 '18 at 08:51
0

I think that the intention of the question was to use some sort of recursion. The following code would deep copy the tree recursively.

def copy_tree(tree):
    new_tree = ()
    for node in tree:
        if type(node) == tuple:
            new_tree += (copy_tree(node),)
        else:
            new_tree += (node,)
    return new_tree


a = ((3, 2), 1, (4,), 5)
b = copy_tree(a)

print(a[0] is b[0])

and the last print would give you False.

Farzad Vertigo
  • 2,458
  • 1
  • 29
  • 32
0

Here's a simple version that copies the tree by feeding the tuple constructor with a recursive generator. To test it, I've written another recursive function compare_trees, which you can use to check that corresponding tuples aren't identical (using is), and that corresponding inner items have the same value (using ==).

def copy_tree(tree):
    return tuple(copy_tree(u) if isinstance(u, tuple) else u for u in tree)

def compare_trees(tree1, tree2, indent=''):
    print(indent, 'tree1', tree1, 'tree2', tree2, 'identical', tree1 is tree2)
    indent += '  '
    for u1, u2 in zip(tree1, tree2):
        if isinstance(u1, tuple) and isinstance(u2, tuple):
            compare_trees(u1, u2, indent)
        else:
            print(indent, 'item1', u1, 'item2', u2, 'equal', u1 == u2)

a = ((3, 2), 1, (4,), 5, (6, (7, 8)))
b = copy_tree(a)
print(b)
compare_trees(a, b)

output

((3, 2), 1, (4,), 5, (6, (7, 8)))
 tree1 ((3, 2), 1, (4,), 5, (6, (7, 8))) tree2 ((3, 2), 1, (4,), 5, (6, (7, 8))) identical False
   tree1 (3, 2) tree2 (3, 2) identical False
     item1 3 item2 3 equal True
     item1 2 item2 2 equal True
   item1 1 item2 1 equal True
   tree1 (4,) tree2 (4,) identical False
     item1 4 item2 4 equal True
   item1 5 item2 5 equal True
   tree1 (6, (7, 8)) tree2 (6, (7, 8)) identical False
     item1 6 item2 6 equal True
     tree1 (7, 8) tree2 (7, 8) identical False
       item1 7 item2 7 equal True
       item1 8 item2 8 equal True

I suppose that it's a little ironic that the test code is larger and more complex than the code we want to test, but sometimes that's inevitable. ;)

PM 2Ring
  • 54,345
  • 6
  • 82
  • 182
-1

You should use the copy module.

This module has two functions to fit your needs, copy and deepcopy. copy does the same than copy_tree.

For example if you do : 

import copy
l = [[0],[0]]
l2 = copy.copy(l)
l[0] = [1]
l[1][0] = [1]

Then l2 will be [[0],[1]] The first element of l2 has not changed because you replaced l first element. However, the second element has changed because you mutated the second element of l, which is a reference to the element of l2.

If you use deepcopy:

 import copy
 l = [[0],[0]]
 l2 = copy.deepcopy(l)
 l[0] = [1]
 l[1][0] = [1]

Then l2 will be [[0],[0]] because l and l2 does not share anything in common anymore.

Corentin Limier
  • 4,946
  • 1
  • 13
  • 24