3

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.

asked May 20, 2015 at 15:48
3
  • 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. 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. 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). Commented May 20, 2015 at 17:12

1 Answer 1

2

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.

answered May 20, 2015 at 17:15

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.