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

Thanks for the link, Matt!