AlgoTree is a tree manipulation library for Python. Version 2.0 is a complete redesign built on immutable-by-default principles with composable transformers and pattern-matching selectors.
Why immutable trees?
Mutable tree libraries have hidden costs. Modifying a tree can break other code holding references to it. Changes are hard to track during debugging. Concurrent modifications cause subtle bugs. The usual story.
AlgoTree takes a different approach: all operations return new tree objects. The original is never modified.
from AlgoTree import Node, node
# Build a tree
tree = node("root",
node("child1", value=1),
node("child2", value=2)
)
# All operations return new trees
tree2 = tree.with_name("new_root") # tree unchanged
tree3 = tree.with_child(Node("child3")) # tree unchanged
This is the same idea behind persistent data structures in Clojure or Haskell. Immutability eliminates a whole class of bugs at the cost of some allocation overhead. For tree manipulation tasks (as opposed to, say, hot inner loops), the tradeoff is worth it.
Building Trees
Multiple construction styles for different use cases:
from AlgoTree import Node, node, TreeBuilder
# Simple construction with Node
tree = Node("root",
Node("child1", attrs={"value": 1}),
Node("child2", attrs={"value": 2})
)
# Convenience function (auto-converts strings)
tree = node("root",
node("child1", value=1),
"child2", # Strings auto-convert to nodes
node("child3",
"grandchild1",
"grandchild2"
)
)
# Fluent builder API
tree = (TreeBuilder("root", type="container")
.child("src")
.child("main.py", type="file", size=1024)
.child("utils.py", type="file", size=512)
.up()
.child("docs")
.child("README.md", type="file")
.build())
Functional Transformations
The standard functional toolkit, applied to trees:
# Map: transform all nodes
doubled = tree.map(lambda n: n.with_attrs(
value=n.get("value", 0) * 2
))
# Filter: keep nodes matching predicate
filtered = tree.filter(lambda n: n.get("value", 0) > 5)
# Find: locate specific nodes
nodes = tree.find_all(lambda n: n.is_leaf)
Composable Selectors
Pattern matching with wildcards and logical composition:
from AlgoTree import name, attrs, leaf, type_
# Pattern matching with wildcards
selector = name("*.txt")
# Attribute matching with predicates
selector = attrs(size=lambda s: s > 1000)
# Logical composition with operators
selector = type_("file") & ~leaf() # Files that aren't leaves
# Structural selectors
selector = type_("file").child_of(name("src"))
selector = leaf().at_depth(2)
# Use selectors with trees
matching_nodes = list(selector.select(tree))
The selectors compose with &, |, and ~. This means you can build complex queries from simple parts without writing custom traversal code.
Pipe-Based Transformers
Build transformation pipelines with the >> operator:
from AlgoTree import map_, filter_, prune, normalize, extract
# Build transformation pipelines
pipeline = (
map_(lambda n: {"processed": True}) >>
filter_(lambda n: n.get("active")) >>
normalize(sort_children=True) >>
extract(lambda n: n.name)
)
# Apply pipeline to tree
result = pipeline(tree)
This is the same idea as Unix pipes. Each stage takes a tree and returns a tree (or extracted values). The >> operator chains them left to right.
Export Formats
# JSON export
json_str = tree.to_json(indent=2)
# GraphViz for visualization
dot_str = tree.to_graphviz()
# Mermaid diagrams
mermaid_str = tree.to_mermaid()
# Path listings
paths = tree.to_paths()
Relationship to AlgoGraph
AlgoTree and AlgoGraph share the same design philosophy: immutable data structures, pipe-based transformers, declarative selectors, lazy views. They also interoperate:
from AlgoTree import Tree
from AlgoGraph import tree_to_graph, graph_to_tree
# Tree to Graph
graph = tree_to_graph(tree)
# Graph to Tree (extracts spanning tree)
tree = graph_to_tree(graph, root='root')
Installation
pip install AlgoTree
Resources
- PyPI: pypi.org/project/AlgoTree/
- GitHub: github.com/queelius/AlgoTree
- Documentation: queelius.github.io/AlgoTree/
Discussion