Ever wondered what happens when you feed a thought-provoking programming concept to an AI and ask it to implement it? I did exactly that with Tyler Glaiel's blog post about tree traversal primitives, and the results from Claude 3.7 Sonnet were nothing short of fascinating.
The Challenge: From Blog Post to Working Rust Crate #
It all started with Tyler Glaiel's insightful post titled "Programming languages should have a tree traversal primitive". In it, Tyler articulated a common frustration many developers face: while programming languages have elegant primitives for linear traversal (for loops), they lack equivalent elegance when dealing with tree structures.
Tyler proposed a syntax that looked like this:
1for_tree(Node* N = mytreeroot; N != NULL; N : {N->left, N->right}){
2 print(N->value);
3}
The simplicity and elegance of this concept struck me. Rather than tackling this implementation challenge myself, I wondered: could Claude do this justice? Could it take this concept and craft a proper Rust implementation without getting lost in the complexity of macros, recursion, and borrow checking?
The Prompt Structure: Guiding Claude's Problem-Solving Process #
For this experiment, I didn't just paste the blog post and ask Claude to code something up. Instead, I created a custom prompt structure that guided Claude to approach the problem like an experienced developer would – with clear planning, systematic reasoning, and reflective practice.
The prompt framework I designed required Claude to use specific XML-tagged blocks:
- Plan tasks in a structured format with clear steps
- Reason through problems by explicitly articulating its thought process
- Make code changes in an organized way, focusing on one issue at a time
- Summarize completed work to reflect on progress and identify next steps
This structured approach essentially forced Claude to "show its work" – not just provide code, but explain why certain decisions were made and how problems were approached.
Inside Claude's Mind: Examples of Planning and Reasoning #
What made this collaboration particularly fascinating was seeing the structured thinking process Claude used. Here's what Claude's planning looked like at the start of the project:
1<planning title="Implement tree traversal primitive in Rust">
2 <step>Analyze the requirements for the tree traversal primitive</step>
3 <step>Design the macro API to be intuitive and similar to the blog post example</step>
4 <step>Implement the core recursive traversal function</step>
5 <step>Create the macro that provides the user-friendly syntax</step>
6 <step>Add support for break, continue, and prune control flow</step>
7 <step>Test the implementation with various examples from the blog post</step>
8 <step>Document the usage with comments and examples</step>
9</planning>
This wasn't just a formality—Claude actually followed this plan step by step, addressing each aspect systematically.
When facing specific challenges, Claude's reasoning process was equally structured. For example, when deciding how to handle control flow in the traversal, Claude reasoned:
1<reasoning>
2The blog post describes a tree traversal primitive that should:
3
41. Allow easy traversal of tree-like structures without explicit recursion
52. Support a syntax similar to a for loop: for_tree(init; condition; branch) { body }
63. Support control flow with break, continue, return, and a new "prune" operation
74. Handle both in-memory trees (like Node structures) and imperative trees
8 (like generating strings)
95. Be intuitive and less error-prone than writing recursive functions
10
11In Rust, we can implement this using macros. The challenging part will be supporting
12the special control flow operations. Standard break/continue won't work naturally with
13recursion, so we'll need to create a special enum to represent these operations and
14have the macro generate code that handles them properly.
15
16For the "prune" operation, we can return early from the current recursive call without
17processing children. For "break", we'll need to propagate a special return value up
18through the call stack.
19</reasoning>
This kind of explicit reasoning led to more thoughtful design decisions than simply trying to code the solution directly.
When Claude encountered errors during implementation, the structured approach really showed its value. Here's how Claude reasoned through a type mismatch error:
1<reasoning>
2Looking at the error message:
3
4error[E0308]: mismatched types
5 --> src/lib.rs:316:30
6 |
7316 | for_tree!(n = 0; n < 10; vec![n + 1] => {
8 | ^^ expected `&_`, found integer
9
10The issue is in how we're handling references in the macro. When using the simplified
11syntax `n = 0`, the macro is expanding in a way that treats `n` as a reference when
12checking the condition, but the comparison `n < 10` is trying to compare a reference
13with an integer directly.
14
15We need to ensure consistent reference handling throughout the macro. We have
16two options:
171. Update the condition function to dereference automatically
182. Modify how the simplified syntax expands to handle this case
19
20I think option 1 is cleaner - we should ensure that when the condition function
21receives a reference, it properly dereferences it before making comparisons.
22</reasoning>
This systematic approach to debugging led to a more robust solution than just trying quick fixes.
The Development Process: From Concept to Code #
When presented with the task, Claude methodically implemented each part of the design plan. For the core functionality, it created a TreeControl enum to handle different traversal behaviors:
1#[derive(Debug, Clone, Copy, PartialEq, Eq)]
2pub enum TreeControl {
3 /// Continue traversal normally
4 Continue,
5 /// Skip traversing children of the current node
6 Prune,
7 /// Break out of the entire traversal
8 Break,
9}
And implemented a flexible traversal function that could work with any tree-like structure:
1pub fn traverse_tree<T, C, B, F>(
2 initial: T,
3 condition: C,
4 branch_fn: B,
5 mut visit_fn: F,
6) where
7 T: Clone,
8 C: Fn(&T) -> bool,
9 B: Fn(&T) -> Vec<T>,
10 F: FnMut(&T) -> TreeControl,
11{
12 // Define the recursive traversal function
13 fn traverse_internal<T, C, B, F>(
14 node: &T,
15 condition: &C,
16 branch_fn: &B,
17 visit_fn: &mut F,
18 ) -> TreeControl
19 where
20 T: Clone,
21 C: Fn(&T) -> bool,
22 B: Fn(&T) -> Vec<T>,
23 F: FnMut(&T) -> TreeControl,
24 {
25 // Visit the current node
26 let result = visit_fn(node);
27
28 // Handle control flow
29 match result {
30 TreeControl::Break => return TreeControl::Break,
31 TreeControl::Prune => return TreeControl::Continue,
32 TreeControl::Continue => {}
33 }
34
35 // Get branches and continue traversal if condition is met
36 for child in branch_fn(node) {
37 if condition(&child) {
38 let child_result = traverse_internal(&child, condition, branch_fn, visit_fn);
39 if child_result == TreeControl::Break {
40 return TreeControl::Break;
41 }
42 }
43 }
44
45 TreeControl::Continue
46 }
47
48 // Only traverse if the initial node meets the condition
49 if condition(&initial) {
50 traverse_internal(&initial, &condition, &branch_fn, &mut visit_fn);
51 }
52}
After completing major components, Claude would summarize the progress and reflect on the implementation:
1<summary>
2I've implemented a tree traversal primitive for Rust using macros, as described in
3Tyler Glaiel's blog post. The implementation features:
4
51. A clean, intuitive syntax similar to for loops:
6 `for_tree!(var = init; condition; branches => { body })`
7
82. Support for special control flow operations:
9 - `break_tree!()` - exits the entire traversal
10 - `prune!()` - skips traversing children of the current node
11
123. Multiple syntax variants for flexibility:
13 - Using the 'in' keyword: `for_tree!(node in root; condition; branches)`
14 - Using '=' for simpler cases: `for_tree!(node = root; condition; branches)`
15
164. Works with both in-memory tree structures and imperative tree generation
17
185. Comprehensive examples and tests showing various use cases
19
20The implementation is a zero-cost abstraction - it compiles down to efficient code
21equivalent to hand-written recursive functions while providing a much more
22intuitive interface.
23</summary>
These structured reflections helped guide future improvements and ensure nothing was missed.
The Result: Arboriter Is Born #
After several iterations of implementation and refinement, the result was impressive—a working Rust crate called "arboriter" that fully implemented Tyler's vision. The syntax was clean and intuitive:
1for_tree!(node in &root; |_| true; |node| {
2 let mut children: Vec<&BinaryNode<i32>> = Vec::new();
3 if let Some(left) = &node.left {
4 children.push(left.as_ref());
5 }
6 if let Some(right) = &node.right {
7 children.push(right.as_ref());
8 }
9 children
10} => {
11 println!("Value: {}", node.value);
12
13 if node.value == 10 {
14 break_tree!(); // Exit the traversal
15 }
16});
But Claude didn't stop at just the implementation. The structured development approach also produced:
- Comprehensive documentation with clear examples
- A complete test suite covering core functionality
- Example programs demonstrating practical applications
- A properly organized crate structure ready for publication
Beyond Basic Trees: Creative Applications #
What surprised me most was how Claude extended the concept beyond basic tree traversal to showcase the versatility of the primitive:
Generating All Strings of a Given Alphabet #
1for_tree!(s in String::new(); |s| s.len() <= 3; |s| {
2 let mut branches: Vec<String> = Vec::new();
3 for c in alphabet.chars() {
4 branches.push(format!("{}{}", s, c));
5 }
6 branches
7} => {
8 println!("Generated: \"{}\"", s);
9
10 if s.len() == 3 {
11 prune!(); // Don't generate longer strings
12 }
13});
Creating Balanced Parentheses #
1// Generate all valid balanced parentheses strings with at most n pairs
2for_tree!(state in ("".to_string(), 0, 0); |state| state.1 <= n; |state| {
3 let (s, open, close) = state;
4 let mut branches = Vec::new();
5
6 // We can add an open paren if we haven't used all n
7 if open < n {
8 branches.push((format!("{}(", s), open + 1, close));
9 }
10
11 // We can add a close paren if there are unclosed open parens
12 if close < open {
13 branches.push((format!("{})", s), open, close + 1));
14 }
15
16 branches
17} => {
18 let (s, open, close) = state;
19
20 // Only print fully balanced strings
21 if open == close && open > 0 {
22 println!("Generated: {}", s);
23 }
24});
Traversing File System Structures #
1for_tree!(node in &fs_root; |_| true; |node| {
2 // Only directories have children to traverse
3 if node.is_directory {
4 node.children.iter().collect()
5 } else {
6 Vec::new()
7 }
8} => {
9 let indent = " ".repeat(get_depth(node, &fs_root));
10 let node_type = if node.is_directory { "DIR" } else { "FILE" };
11 println!("{}{}: {}", indent, node_type, node.name);
12});
The Final Push: Polishing for Publication #
Toward the end of the project, Claude demonstrated remarkable attention to detail. When preparing the crate for publication, Claude's reasoning showed careful consideration of the user experience:
1<reasoning>
2Before publication, we need to ensure the crate meets high-quality standards:
3
41. Documentation is crucial - users need to understand how to use this primitive
5 without extensive training. Each function and macro should have examples.
6
72. Error messages need to be clear and helpful - the macro should produce
8 understandable errors when used incorrectly.
9
103. We should have a comprehensive set of examples covering different use cases
11 to inspire users.
12
134. The API should follow Rust conventions and be consistent with how other
14 macros in the ecosystem work.
15
16For the crate name, "arboriter" combines "arbor" (tree) with "iter" (iteration),
17while also hinting at "arborist" (tree specialist). This name effectively
18communicates the purpose while being memorable and unique in the Rust ecosystem.
19</reasoning>
This kind of holistic thinking about the entire user experience elevated the project from merely functional code to a polished, publishable crate.
Lessons Learned: The Impact of Structured AI Collaboration #
This experiment revealed several valuable insights about working with Claude on complex programming tasks:
1. Structure Creates Better Thinking #
By requiring Claude to plan, reason, implement, and reflect separately, the quality of its output dramatically improved. The structure didn't constrain creativity—it enhanced it by enforcing methodical problem-solving.
2. Explicit Reasoning Leads to Better Solutions #
When Claude was required to explain its reasoning before implementing solutions, the resulting code was more robust and correct. This mirrors how human developers often benefit from rubber-duck debugging or writing design documents.
3. Iterative Refinement Is Key #
The development wasn't a one-shot perfect implementation. It took several rounds of testing and refinement, with Claude learning from errors and improving its approach. This mirrors real-world software development.
4. Documentation Becomes Part of the Process #
Because documentation was built into the structured approach, the resulting code was well-documented from the start—not as an afterthought. This produced a much more usable final product.
Conclusion: A New Era of Collaborative Programming #
The arboriter project demonstrates the exciting possibilities of human-AI programming collaboration. By providing both a concept (via Tyler's blog post) and a structured development framework, I was able to guide Claude to create a sophisticated, well-implemented Rust crate that I couldn't have built as quickly on my own.
This doesn't mean AI will replace programmers—far from it. Instead, it suggests a future where programmers can operate at a higher level of abstraction, focusing on concepts and design while collaborating with AI to handle implementation details. The key insight is that how we prompt and structure these collaborations dramatically affects the quality of the results.
The code for arboriter is available on GitHub, and I encourage you to check it out. It stands as a testament to what's possible when human guidance meets AI implementation capability, especially when that collaboration is deliberately structured to bring out the best in both parties.
Rust Crate GitHub Repository Documentation