traversal: Tree Operations

All operations respect the children/rebuild contract: rebuild node (children node) == node.

Core Operations

children

Get immediate child nodes in deterministic order.

traversal.children :: Expr -> [Expr]

Example:

# For: { tag = "App"; func = f; arg = x; }
traversal.children node  # => [f, x]

rebuild

Reconstruct node from new children (inverse of children).

traversal.rebuild :: Expr -> [Expr] -> Expr

Example:

newNode = traversal.rebuild node [newFunc newArg]

descend

Apply function to all immediate children, then rebuild.

traversal.descend :: (Expr -> Expr) -> Expr -> Expr

Example:

# Transform all direct children
traversal.descend (n: n + 1) node

Transformations

transform

Bottom-up transformation: f (descend (transform f) node).

traversal.transform :: (Expr -> Expr) -> Expr -> Expr

Example:

# Replace all integers with their double
doubleInts = traversal.transform (node:
  if syntax.isConstant node && syntax.isInt node.contents then
    syntax.mkConstant (syntax.mkInt (node.contents.contents * 2))
  else
    node
);

rewrite

Apply rule bottom-up; null means no change.

traversal.rewrite :: (Expr -> Expr | null) -> Expr -> Expr

Example:

# Simplify constant folding
simplify = traversal.rewrite (node:
  if isBinaryAdd node && bothConstants node then
    syntax.mkInt (evalNode node)
  else
    null  # no change
);

para

Paramorphism: access node and recursive results from children.

traversal.para :: (Expr -> [a] -> a) -> Expr -> a

Example:

# Count all nodes
countNodes = traversal.para (node: childCounts:
  1 + builtins.foldl' (a: b: a + b) 0 childCounts
);

Exploration

universe

All descendant nodes including self.

traversal.universe :: Expr -> [Expr]

Example:

allSymbols = builtins.filter syntax.isSym (traversal.universe ast);

holes

Each child paired with a replacement function.

traversal.holes :: Expr -> [(Expr, Expr -> Expr)]

Example:

# Get all positions where a child can be replaced
holes = traversal.holes ast;
# => [(child1, \replacement -> rebuild node [replacement ...]),
#     (child2, \replacement -> rebuild node [... replacement ...])]

contexts

Every subnode paired with a function to replace it in context.

traversal.contexts :: Expr -> [(Expr, Expr -> Expr)]

Example:

# Get all subexpressions with their context
contexts = traversal.contexts ast;

Children/Rebuild Contract

All traversal operations maintain this invariant:

traversal.rebuild node (traversal.children node) == node

This ensures that operations can freely decompose and reconstruct nodes without losing information.

Use Cases

Deep Transformation

# Replace all variable references
replaceVars = traversal.transform (node:
  if syntax.isSym node then
    syntax.mkSym (replaceName node.contents)
  else
    node
);

Collection

# Collect all function applications
collectApps = traversal.universe >> builtins.filter syntax.isApp;

Analysis

# Check if expression contains a specific pattern
containsAssert = node:
  builtins.any syntax.isAssert (traversal.universe node);