Can I access full list inside split_last_mut()?

help
1

I try to implement partial recursive function recently.

Partial recursive function will take a list of number, and inspect the last one.
If the last number is 0, it will call another function f.
If it is not 0, it will minus 1 and call the recursively call itself.

Here is the code:

pub fn recurse(f: F, g: G, values: &mut[u32]) -> u32 {
    let easier_values = &mut values.to_vec()[..];
    if let Some((last, elems)) = easier_values.split_last_mut() {
        if *last == 0 {
            return f(elems);
        } else {
            *last = *last - 1;
        }
    }
    let mut easier_result = recurse(f.clone(), g.clone(), easier_values);
    if let Some((last, elems)) = easier_values.split_last_mut() {
        return g(elems, last, &mut easier_result);
    }
    unreachable!();
}

What I want to ask is that I have to write two split_last_mut otherwise rustc will stop me. However I think maybe there is a way that I don't have to call split_last_mut twice?

2

You have to, because recurse is allowed to modify any element in easier_values, and mere possibility of this happening invalidates all prior references to elements in this slice.

But this looks like infinite recursion? Did you really mean to pass all ements to recurse rather than e.g. only elems?

3

It decrements the last elem, and some recursive call will eventually trigger the return f(elems) bit. I agree the code is a bit circuitous, but perhaps that's an artifact of coming up with a minimal repro/example.

I also didn't quite understand why easier_values exists, which is a temp Vec allocation - seems just using values should work.

@yodalee, if you somehow need to keep the code structured like this, you can use &[Cell<u32>] instead of &mut [u32] and then don't need mutable borrows anymore - that will let you keep the borrow across recurse calls.

If you want to keep discussing things in this thread, I'd suggest putting the code into the playground so it's a bit easier to help you.

4

@kornel: It will not infinite recursion, since innermost recurse will trigger function f and start return.

@vitalyd thanks for reply.

I cannot pass easier_value to another recurse call, since it has been borrowed at split_last_mut.

I create playground to show the result, and I will try Cell first.

5

Personally, I'd just call split_last_mut() again and move on:

pub fn recurse(f: F, g: G, values: &mut [u32]) -> u32 {
    if let Some((last, elems)) = values.split_last_mut() {
        if *last == 0 {
            return f(elems);
        } else {
            *last -= 1;
        }
        let mut easier_result = recurse(f.clone(), g.clone(), values);
        let (last, elems) = values.split_last_mut().unwrap();
        return g(elems, last, &mut easier_result);
    }
    unreachable!();
}

What's your concern with the 2nd call? Note you don't need the easier_values, as mentioned.

6

I know, I will try to remove it.
I wonder whether two split_last_mut call may be duplicate and have some performance issue? Or maybe split_last_mut is just return a reference so no penalty will pay?

7

I wouldn't worry about the performance here (or at least not yet). For example, godbolt shows that repeated calls to split_last_mut within the same fn are optimized out - the compiler loads the value just once, and then just does comparisons.

8

Understood, thanks.