Paul Edwin (@paul-edwin.hachyderm.io.ap.brid.gy)

Functional Optics for Modern Java - Part 4 <h1 id="the-focus-dsl-traversals-and-pattern-rewrites">The Focus DSL: Traversals and Pattern Rewrites</h1> Part 4 of the Functional Optics for Modern Java series In <a href="/2026/01/09/java-the-immutability-gap.html">Part 1</a> and <a href="/2026/01/16/optics-fundamentals.html">Part 2</a>, we established why optics matter and how they work. In <a href="/2026/01/23/ast-basic-optics.html">Part 3</a>, we built our expression language AST and applied basic optics using lenses for field access and prisms for variant matching. Finally, we created a simple optimiser, but left things hanging with a fundamental limitation that we shall address now: How do we visit all nodes in a tree, not just the top level? This is where traversals come into play as the essential tool. A traversal focuses on zero or more elements within a structure, making it perfect for recursive tree operations. The <a href="https://higher-kinded-j.github.io/latest/optics/ch4_intro.html">Focus DSL</a> provides <code class="language-plaintext highlighter-rouge">TraversalPath</code>: a fluent wrapper around traversals that makes collection navigation more readable and composable. By the end of this article, we’ll be writing code like: <div class="language-java highlighter-rouge"><div class="highlight"><pre class="highlight"><code>// Navigate all employees in all departments, modify their salaries Company updated = CompanyFocus.departments() .each() // Traverse each department .employees() // Navigate to employees list .each() // Traverse each employee .salary() // Focus on salary field .modifyAll(s -> s.multiply(1.1), company); </code></pre></div></div> No manual recursion. No reconstruction boilerplate. Just a fluent path that describes what you want. <h3 id="running-the-examples">Running the Examples</h3> <hr /> <h2 id="article-code">Article Code</h2> All code examples from this article have <a href="https://github.com/higher-kinded-j/expression-language-example">runnable demos:</a> <ul> <li><a href="https://github.com/higher-kinded-j/expression-language-example/blob/main/src/main/java/org/higherkindedj/article4/demo/TraversalDemo.java">TraversalDemo</a>: Using Higher-Kinded-J’s Traversal interface for composable, type-safe tree manipulation.</li> <li><a href="https://github.com/higher-kinded-j/expression-language-example/blob/main/src/main/java/org/higherkindedj/article4/demo/OptimiserDemo.java">OptimiserDemo</a>: Constant folding, identity simplification, and cascading optimisation using traversal-based passes.</li> </ul> The AST types are defined in <a href="https://github.com/higher-kinded-j/expression-language-example/blob/main/src/main/java/org/higherkindedj/article4/ast/"><code class="language-plaintext highlighter-rouge">org.higherkindedj.article4.ast</code></a>, with transformations in <a href="https://github.com/higher-kinded-j/expression-language-example/blob/main/src/main/java/org/higherkindedj/article4/transform/"><code class="language-plaintext highlighter-rouge">org.higherkindedj.article4.transform</code></a> and traversals in <a href="https://github.com/higher-kinded-j/expression-language-example/blob/main/src/main/java/org/higherkindedj/article4/traversal/"><code class="language-plaintext highlighter-rouge">org.higherkindedj.article4.traversal</code></a>. <hr /> <h2 id="traversals-as-garden-pruning">Traversals as Garden Pruning</h2> Before diving into code, consider an analogy. Imagine you’re pruning a tree in a garden. You need to visit every branch, decide what to do at each one, and rebuild the tree with your changes. You have two strategies: <ul> <li> Bottom-up (leaves first): Start at the leaf tips, prune outward branches, then work your way down. Each branch is trimmed after its subbranches are done. This is perfect when you need to see the final state of subbranches before deciding on the parent. </li> <li> Top-down (trunk first): Start at the trunk, make decisions about major branches first, then work outward. Each branch is examined before its subbranches. This works when you want to make early decisions that affect the whole subtree. </li> </ul> In programming, a traversal is exactly this: a systematic way to visit every node in a tree structure, with a strategy for when to act on each node relative to its children. The Focus DSL makes this as natural as describing which branches to visit. <hr /> <h2 id="the-recursive-challenge">The Recursive Challenge</h2> Consider our expression AST. When we write <code class="language-plaintext highlighter-rouge">(x + 1) * (y + 2)</code>, we get: <div class="language-java highlighter-rouge"><div class="highlight"><pre class="highlight"><code>new Binary( new Binary(new Variable("x"), ADD, new Literal(1)), MUL, new Binary(new Variable("y"), ADD, new Literal(2)) ) </code></pre></div></div> Visualised as a tree: <img src="/magnussmith/assets/optics/mfj-traversal-rewrite-1.png" alt="mfj-traversal-rewrite-1.png" title="Binary Tree" /> This tree has seven nodes: three <code class="language-plaintext highlighter-rouge">Binary</code> expressions, two <code class="language-plaintext highlighter-rouge">Variable</code> nodes, and two <code class="language-plaintext highlighter-rouge">Literal</code> nodes. If we want to find all variables, we can’t just look at the top level; we need to descend into every branch. As we discussed in Part 3, the traditional Visitor pattern requires substantial boilerplate: an interface, accept methods in each node, and a visitor implementation for every operation. Even with Java 25’s pattern matching, we still face the reconstruction cascade for transformations. Traversals offer something better: define the traversal structure once, then use it for any operation. <hr /> <h2 id="building-a-universal-expression-traversal">Building a Universal Expression Traversal</h2> A <code class="language-plaintext highlighter-rouge">Traversal<S, A></code> focuses on zero or more <code class="language-plaintext highlighter-rouge">A</code> values within an <code class="language-plaintext highlighter-rouge">S</code> structure. For expressions, we want <code class="language-plaintext highlighter-rouge">Traversal<Expr, Expr></code>: a traversal that visits all subexpressions within an expression. First, let’s define what “all subexpressions” means for each variant: <table> <thead> <tr> <th>Expression Type</th> <th>Sub-expressions</th> </tr> </thead> <tbody> <tr> <td><code class="language-plaintext highlighter-rouge">Literal</code></td> <td>None</td> </tr> <tr> <td><code class="language-plaintext highlighter-rouge">Variable</code></td> <td>None</td> </tr> <tr> <td><code class="language-plaintext highlighter-rouge">Binary</code></td> <td><code class="language-plaintext highlighter-rouge">left</code>, <code class="language-plaintext highlighter-rouge">right</code></td> </tr> <tr> <td><code class="language-plaintext highlighter-rouge">Conditional</code></td> <td><code class="language-plaintext highlighter-rouge">cond</code>, <code class="language-plaintext highlighter-rouge">then_</code>, <code class="language-plaintext highlighter-rouge">else_</code></td> </tr> </tbody> </table> Here’s the traversal implementation: <div class="language-java highlighter-rouge"><div class="highlight"><pre class="highlight"><code>public final class ExprTraversal { /** * A traversal targeting all immediate children of an expression. * Does not descend recursively; use with transform utilities for full tree traversal. */ public static Traversal<Expr, Expr> children() { return new Traversal<>() { @Override public <F> Kind<F, Expr> modifyF( Function<Expr, Kind<F, Expr>> f, Expr source, Applicative<F> applicative) { return switch (source) { case Literal _ -> applicative.of(source); case Variable _ -> applicative.of(source); case Binary(var l, var op, var r) -> applicative.map2(f.apply(l), f.apply(r), (newL, newR) -> new Binary(newL, op, newR)); case Conditional(var c, var t, var e) -> applicative.map3(f.apply(c), f.apply(t), f.apply(e), (newC, newT, newE) -> new Conditional(newC, newT, newE)); }; } }; } } </code></pre></div></div> This is effect-polymorphic: the same traversal works with any <code class="language-plaintext highlighter-rouge">Applicative</code> functor. We can use it for pure transformations, error-accumulating validation, or stateful operations. (Don’t worry if “effect-polymorphic” is unfamiliar; we’ll explore this concept further. For now, just know it means this same traversal code works whether you’re doing pure transformations, error handling, or validation.) For simpler use cases, Higher-Kinded-J provides the <code class="language-plaintext highlighter-rouge">Traversals.modify</code> utility: <div class="language-java highlighter-rouge"><div class="highlight"><pre class="highlight"><code>import org.higherkindedj.optics.util.Traversals; // Apply a pure transformation to all children Expr result = Traversals.modify(children(), f, expr); </code></pre></div></div> This handles the <code class="language-plaintext highlighter-rouge">Id</code> effect internally, giving you a clean API for pure transformations. <h3 id="the-focus-dsl-alternative-traversalpath">The Focus DSL Alternative: TraversalPath</h3> While the raw <code class="language-plaintext highlighter-rouge">Traversal</code> interface provides maximum control, the Focus DSL offers a more ergonomic API for everyday use. <code class="language-plaintext highlighter-rouge">TraversalPath</code> wraps a traversal and provides fluent methods: <div class="language-java highlighter-rouge"><div class="highlight"><pre class="highlight"><code>import org.higherkindedj.optics.focus.TraversalPath; import org.higherkindedj.optics.focus.FocusPaths; // Create a TraversalPath from our children traversal TraversalPath<Expr, Expr> childrenPath = TraversalPath.fromTraversal(children()); // Now we have fluent operations: List<Expr> allChildren = childrenPath.getAll(expr); // Collect all children Expr modified = childrenPath.modifyAll(this::optimise, expr); // Transform all children </code></pre></div></div> The Focus DSL becomes even more powerful with collection navigation. For lists, use <code class="language-plaintext highlighter-rouge">each()</code>: <div class="language-java highlighter-rouge"><div class="highlight"><pre class="highlight"><code>// Given a department with a list of employees FocusPath<Department, List<Employee>> staffPath = DepartmentFocus.staff(); // Navigate into the list with each() TraversalPath<Department, Employee> allStaff = staffPath.each(); // Now we can operate on all employees: List<Employee> employees = allStaff.getAll(department); Department updated = allStaff.modifyAll(Employee::promote, department); </code></pre></div></div> The <code class="language-plaintext highlighter-rouge">each()</code> method is the key: it transforms a <code class="language-plaintext highlighter-rouge">FocusPath<S, List<A>></code> into a <code class="language-plaintext highlighter-rouge">TraversalPath<S, A></code>. This pattern scales to nested structures, as we’ll see throughout this article. <h3 id="deep-traversal-visiting-all-descendants">Deep Traversal: Visiting All Descendants</h3> The <code class="language-plaintext highlighter-rouge">children()</code> traversal only visits immediate children. For full tree traversal, we combine it with recursive descent: <div class="language-java highlighter-rouge"><div class="highlight"><pre class="highlight"><code>/** * Transform all nodes in the tree from leaves to root (bottom-up). * Each node is transformed after its children. */ public static Expr transformBottomUp(Expr expr, Function<Expr, Expr> f) { // First transform all children recursively Expr transformed = Traversals.modify( children(), child -> transformBottomUp(child, f), expr ); // Then transform this node return f.apply(transformed); } /** * Transform all nodes in the tree from root to leaves (top-down). * Each node is transformed before its children. */ public static Expr transformTopDown(Expr expr, Function<Expr, Expr> f) { // First transform this node Expr transformed = f.apply(expr); // Then transform all children recursively return Traversals.modify( children(), child -> transformTopDown(child, f), transformed ); } </code></pre></div></div> The choice between bottom-up and top-down matters: <ul> <li> Bottom-up: Children are transformed first. Use this when transformations depend on the structure of children (like constant folding, where we need to fold <code class="language-plaintext highlighter-rouge">1 + 2</code> before we can simplify <code class="language-plaintext highlighter-rouge">(1 + 2) * 3</code>). </li> <li> Top-down: The node is transformed first. Use this when you want to pattern-match on the original structure before children change (like macro expansion). </li> </ul> Here’s the traversal order visualised: <img src="/magnussmith/assets/optics/mfj-traversal-rewrite-2.png" alt="mfj-traversal-rewrite-2.png" title="Bottom-up Top-down Trees" /> For constant folding, bottom-up is essential: we need to evaluate <code class="language-plaintext highlighter-rouge">1 + 2</code> at the leaves before we can recognise that the parent is now <code class="language-plaintext highlighter-rouge">3 * 5</code>. <h3 id="focus-dsl-the-practical-choice">Focus DSL: The Practical Choice</h3> For most use cases, the Focus DSL provides what you need without writing custom traversals. Here’s the pattern for nested structures: <div class="language-java highlighter-rouge"><div class="highlight"><pre class="highlight"><code>@GenerateFocus(generateNavigators = true) record Company(String name, List<Department> departments) {} @GenerateFocus(generateNavigators = true) record Department(String name, List<Employee> employees, Employee manager) {} @GenerateFocus(generateNavigators = true) record Employee(String name, BigDecimal salary, Address address) {} // Navigate all the way to employee addresses: TraversalPath<Company, Address> allEmployeeAddresses = CompanyFocus .departments().each() // Into each department .employees().each() // Into each employee .address(); // To their address // Get all addresses List<Address> addresses = allEmployeeAddresses.getAll(company); // Relocate all employees Company relocated = allEmployeeAddresses.modifyAll( addr -> new Address("New HQ", addr.city(), addr.postcode()), company ); </code></pre></div></div> With navigators enabled, cross-type navigation happens automatically. No explicit <code class="language-plaintext highlighter-rouge">via()</code> calls, no manual composition. The path reads like English: “company’s departments, each one’s employees, each one’s address.” <hr /> <h2 id="collecting-information">Collecting Information</h2> Traversals aren’t just for modification; they’re equally powerful for extraction. We use folds to aggregate information from all focused elements. <h3 id="finding-all-variables">Finding All Variables</h3> <div class="language-java highlighter-rouge"><div class="highlight"><pre class="highlight"><code>public static Set<String> findVariables(Expr expr) { Set<String> vars = new HashSet<>(); collectVariables(expr, vars); return vars; } private static void collectVariables(Expr expr, Set<String> accumulator) { switch (expr) { case Variable(var name) -> accumulator.add(name); case Literal _ -> { } case Binary(var l, _, var r) -> { collectVariables(l, accumulator); collectVariables(r, accumulator); } case Conditional(var c, var t, var e) -> { collectVariables(c, accumulator); collectVariables(t, accumulator); collectVariables(e, accumulator); } } } </code></pre></div></div> With the Focus DSL, we can make this more readable: <div class="language-java highlighter-rouge"><div class="highlight"><pre class="highlight"><code>public static Set<String> findVariables(Expr expr) { // Create a TraversalPath that focuses on all Variable nodes TraversalPath<Expr, Expr> allNodes = ExprFocus.universe(); // All descendants // Filter to variables and extract names return allNodes.getAll(expr).stream() .filter(e -> e instanceof Variable) .map(e -> ((Variable) e).name()) .collect(Collectors.toSet()); } </code></pre></div></div> Or using <code class="language-plaintext highlighter-rouge">foldMap</code> on the TraversalPath for a more functional approach: <div class="language-java highlighter-rouge"><div class="highlight"><pre class="highlight"><code>public static Set<String> findVariables(Expr expr) { TraversalPath<Expr, Expr> allNodes = ExprFocus.universe(); return allNodes.foldMap( Monoids.set(), e -> e instanceof Variable(var name) ? Set.of(name) : Set.of(), expr ); } </code></pre></div></div> The <code class="language-plaintext highlighter-rouge">foldMap</code> method on <code class="language-plaintext highlighter-rouge">TraversalPath</code> traverses all focused elements and combines results using a monoid (here, set union). <h3 id="counting-nodes-by-type">Counting Nodes by Type</h3> <div class="language-java highlighter-rouge"><div class="highlight"><pre class="highlight"><code>public record NodeCounts(int literals, int variables, int binaries, int conditionals) { public static NodeCounts ZERO = new NodeCounts(0, 0, 0, 0); public NodeCounts add(NodeCounts other) { return new NodeCounts( literals + other.literals, variables + other.variables, binaries + other.binaries, conditionals + other.conditionals ); } } public static NodeCounts countNodes(Expr expr) { return foldMap( expr, e -> switch (e) { case Literal _ -> new NodeCounts(1, 0, 0, 0); case Variable _ -> new NodeCounts(0, 1, 0, 0); case Binary _ -> new NodeCounts(0, 0, 1, 0); case Conditional _ -> new NodeCounts(0, 0, 0, 1); }, NodeCounts::add ); } </code></pre></div></div> <h3 id="the-foldmap-implementation">The foldMap Implementation</h3> <div class="language-java highlighter-rouge"><div class="highlight"><pre class="highlight"><code>public static <A> A foldMap(Expr expr, Function<Expr, A> extract, BinaryOperator<A> combine) { A current = extract.apply(expr); return switch (expr) { case Literal _, Variable _ -> current; case Binary(var l, _, var r) -> combine.apply(current, combine.apply(foldMap(l, extract, combine), foldMap(r, extract, combine))); case Conditional(var c, var t, var e) -> combine.apply(current, combine.apply(foldMap(c, extract, combine), combine.apply(foldMap(t, extract, combine), foldMap(e, extract, combine)))); }; } </code></pre></div></div> <hr /> <h2 id="filtered-traversals-and-conditional-updates">Filtered Traversals and Conditional Updates</h2> Sometimes we only want to focus on certain elements. The Focus DSL provides <code class="language-plaintext highlighter-rouge">modifyWhen()</code> for conditional updates and filtering capabilities for targeted navigation. <h3 id="conditional-modification-with-modifywhen">Conditional Modification with modifyWhen</h3> The <code class="language-plaintext highlighter-rouge">modifyWhen</code> method is perfect for targeted updates: <div class="language-java highlighter-rouge"><div class="highlight"><pre class="highlight"><code>// Give a raise only to employees earning below a threshold TraversalPath<Company, Employee> allEmployees = CompanyFocus .departments().each() .employees().each(); Company updated = allEmployees.modifyWhen( emp -> emp.salary().compareTo(threshold) < 0, // Predicate emp -> emp.withSalary(emp.salary().multiply(1.15)), // Transformation company ); </code></pre></div></div> This is cleaner than filtering after the fact: the predicate and transformation are co-located, making the intent clear. <h3 id="targeting-only-binary-additions">Targeting Only Binary Additions</h3> For our expression language, we might want to target specific node types: <div class="language-java highlighter-rouge"><div class="highlight"><pre class="highlight"><code>public static Expr doubleAllAdditions(Expr expr) { return transformBottomUp(expr, e -> { if (e instanceof Binary(var l, BinaryOp.ADD, var r)) { // Transform a + b into (a + b) + (a + b) return new Binary(e, BinaryOp.ADD, e); } return e; }); } </code></pre></div></div> <h3 id="using-prisms-for-type-safe-filtering">Using Prisms for Type-Safe Filtering</h3> The Focus DSL integrates beautifully with prisms for sum type navigation: <div class="language-java highlighter-rouge"><div class="highlight"><pre class="highlight"><code>public static List<BinaryOp> findAllOperators(Expr expr) { // Navigate to all Binary nodes using instanceOf TraversalPath<Expr, Binary> allBinaries = ExprFocus.universe() .via(AffinePath.instanceOf(Binary.class)); return allBinaries.getAll(expr).stream() .map(Binary::op) .collect(Collectors.toList()); } </code></pre></div></div> The <code class="language-plaintext highlighter-rouge">AffinePath.instanceOf()</code> creates an affine path that focuses on elements of a specific type. When composed with a traversal, it filters to only matching elements. <h3 id="sum-type-navigation-with-instanceof">Sum Type Navigation with instanceOf</h3> For sealed interfaces, <code class="language-plaintext highlighter-rouge">instanceOf</code> is particularly powerful: <div class="language-java highlighter-rouge"><div class="highlight"><pre class="highlight"><code>// Focus on all Circle shapes in a drawing TraversalPath<Drawing, Circle> circles = DrawingFocus.shapes() .each() .via(AffinePath.instanceOf(Circle.class)); // Double all circle radii Drawing updated = circles.modifyAll( c -> new Circle(c.radius() * 2), drawing ); </code></pre></div></div> This pattern combines the type safety of sealed interfaces with the composability of the Focus DSL. The compiler ensures exhaustiveness while the DSL provides elegant navigation. <hr /> <h2 id="implementing-optimisation-passes">Implementing Optimisation Passes</h2> With traversals in place, we can build sophisticated optimisation passes. Each pass is a transformation function; the optimiser composes them. <h3 id="pass-1-constant-folding">Pass 1: Constant Folding</h3> Evaluate operations where both operands are literals: <div class="language-java highlighter-rouge"><div class="highlight"><pre class="highlight"><code>public static Expr foldConstants(Expr expr) { return transformBottomUp(expr, ExprOptimiser::foldConstant); } private static Expr foldConstant(Expr expr) { if (expr instanceof Binary(Literal(var l), var op, Literal(var r))) { return evaluateBinary(l, op, r) .map(result -> (Expr) new Literal(result)) .orElse(expr); } return expr; } private static Optional<Object> evaluateBinary(Object left, BinaryOp op, Object right) { return switch (op) { case ADD -> evaluateAdd(left, right); case SUB -> evaluateSub(left, right); case MUL -> evaluateMul(left, right); case DIV -> evaluateDiv(left, right); case AND -> evaluateAnd(left, right); case OR -> evaluateOr(left, right); case EQ -> Optional.of(left.equals(right)); case NE -> Optional.of(!left.equals(right)); case LT, LE, GT, GE -> evaluateComparison(left, op, right); }; } </code></pre></div></div> <h3 id="pass-2-identity-simplification">Pass 2: Identity Simplification</h3> Remove operations that don’t change the result: <div class="language-java highlighter-rouge"><div class="highlight"><pre class="highlight"><code>public static Expr simplifyIdentities(Expr expr) { return transformBottomUp(expr, ExprOptimiser::simplifyIdentity); } private static Expr simplifyIdentity(Expr expr) { return switch (expr) { // x + 0 → x, 0 + x → x case Binary(var x, ADD, Literal(Integer i)) when i == 0 -> x; case Binary(Literal(Integer i), ADD, var x) when i == 0 -> x; // x * 1 → x, 1 * x → x case Binary(var x, MUL, Literal(Integer i)) when i == 1 -> x; case Binary(Literal(Integer i), MUL, var x) when i == 1 -> x; // x * 0 → 0, 0 * x → 0 case Binary(_, MUL, Literal(Integer i)) when i == 0 -> new Literal(0); case Binary(Literal(Integer i), MUL, _) when i == 0 -> new Literal(0); // x && true → x, true && x → x case Binary(var x, AND, Literal(Boolean b)) when b -> x; case Binary(Literal(Boolean b), AND, var x) when b -> x; // x || false → x, false || x → x case Binary(var x, OR, Literal(Boolean b)) when !b -> x; case Binary(Literal(Boolean b), OR, var x) when !b -> x; // x && false → false case Binary(_, AND, Literal(Boolean b)) when !b -> new Literal(false); case Binary(Literal(Boolean b), AND, _) when !b -> new Literal(false); // x || true → true case Binary(_, OR, Literal(Boolean b)) when b -> new Literal(true); case Binary(Literal(Boolean b), OR, _) when b -> new Literal(true); default -> expr; }; } </code></pre></div></div> <h3 id="pass-3-dead-branch-elimination">Pass 3: Dead Branch Elimination</h3> Remove conditional branches with constant conditions: <div class="language-java highlighter-rouge"><div class="highlight"><pre class="highlight"><code>public static Expr eliminateDeadBranches(Expr expr) { return transformBottomUp(expr, ExprOptimiser::eliminateDeadBranch); } private static Expr eliminateDeadBranch(Expr expr) { return switch (expr) { case Conditional(Literal(Boolean b), var t, var e) -> b ? t : e; default -> expr; }; } </code></pre></div></div> <h3 id="pass-4-common-subexpression-detection">Pass 4: Common Subexpression Detection</h3> Identify repeated subexpressions (useful for let-binding which we will see to in Part 5): <div class="language-java highlighter-rouge"><div class="highlight"><pre class="highlight"><code>public static Map<Expr, Integer> findCommonSubexpressions(Expr expr) { Map<Expr, Integer> counts = new HashMap<>(); countSubexpressions(expr, counts); // Return only expressions that appear more than once return counts.entrySet().stream() .filter(e -> e.getValue() > 1) .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue)); } private static void countSubexpressions(Expr expr, Map<Expr, Integer> counts) { counts.merge(expr, 1, Integer::sum); switch (expr) { case Binary(var l, _, var r) -> { countSubexpressions(l, counts); countSubexpressions(r, counts); } case Conditional(var c, var t, var e) -> { countSubexpressions(c, counts); countSubexpressions(t, counts); countSubexpressions(e, counts); } default -> { } } } </code></pre></div></div> <hr /> <h2 id="extending-the-ast-source-locations">Extending the AST: Source Locations</h2> Real compilers need to track where expressions come from for error messages. Let’s extend our AST with source location metadata. <div class="language-java highlighter-rouge"><div class="highlight"><pre class="highlight"><code>public record SourceLocation(String file, int line, int column) { @Override public String toString() { return file + ":" + line + ":" + column; } } public record Located<T>(T value, SourceLocation location) { public <U> Located<U> map(Function<T, U> f) { return new Located<>(f.apply(value), location); } } </code></pre></div></div> Now we can create <code class="language-plaintext highlighter-rouge">Located<Expr></code> to track positions. Here lies a question in that when we transform an expression, what happens to the location? <h3 id="preserving-locations-through-transformations">Preserving Locations Through Transformations</h3> <div class="language-java highlighter-rouge"><div class="highlight"><pre class="highlight"><code>public static Located<Expr> transformPreservingLocation( Located<Expr> located, Function<Expr, Expr> f) { return located.map(f); } </code></pre></div></div> For more sophisticated location handling (like updating locations when inlining code), indexed optics become valuable. We’ll explore those in Part 5. <hr /> <h2 id="the-complete-optimiser">The Complete Optimiser</h2> Combining all passes into a single optimiser: <div class="language-java highlighter-rouge"><div class="highlight"><pre class="highlight"><code>public final class ExprOptimiser { /** * Run all optimisation passes until the expression stops changing. */ public static Expr optimise(Expr expr) { Expr current = expr; Expr previous; do { previous = current; current = runAllPasses(current); } while (!current.equals(previous)); return current; } private static Expr runAllPasses(Expr expr) { Expr result = expr; result = foldConstants(result); result = simplifyIdentities(result); result = eliminateDeadBranches(result); return result; } } </code></pre></div></div> The fixed-point iteration ensures we catch cascading simplifications: <img src="/magnussmith/assets/optics/mfj-traversal-rewrite-3.png" alt="mfj-traversal-rewrite-3.png" title="Optimisation Pipeline" /> For example: <img src="/magnussmith/assets/optics/mfj-traversal-rewrite-4.png" alt="mfj-traversal-rewrite-4.png" title="Optimisation example" /> <h3 id="example-complex-optimisation">Example: Complex Optimisation</h3> <div class="language-java highlighter-rouge"><div class="highlight"><pre class="highlight"><code>// if (true && (1 < 2)) then (x + 0) * 1 else y Expr complex = new Conditional( new Binary(new Literal(true), AND, new Binary(new Literal(1), LT, new Literal(2))), new Binary( new Binary(new Variable("x"), ADD, new Literal(0)), MUL, new Literal(1)), new Variable("y") ); Expr optimised = ExprOptimiser.optimise(complex); // Result: Variable("x") </code></pre></div></div> The optimiser: <ol> <li>Folds <code class="language-plaintext highlighter-rouge">1 < 2</code> → <code class="language-plaintext highlighter-rouge">true</code></li> <li>Simplifies <code class="language-plaintext highlighter-rouge">true && true</code> → <code class="language-plaintext highlighter-rouge">true</code></li> <li>Eliminates the dead else-branch</li> <li>Simplifies <code class="language-plaintext highlighter-rouge">x + 0</code> → <code class="language-plaintext highlighter-rouge">x</code></li> <li>Simplifies <code class="language-plaintext highlighter-rouge">x * 1</code> → <code class="language-plaintext highlighter-rouge">x</code></li> </ol> All through composable, declarative transformations. <hr /> <h2 id="bridging-to-the-effect-path-apihttpshigher-kinded-jgithubiolatesteffectchintrohtml">Bridging to the <a href="https://higher-kinded-j.github.io/latest/effect/ch_intro.html">Effect Path API</a></h2> <h3 id="what-is-effect-polymorphism">What is effect-polymorphism?</h3> In functional programming, an effect is any computational context beyond returning a plain value; things like “might fail,” “might be absent,” “accumulates errors,” or “carries state.” Effect-polymorphism means writing code once that works with any of these contexts. Instead of writing separate versions of a traversal for “transform purely,” “transform with possible failure,” and “transform while accumulating errors,” we write a single generic version that is parameterised by the effect type. The traversal doesn’t care which effect you use; it just requires that the effect supports certain operations (specifically, the <code class="language-plaintext highlighter-rouge">Applicative</code> interface). This is what <code class="language-plaintext highlighter-rouge">modifyF</code> provides: the <code class="language-plaintext highlighter-rouge">F</code> is a placeholder for any effect, so the same traversal logic handles pure transformations, validation, state threading, or any other effect you plug in. The TraversalPath we’ve built throughout this article navigates and transforms data structures. But what happens when transformations might fail, or when we need to accumulate errors from multiple elements? Higher-Kinded-J’s Effect Path API provides the answer. Effect Paths wrap computations in contexts like <code class="language-plaintext highlighter-rouge">Maybe</code> (optional), <code class="language-plaintext highlighter-rouge">Either</code> (fail-fast errors), or <code class="language-plaintext highlighter-rouge">Validated</code> (accumulated errors). The Focus DSL bridges directly to these effect types. <h3 id="from-focus-paths-to-effect-paths">From Focus Paths to Effect Paths</h3> Every Focus path type provides bridge methods to enter the effect world: <div class="language-java highlighter-rouge"><div class="highlight"><pre class="highlight"><code>// FocusPath<S, A> bridges to effects FocusPath<Employee, String> namePath = EmployeeFocus.name(); MaybePath<String> maybeName = namePath.toMaybePath(employee); EitherPath<Error, String> eitherName = namePath.toEitherPath(employee); </code></pre></div></div> For AffinePath (which might not find a value), the bridge handles the missing case: <div class="language-java highlighter-rouge"><div class="highlight"><pre class="highlight"><code>// AffinePath<S, A> handles optionality AffinePath<User, String> nicknamePath = UserFocus.nickname(); // Optional field MaybePath<String> maybeNickname = nicknamePath.toMaybePath(user); // Returns Maybe.just(name) or Maybe.nothing() EitherPath<String, String> eitherNickname = nicknamePath.toEitherPath(user, "No nickname set"); // Returns Either.right(name) or Either.left("No nickname set") </code></pre></div></div> <h3 id="whats-ahead-the-effect-path-api">What’s Ahead: The Effect Path API</h3> Beyond optics and the Focus DSL, Higher-Kinded-J provides the Effect Path API: a fluent interface for computations that might fail, accumulate errors, or require deferred execution. The Effect Path types follow the “railway” metaphor where values travel along success or failure tracks: <img src="/magnussmith/assets/optics/mfj-traversal-rewrite-5.png" alt="mfj-traversal-rewrite-5.png" title="Railway" /> The core Effect Path types include: <table> <thead> <tr> <th>Effect Path</th> <th>Wraps</th> <th>Use Case</th> </tr> </thead> <tbody> <tr> <td><code class="language-plaintext highlighter-rouge">MaybePath<A></code></td> <td><code class="language-plaintext highlighter-rouge">Maybe</code></td> <td>Optional values (might be absent)</td> </tr> <tr> <td><code class="language-plaintext highlighter-rouge">EitherPath<E, A></code></td> <td><code class="language-plaintext highlighter-rouge">Either</code></td> <td>Fail-fast error handling</td> </tr> <tr> <td><code class="language-plaintext highlighter-rouge">ValidationPath<E, A></code></td> <td><code class="language-plaintext highlighter-rouge">Validated</code></td> <td>Error accumulation</td> </tr> <tr> <td><code class="language-plaintext highlighter-rouge">TryPath<A></code></td> <td><code class="language-plaintext highlighter-rouge">Try</code></td> <td>Exception handling</td> </tr> <tr> <td><code class="language-plaintext highlighter-rouge">IOPath<A></code></td> <td><code class="language-plaintext highlighter-rouge">IO</code></td> <td>Deferred side effects</td> </tr> </tbody> </table> Understanding the underlying effect types: <ul> <li> <a href="https://github.com/higher-kinded-j/higher-kinded-j/blob/main/hkj-core/src/main/java/org/higherkindedj/hkt/maybe/Maybe.java">Maybe</a>: Represents a value that might be absent, similar to <code class="language-plaintext highlighter-rouge">Optional</code> but with richer composition. Use when a value simply might not exist. </li> <li> <a href="https://github.com/higher-kinded-j/higher-kinded-j/blob/main/hkj-core/src/main/java/org/higherkindedj/hkt/either/Either.java">Either</a>: Represents a value that is either a <code class="language-plaintext highlighter-rouge">Left</code> (typically an error) or a <code class="language-plaintext highlighter-rouge">Right</code> (the success value). Fails fast on the first error encountered. </li> <li> <a href="https://github.com/higher-kinded-j/higher-kinded-j/blob/main/hkj-core/src/main/java/org/higherkindedj/hkt/validated/Validated.java">Validated</a>: Like <code class="language-plaintext highlighter-rouge">Either</code>, but designed for error accumulation. When combining multiple validations, collects all errors rather than stopping at the first. </li> <li> <a href="https://github.com/higher-kinded-j/higher-kinded-j/blob/main/hkj-core/src/main/java/org/higherkindedj/hkt/trymonad/Try.java">Try</a>: Captures computations that might throw exceptions. Converts exception-throwing code into values you can compose safely. </li> <li> <a href="https://github.com/higher-kinded-j/higher-kinded-j/blob/main/hkj-core/src/main/java/org/higherkindedj/hkt/io/IO.java">IO</a>: Represents a deferred side effect. The computation is described but not executed until explicitly run, enabling pure functional composition of effectful operations. </li> </ul> These types integrate seamlessly with Focus paths via bridge methods: <div class="language-java highlighter-rouge"><div class="highlight"><pre class="highlight"><code>// Navigate to a field, then enter the Effect Path world FocusPath<User, String> emailPath = UserFocus.email(); </code></pre></div></div> <h3 id="effect-paths-with-traversals">Effect Paths with Traversals</h3> TraversalPath works with Effect Paths through <code class="language-plaintext highlighter-rouge">modifyF</code>. This is the bridge to effect-polymorphic operations: <div class="language-java highlighter-rouge"><div class="highlight"><pre class="highlight"><code>// Validate all employees in a company TraversalPath<Company, Employee> allEmployees = CompanyFocus .departments().each() .employees().each(); // Bridge to ValidationPath for error accumulation ValidationPath<List<Error>, Company> validated = Path.valid(company, Semigroups.list()) .via(c -> { // Use modifyF with Validated applicative for error accumulation Kind<ValidatedKind.Witness<List<Error>>, Company> result = allEmployees.modifyF( emp -> validateEmployee(emp), c, validatedApplicative ); return VALIDATED.narrow(result); }); </code></pre></div></div> <h3 id="the-railway-model">The Railway Model</h3> Effect Paths follow the “railway” pattern where values travel along success or failure tracks: <img src="/magnussmith/assets/optics/mfj-traversal-rewrite-5.png" alt="mfj-traversal-rewrite-5.png" title="Railway pattern" /> This pattern enables comprehensive validation rather than fail-fast behaviour. The <code class="language-plaintext highlighter-rouge">ValidationPath</code> accumulates all errors using a <code class="language-plaintext highlighter-rouge">Semigroup</code>, so users see every problem at once. <h3 id="preview-effect-polymorphic-traversals">Preview: Effect-Polymorphic Traversals</h3> In Part 5, we’ll explore the Effect Path API in depth. The key takeaway is that the same Focus paths work with different effect types: <div class="language-java highlighter-rouge"><div class="highlight"><pre class="highlight"><code>// Same path, different effects TraversalPath<Expr, Expr> allChildren = ExprFocus.children(); // Pure transformation Expr optimised = allChildren.modifyAll(this::optimise, expr); // With Maybe (might fail) MaybePath<Expr> maybeResult = Path.just(expr) .via(e -> allChildren.modifyF(this::tryOptimise, e, maybeApplicative)); // With Validated (accumulate errors) ValidationPath<List<Error>, Expr> validated = Path.valid(expr, Semigroups.list()) .via(e -> allChildren.modifyF(this::validateNode, e, validatedApplicative)); </code></pre></div></div> The Effect Path API turns the theoretical power of <code class="language-plaintext highlighter-rouge">modifyF</code> into a practical, fluent interface. <hr /> <h2 id="summary">Summary</h2> This article introduced traversals and the Focus DSL’s <code class="language-plaintext highlighter-rouge">TraversalPath</code> for recursive manipulation: <ol> <li>TraversalPath: Fluent wrapper for traversals with <code class="language-plaintext highlighter-rouge">getAll()</code>, <code class="language-plaintext highlighter-rouge">modifyAll()</code>, <code class="language-plaintext highlighter-rouge">foldMap()</code></li> <li>Collection Navigation: <code class="language-plaintext highlighter-rouge">each()</code> for lists, <code class="language-plaintext highlighter-rouge">at()</code> for indices, <code class="language-plaintext highlighter-rouge">atKey()</code> for maps</li> <li>Conditional Updates: <code class="language-plaintext highlighter-rouge">modifyWhen()</code> for predicate-based transformations</li> <li>Sum Type Navigation: <code class="language-plaintext highlighter-rouge">AffinePath.instanceOf()</code> for type-safe variant targeting</li> <li>Deep Traversal: Bottom-up and top-down recursive descent</li> <li>Composable Optimiser: Multiple passes running to fixed point</li> </ol> The Focus DSL separates what to visit from what to do. Build paths declaratively, then apply operations fluently. This is the optics philosophy made accessible. <h3 id="the-higher-kinded-j-advantage-for-tree-operations">The Higher-Kinded-J Advantage for Tree Operations</h3> The Focus DSL transforms what could be tedious tree manipulation into expressive, readable code. Consider what we achieved: <ol> <li> Fluent navigation with TraversalPath: Instead of writing custom traversals, we chain methods: <code class="language-plaintext highlighter-rouge">.departments().each().employees().each().salary()</code>. The path describes the data shape, not the mechanics of traversal. </li> <li> Collection navigation built-in: Methods like <code class="language-plaintext highlighter-rouge">each()</code>, <code class="language-plaintext highlighter-rouge">at()</code>, and <code class="language-plaintext highlighter-rouge">atKey()</code> handle the common cases. No need to write <code class="language-plaintext highlighter-rouge">Traversals.list()</code> and compose it manually. </li> <li> Conditional updates with modifyWhen: Target specific elements with predicates directly on the path. The intent is clear and the implementation is correct by construction. </li> <li> Sum type integration: <code class="language-plaintext highlighter-rouge">AffinePath.instanceOf()</code> bridges sealed interfaces with the Focus DSL. Navigate to specific variants type-safely. </li> <li> Effect polymorphism underneath: The Focus DSL wraps Higher-Kinded-J’s effect-polymorphic traversals. When you need <code class="language-plaintext highlighter-rouge">modifyF</code> for validation or state, the same paths work. </li> </ol> The Focus DSL embodies the principle: common things should be easy, powerful things should be possible. Most operations use the fluent API; when you need maximum control, the underlying traversals are always accessible. <hr /> <h2 id="whats-next">What’s Next</h2> We’ve built a powerful foundation for tree manipulation with the Focus DSL. Our <code class="language-plaintext highlighter-rouge">TraversalPath</code> chains can visit every node, <code class="language-plaintext highlighter-rouge">foldMap</code> can aggregate information, and optimisation passes compose cleanly. But we’ve been working with pure transformations. Real compilers need effects: <ul> <li>Type checking should accumulate errors, not fail on the first one</li> <li>Interpretation needs to track variable bindings (state)</li> <li>Optimisation might need logging for debugging</li> </ul> In Part 5, we’ll explore effect-polymorphic optics with <code class="language-plaintext highlighter-rouge">modifyF</code>. The Focus DSL integrates seamlessly: <div class="language-java highlighter-rouge"><div class="highlight"><pre class="highlight"><code>// Preview: effectful modification through Focus paths Kind<ValidatedKind.Witness<List<TypeError>>, Employee> result = employeePath.modifyF( emp -> validateEmployee(emp), // Returns Validated employee, validatedApplicative ); </code></pre></div></div> The same Focus paths we’ve built work with <code class="language-plaintext highlighter-rouge">Validated</code> for error accumulation, <code class="language-plaintext highlighter-rouge">State</code> for environment threading, and any other effect. Higher-Kinded-J provides the type-class instances that make this polymorphism possible. We’ll see how <code class="language-plaintext highlighter-rouge">Validated</code> differs from <code class="language-plaintext highlighter-rouge">Either</code> (accumulating all errors rather than short-circuiting), how <code class="language-plaintext highlighter-rouge">State</code> threads environment bindings through interpretation, and how these effects compose with Focus paths. The expression language will gain a full type system and interpreter, all built on the same Focus DSL foundations. <hr /> <h2 id="further-reading">Further Reading</h2> <h3 id="tree-traversals-and-recursion-schemes">Tree Traversals and Recursion Schemes</h3> <ul> <li>Patrick Thomson, <a href="https://blog.sumtypeofway.com/posts/introduction-to-recursion-schemes.html">“An Introduction to Recursion Schemes”</a>: A gentle introduction to the theory behind generic tree traversal patterns like catamorphisms and anamorphisms.</li> </ul> <h3 id="compiler-optimisation">Compiler Optimisation</h3> <ul> <li>Andrew Appel, Modern Compiler Implementation in ML: Classic text covering constant folding, dead code elimination, and the other optimisations we’ve implemented. Available in Java and C editions.</li> </ul> <h3 id="term-rewriting">Term Rewriting</h3> <ul> <li> Franz Baader & Tobias Nipkow, Term Rewriting and All That: For readers interested in the theoretical foundations of pattern-based rewriting systems. </li> <li> The optimisation passes in this article are simple term rewrites. Industrial strength rewriting (like in GHC’s rule system) adds phases, termination proofs, and confluent rule ordering. </li> </ul> <h3 id="algebraic-data-types-in-java">Algebraic Data Types in Java</h3> <ul> <li><a href="https://blog.scottlogic.com/2025/01/20/algebraic-data-types-with-java.html">“Algebraic Data Types with Java”</a> (Scott Logic, 2025): A thorough introduction to algebraic data types using Java’s sealed interfaces and records. Covers how sum types (like our expression AST) and product types compose to model complex domains.</li> </ul> <h3 id="higher-kinded-j">Higher-Kinded-J</h3> <ul> <li> <a href="https://github.com/higher-kinded-j/higher-kinded-j/blob/main/hkj-api/src/main/java/org/higherkindedj/optics/Traversal.java">Traversal Documentation</a>: API reference for working with multi-focus optics. </li> <li> <a href="https://github.com/higher-kinded-j/higher-kinded-j/blob/main/hkj-core/src/main/java/org/higherkindedj/optics/util/Traversals.java">Traversals Utility Class</a>: Helper methods for <code class="language-plaintext highlighter-rouge">getAll</code>, <code class="language-plaintext highlighter-rouge">modify</code>, and fold operations. </li> <li> <a href="https://higher-kinded-j.github.io/latest/optics/ch4_intro.html">Focus DSL Guide</a>: Fluent navigation with FocusPath, AffinePath, and TraversalPath. </li> <li> <a href="https://higher-kinded-j.github.io/latest/effect/ch_intro.html">Effect Path API Guide</a>: Railway-style error handling with MaybePath, EitherPath, and ValidationPath. </li> </ul> <hr /> <h3 id="next-time">Next time</h3> Real compilers and interpreters need more. Type checking should report all errors, not just the first one. Interpretation must track variable bindings as it descends through the tree. These are effects, and they change everything. Next time, in Part 5 we take a closer look at how effects help structure our code. https://blog.scottlogic.com/2026/01/30/traversals-rewrites.html