Fully generic recursion in Rust

Previously, we introduced a method for writing performant stack safe recursion in Rust for a single recursive data structure. This post uses the same ideas to implement a single recursion backend that can collapse or expand any recursive data structure.
Read more →

Elegant and performant recursion in Rust

This is a post about writing elegant and performant recursive algorithms in Rust. It makes heavy use of a pattern from Haskell called recursion schemes, but you don't need to know anything about that; it's just an implementation detail. Instead, as motivation, I have benchmarks showing a 14-34% improvement over the typical boxed pointer representation of recursive data structures in Rust.
Read more →

Stack Machines for Free

Previously we saw how to expand seed values into recursive structures given a function that expands a single layer of structure, and how to collapse recursive structures into a single value given a function that consumes a single layer of structure. Here we'll see how to fuse those two steps, to generate a stack machine that simultaneously expands and collapses recursive structures, given just a function for expanding layers and a function for collapsing layers.

execution graph for simultaneously expanding and collapsing a simple expression

Read more →