Table of Contents
If you just need to use
lazytree, you can just run:
$ pip install lazytree
For developers, note that this project uses the poetry python package/dependency management tool. Please familarize yourself with it and then run:
$ poetry install
LazyTree is a triple,
(root, child_map, view) where
root : A
and a child map,
child_map, which maps
a to a (finite) list of
child_map : A -> List[A] define the tree's structure and
view : A -> B defines what the tree represents. The default view is
the identity map,
lambda x: x.
This structure is useful for modeling infinite (or really large) trees where only a finite number of nodes need to be accessed. For example, the following Binary tree represents the recursive subdivision of the interval [0, 1].
from lazytree import LazyTree def split(itvl): lo, hi = itvl mid = lo + (hi - lo)/2 return (lo, mid), (mid, hi) tree = LazyTree( root=(0, 1), # Initial Itvl child_map=split # Itvl -> [Itvl] )
LazyTree object can be thought of as containing the pieces of data.
rootof the tree.
- The data represented by the
root, accessed via the
- The child subtrees - computed using
child_mapand accessed through the
For example, in our interval example, each node corresponds to an interval of
(0, 1) and has two child subtrees.
# View the current root. assert tree.view() == tree.root subtrees = tree.children assert len(subtrees) == 2
Often, for each node in a tree, one is interested in computing a particular function. This can be done using the
view methods. For example, below
map each interval in the tree to it's size. This results in a new
tree2 = tree.map(lambda itvl: itvl - itvl) # Change view to itvl size. assert tree2.view() == 1 # Access the root's subtrees subtrees = tree2.children assert len(subtrees) == 2 assert subtrees.root == (0, 0.5) assert subtrees.view() == 0.5
Travesals of a
LazyTree object are also implemented. For example,
# Breadth First Search through tree. ## Note: calls .view() before returning. itvls = tree.bfs() # returns a generator. sizes = tree2.bfs() # returns a generator. assert next(itvls) == (0, 1) assert next(sizes) == 1 assert next(itvls) == (0, 0.5) assert next(sizes) == 0.5 assert next(itvls) == (0.5, 1) assert next(sizes) == 0.5 # Cost guided traversal. ## Note: Smaller means higher priority. sizes = tree2.cost_guided_refinement(cost=lambda x: x) assert next(sizes) == 1 # (0, 1) assert next(sizes) == 0.5 # (0, 0.5) assert next(sizes) == 0.25 # (0, 0.25) # Iterative Deepening Depth First Traversal sizes = tree2.iddfs(max_depth=3) # returns a generator. assert list(sizes) == [1, 0.5, 0.5, 0.25, 0.25, 0.25, 0.25, 0.125, 0.125, 0.125, 0.125, 0.125, 0.125, 0.125, 0.125] # Note, you can reset the current view. tree3 = tree2.with_identity_view() assert tree3.view() == tree.view()
Finally, one can "prune" away subtrees by labeling them as leaf nodes using the
prune method. If you are sure that the resulting tree is finite (either due to pruning or the provided
child_map) then one can compute the leaves of the tree.
# Prune subtrees with a root of size less than 0.1. tree4 = tree2.prune(isleaf=lambda s: s < 0.2) sizes = tree.bfs() assert all(s > 0.001 for s in sizes) # Note that sizes is now finite. # Compute leafs of tree. Careful! Could be infinite! assert all(s == 0.125 for s in tree4.leaves()) assert len(list(tree4.leaves())) == 8