# Stack overflow-free mapping over nested data

I would like to map over a deeply nested recursive data structure.
Is there a safe way (i.e. no `unwrap()` etc.) to do this without getting stack overflows?

An example of what I want to achieve (playground):

``````#[derive(Debug)]
enum BinaryTree {
Node(Box<BinaryTree>, Box<BinaryTree>),
Leaf(i32),
}

use BinaryTree::*;

impl BinaryTree {
/// Applies the given function to every leaf in the tree
fn map<F: Fn(i32) -> i32>(&mut self, f: &F) {
match *self {
Node(ref mut tree1, ref mut tree2) => {
tree1.map(f);
tree2.map(f);
}
Leaf(ref mut n) => *n = f(*n),
}
}
}

fn main() {
let mut tree = Leaf(0);
/// create a deep tree
for i in 1..100000 {
tree = Node(Box::new(Leaf(i)), Box::new(tree));
}
// BOOM! stack overflow
tree.map(&|i| i + 1)
}
``````

You can always transform a recursive function into an iterative one, by using a Vec to simulate the stack. (instead of calling `tree1.map`, push `&tree1` to the stack, and loop)

With this little trick you can get rid of the stack size limit. But maybe you want something more interesting, using less memory?

It's the creation of your deep tree that is smashing the stack (on the playground anyway). I didn't look further but my guess is that it's building all values on the stack before boxing them or such. If you run it in release mode instead, it runs to completion.

Here's a simple non-recursing `map` I made before I realized creation was overflowing.

Thank you a lot for your non-recursing map. This is some really interesting stuff.

Nonetheless, I have found out in the meantime that the stack overflow is not caused by the mapping function, but by the destructor that is called when the tree is dropped at the end of the `main` function.

In case it's helpful to anyone with similar issues, the â€śToo Many Listsâ€ť book explains the problem with `Drop` and recursive data structures, and its solution: Drop - Learning Rust With Entirely Too Many Linked Lists

2 Likes