Convert tail-recursive form to iterative form?

help
1

How can I convert the following tail-recursive function to an iterative function?

fn main() {}

fn test<'a, K: Bound, V>(b: &K, x: &'a mut BoundNode<K, V>) -> &'a mut BoundNode<K, V> {
    match *x {
        BoundNode::Branch { ref mut left, ref mut right, .. } => test(
            b,
            if left.bound().cost(b) <= right.bound().cost(b) {
                left
            } else {
                right
            },
        ),
        BoundNode::Leaf { .. } => x,
    }
}

#[derive(Clone, Debug)]
enum BoundNode<K, V> {
    Leaf {
        bound: K,
        node: V,
    },
    Branch {
        bound: K,
        left: Box<BoundNode<K, V>>,
        right: Box<BoundNode<K, V>>,
    },
}

impl<K, V> BoundNode<K, V> {
    fn bound(&self) -> &K {
        match self {
            BoundNode::Leaf { bound, .. } => bound,
            BoundNode::Branch { bound, .. } => bound,
        }
    }
}

pub trait Bound {
    type Distance: PartialOrd;
    fn join(&self, &Self) -> Self;
    fn cost(&self, &Self) -> Self::Distance;
}
2

nll will let you do it without unsafe but until that comes;

    let mut y: &BoundNode<K, V> = x;
    loop {
        match y {
            BoundNode::Branch { ref left, ref right, .. } => {
                y = if left.bound().cost(b) <= right.bound().cost(b) {
                    left
                } else {
                    right
                };
            },
            BoundNode::Leaf { .. } => break,
        }
    }
    unsafe { &mut *(y as *const _ as *mut _) }
3

Well, if it's between unsafe and tail-recursion, does Rust guarantee TCO?

4

Pretty sure TCO is not guaranteed - it's an optimization pass in LLVM which may or may not trigger. Debug builds will certainly not have it.

Personally, I'd go with unsafe if recursion depth is a concern. NLL can't come soon enough :slight_smile:.

5

I'm pretty sure there's no need for unsafe:

fn test<'a, K: Bound, V>(b: &K, mut x: &'a mut BoundNode<K, V>) -> &'a mut BoundNode<K, V> {
    loop {
        match {x} {
            BoundNode::Branch { left, right, .. } =>
                if left.bound().cost(b) <= right.bound().cost(b) {
                    x = left;
                } else {
                    x = right;
                },
            e => return e,
        }
    }
}

Compiles on stable: Rust Playground

If, like me the first time I hit this, you're wondering WTF is going on, bluss has helpfully explained in Stuff the Identity Function Does (in Rust)

Edit: Oh, and rust definitely doesn't guarantee TCO. In fact afaik it never does it in debug mode, so you really don't want to depend on it. The become keyword is reserved for demanding TCO -- it will do things like change drop locations, too, so more code can be tailed -- but it hasn't happened yet. See https://github.com/rust-lang/rfcs/pull/81 and https://github.com/rust-lang/rfcs/pull/1888 for some previous discussion.

5 Likes
6

Well spotted. It was first thing I tried but assumed wrong in thinking the error was due to that way not going to work. I left in the BoundNode::Leaf match and failed to associate the error. Definitely not a nice intuitive construct so much prefer nll making it pass without.

1 Like