This is the third post in a three-post series. In the first post we developed a stack-safe, ergonomic, and concise method for working with recursive d

Single Pass Recursion in Rust

submited by
Style Pass
2022-10-05 23:00:18

This is the third post in a three-post series. In the first post we developed a stack-safe, ergonomic, and concise method for working with recursive data structures (using a simple expression language as an example). In the second post we made it fully generic, providing a set of generic tools for expanding and collapsing any recursive data structure in Rust.

In this post we will see how to combine these two things - expanding a structure and collapsing it at the same time, performing both operations in a single pass. In the process, we will gain the ability to write arbitrary recursive functions over traditional boxed-pointer recursive structures (instead of the novel RecursiveTree type introduced in my previous post) while retaining stack safety.

This post covers functionality already implemented in my recursion crate. For that reason, it will focus on diagrams over code, but the relevant code is provided if you're interested or curious.

Leave a Comment