I am writing a library for working with special types of trees, called Foo trees. A Foo tree has very special structure. There some operations, called bar and baz, which only make sense on Foo trees. So I'm designing a FooTree class to represent Foo trees.

To construct a FooTree instance, one might pass some object representing a tree. This object will be checked for special structure and stored internally:

class FooTree(object):

    def __init__(self, tree):
        ... # check that tree is a valid Foo tree
        self._tree = tree

    def bar(self):
        # operation that only makes sense on a foo tree

The problem is: what if I construct a FooTree from a mutable object? For example, say Tree is a type whose instances are mutable:

tree = Tree()
... # build a valid Foo tree
foo_tree = FooTree(tree)
tree.remove_node(0) # tree is no longer a Foo tree

Since tree is no longer a valid Foo tree, and foo_tree wraps a reference to tree, foo_tree is no longer valid.

Instead I might copy the tree when creating a FooTree:

class FooTree(object):

    def __init__(self, tree):
        ... # check that tree is a valid Foo tree
        self._tree = tree.copy()

    def bar(self):
        # operation that only makes sense on a foo tree

This solves the problem, but creates a new one: Foo trees are typically very large, so copying them is expensive.

What patterns exist for creating FooTree objects from Tree objects, without copying and without the mutability problem?

For example, I might have FooTree accept a callable which produces a Tree:

class FooTreeBuilder(object):
    def __init__(self, data):
        self.data = data

    def __call__(self):
        tree = Tree()
        ... # build tree from self.data
        return tree

class FooTree(object):

    def __init__(self, builder):
        self._tree = builder()

builder = FooTreeBuilder(data)
foo_tree = FooTree(builder)

Are there any better approaches? I'm specifically looking for approaches that lend well to Python implementations.

  • Without copying you can't solve this. Names in Python are references to objects, so if the object is mutable, unless you guarantee you hold the only reference you can't guarantee something holding another reference hasn't mutated it.
    – jonrsharpe
    Commented May 20, 2015 at 16:51
  • @jonrsharpe I can't guarantee I have the only reference, sure, but I can make reasonably sure that I do, as is the case with the FooTreeBuilder example I've given. What I'm looking for are suggestions for similar patterns, or arguments for why the former case (allowing the reference to be mutated) is OK.
    – jme
    Commented May 20, 2015 at 17:07
  • 1
    If it wasn't ok, you'd be using an immutable object! The builder isn't really solving the same problem, as you're starting from a different point than an existing tree (or if the tree does exist, rebuilding is no different to copying).
    – jonrsharpe
    Commented May 20, 2015 at 17:12

1 Answer 1


some options are:

  • using immutable trees as basic data structure
  • using a builder or mutation operations to construct a FooTree without needing a Tree
  • copying the input tree (which is good practice unless you have really big data and performance issues)

Note that by builder I mean the builder pattern as described by Joshua Bloch. (Long article, but the design issue is relevant for Python just as it is for Java.) Your Builder callable does not really mitigate the problem, because if a user of FooTree already has a Tree, they will just call FooTree(lambda: myTree) and thus you'll have the mutability problem again.

The builder pattern (or making making FooTree mutable), on the other hand, allow your users to create FooTrees directly without needing a Tree first.

and the best choice depends on:

  • whether Tree is a class that you can design (and make immutable) as opposed to using something that is given.
  • in your application domain: do trees change often or is immutability actually a good abstraction?
  • how much separation you want between your own FooTrees and the other Trees. Maybe copying the tree has good side benefits like using a specialized data structure for your own trees.
  • do you actually need trees anyways? are they your given input material? or would a solution without the Tree class make any sense?

All of this is independent of the language who are using and making it Pythonic is a matter of implementing the chosen design.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.