Append an element to a recursive list iteratively

help
1

Hi,

I've been playing around with loops over recursive data structures a bit. There were some surprises and I was wondering if my examples could be improved. Note that I know that tloops probably are not the best way to solve the problem, but I am specifically interested what the limitations of loops in those cases are.

Here's my code to insert an element at the end:

pub enum List {
    Node(i32, Box<List>),
    Nil
}

fn append_iter(list: &mut List, element: i32) {
    let mut current = list;

    loop {
        let cu = current; // needed to unconfuse borrowck
        current = match *cu {
            List::Node(_, ref mut tail) => tail,
            List::Nil => {
                *cu = List::Node(element, Box::new(List::Nil));
                break;
            }
        };
    }
}

Now this works, but it's not too nice. I've two questions: is there some way to use a while let or something similar (instead of the loop with break) and is there some way to get a reference to the tail out of the loop that can be used to insert the new element after the loop?

2

Yes, Rust has exactly while let pattern = expr { .. }

But unfortunately the current borrowchecker gets very confused with loops and borrows, and I don't believe there's any way to convince the compiler that what you're doing is the right thing while using while-let. As you clearly know, the general trick with mutable borrows and loops is to move the old loop variable to a temporary value at the start of the loop before matching on it, but of course you can't do that with while-let.

Here's a hack to get the reference out though:

pub enum List {
    Node(i32, Box<List>),
    Nil
}

fn append_iter(list: &mut List, element: i32) {
    let mut current = list;

    loop {
        let temp = current;
        if let List::Node(_, ref mut tail) = *temp {
            current = tail;
        } else {
            // need to reassign `current` at the end, because Rust correctly 
            // determines `current` will be uninit otherwise
            current = temp;
            break;
        }
    }
    *current = List::Node(element, Box::new(List::Nil));
}
1 Like
3

Great, thank you very much!