Python library for manipulating infinite trees.

# Installation

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`

# Usage

A `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 children `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]
)
```

Conceptually a `LazyTree` object can be thought of as containing the pieces of data.

1. The `root` of the tree.
2. The data represented by the `root`, accessed via the `view` method.
3. The child subtrees - computed using `child_map` and accessed through the `.children` attribute.

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 `map` and `view` methods. For example, below `map` each interval in the tree to it's size. This results in a new `LazyTree` object.

```tree2 = tree.map(lambda itvl: itvl[1] - itvl[0])  # Change view to itvl size.
assert tree2.view() == 1

# Access the root's subtrees
subtrees = tree2.children
assert len(subtrees) == 2
assert subtrees[0].root == (0, 0.5)
assert subtrees[0].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
```