Recursive auxiliary function and little recursive things

Hi there !

To more deeper the rust language, i've decided to code the List standard library of Ocaml. But I get an issue.

pub fn init<U: Fn(u32) -> T>(length: u32, f: U) -> Self
    {
        let aux = |i: u32, stackl: Self| 
                    if i == length { stackl }
                    else { aux(i+1, List::<T>::cons(f(i),stackl)) };
        aux(0,Nil)
    }   

The goal of this function is to return a List<T> object, which is initialized with [f(0) ; f(1) ; ... ; f(length - 1) ]. I've first tried to define a auxilliary function, but that doesn't capture length, so i've tried with closure, but I can't do this because the name of the closure isn't known.

How to do this ?

Other little questions : is it possible to make mutually recursive functions and types in Rust ?

Thanks a lot ! :slight_smile:

You could pass length through,

pub fn init<F: Fn(u32) -> T>(length: u32, f: F) -> Self
    {
        init_inner(0, length, f)
    }   

fn init_inner<F: Fn(u32) -> T>(i: u32, length: u32, f: F) -> Self
    {
        if i == length { Nil }
        else { List::<T>::cons(f(i), init_inner(i+1, length, f)) }
    }   

You could also desugar the closures, like I show in my blog,

1 Like

Yeah I've found about this. But Rust doesn't support tail recursion, isn't it ? So with length usize with 100 elements in my list, I get 400 bytes for ... nothing ?

And about extern function, this function hasn't purpose outside the function. Rust have real function limites >.< (see Rust as functionnal language is a bit oversaid).

But thanks for your link !

You can put the function inside inner.

pub fn init<F: Fn(u32) -> T>(length: u32, f: F) -> Self {
    fn init_inner<T, F: Fn(u32) -> T>(i: u32, length: u32, f: F) -> List<T> {
        if i == length {
            List::Nil
        } else {
            List::cons(f(i), init_inner(i + 1, length, f))
    }

    init_inner(0, length, f)
}

Rust doesn't optimize tail recursion, which is one reason why recursive functions are harder to write.
You could use a trampoline, or write a more idiomatic function:

pub fn init<F: Fn(u32) -> T>(length: u32, f: F) -> Self {
    (0..length)
        .into_iter()
        // Have to reverse indices since we're folding from the end.
        .rev()
        .map(f)
        .fold(List::Nil, |xs, x| List::cons(x, xs))
}
1 Like

This thread inspired me to write a [set of] combinator[s] for creating recursive Fn closures.

The implementation is here updated (see below).

Edit: I took a look inside the crate recur-fn and its approach inspired me to the much simpler solution in the updated link.

It contains functions like this for different arities:

pub fn rec1<A, O>(f: impl Fn(&dyn Fn(A) -> O, A) -> O) -> impl Fn(A) -> O
pub fn rec2<A, B, O>(f: impl Fn(&dyn Fn(A, B) -> O, A, B) -> O) -> impl Fn(A, B) -> O
// ...

With that, you can write something like this:

// demonstration
fn fib(n: u16) -> u16 {
    let helper = rec3(|helper, x, y, i|
        if i == n {
            y
        } else {
            helper(y,x+y,i+1)
        }
    );
    helper(1,0,0)
}

Of course the use is limited since this doesn’t solve the missing tail recursion optimization.

2 Likes

Yes, that for sure is possible.

Thanks for your answers, as rust newbie, your code is incredible :heart_eyes: But I must say that I don't understand all.

About the recursive types : I'm happy, that works from nothing, I've even not tried before asking, I should do ! Just a little question about the

pub fn map<B, F: Fn(A) -> B>(self, f: &F) -> Forest<B> {
        match self {
            Forest::Nil => Forest::Nil,
            Forest::Cons(t, ts) => Forest::cons(t.map(f), ts.map(f)),
        }
    }

It seemed to me that should be f: &dyn F because not sure about the size of the argument ?

--
About your code letting us to write recursive closure :
1/ First, thanks ! I even didn't know the keyword move.
2/ I've absolutely no idea which sort of dark magic is done by this code :

pub fn rec1<A, O>(f: impl Fn(&dyn Fn(A) -> O, A) -> O) -> impl Fn(A) -> O {
    move |a| {
        let r: RefCell<&dyn Fn(A) -> O> = RefCell::new(&|_| unimplemented!());
        let g = |a| (&f)(&*r.borrow(), a);
        *r.borrow_mut() = &g;
        g(a)
    }
}

What the purpose of r ? I think it's just a necessary thing for Rust compiler, but what does it do ?
And ... |a| (&f)(&*r.borrow(), a). No idea what happens here >.<" A function is called, and the function is called by reference for avoiding being captured by the closure by move, but why use move keyword so ?

In all cases, really thanks. I'm new to rust, and your code is just as a magical cookie I must found the recept made from :3

[NB : For my english, it looks to me that it's worst than usually]

I will choose not to explain this code, (well, I did it anyways in my next post) since I found the easier approach that I also edited into my previous comment. I do however want to note that was not super dark magic in the form of unsafe code.

In this map function the closure type F is a generic type parameter. What that means is that for every closure that map is used with the compiler will generate a specialized version of map. These generated versions then each know about the size of their respective F.

By the way, the reason why I’m taking the parameter f as the type “reference to F” is that I can then copy that reference into multiple recursive calls to t.map(f) and ts.map(f).

Okay, just a short explanation. The monster (&f)(&*r.borrow(), a) can actually be written f(&*r.borrow(), a) (I know, only slightly better), the extra & appeared in an (unsuccessful) attempt to make the compiler happy during development that I forgot to revert. The idea behind this approach was:

First create a function reference r, pointing to a dummy/stub, then create g which is kind-of recursive because it accesses r, where r is actually modified to point to g after g is created and before g is first called.

let r: RefCell<&dyn Fn(A) -> O> = RefCell::new(&|_| unimplemented!()); // r pointing to dummy
let g = |a| f(&*r.borrow(), a); // g is created
*r.borrow_mut() = &g; // r is modified to point to g
g(a) // g is called

Thinking about r as eventually pointing to g, we have, intuitively speaking: g = |a| f(&g, a).

2 Likes

Very ingenious! Almost daily I find myself again amazed at what can be written in safe Rust.

1 Like

In this case unnecessarily so, since I can use an actually recursive fn instead (as you probably already saw).

I also have to admit that I probably needed about 5-10 iterations for the type of r before I reached RefCell<&dyn Fn(A) -> O>, some of which included a significant amount of extra Box and Rc etc...

I was particularly disappointed that this doesn’t work:

let f: Box<dyn Fn(u32) -> u32>;
f = Box::new(|a| if a > 0 { f(a - 1) } else { 0 });
1 Like

About your previous test :

let f: Box<dyn Fn(u32) -> u32>;
f = Box::new(|a| if a > 0 { f(a - 1) } else { 0 });

If I well understand, rustc is crying cause of two errors :

  • First, the closure uses a possible non-initialized variable (f).
  • Second is more trickier, and I'm not sure I understand. It tells
error[E0597]: `f` does not live long enough
 --> rec2.rs:4:33
  |
4 |     f = Box::new(|a| if a > 0 { f(a - 1) } else { 0 });
  |                  ---            ^ borrowed value does not live long enough
  |                  |
  |                  value captured here
5 | }
  | -
  | |
  | `f` dropped here while still borrowed
  | borrow might be used here, when `f` is dropped and runs the destructor for type `std::boxed::Box<dyn std::ops::Fn(u32) -> u32>`

Why the closure captures the ownership of f ? The keyword move makes it happening, but no move keyword here ?!

Last question : why do you use the move keyword in your easier approach ? What's the point ?

And thanks for your explanations. They make rust magic to me <3

It doesn't. The capture is only a borrow of f.

The code for reference

pub fn rec1<A, O>(f: impl Fn(/* ... */) -> O) -> impl Fn(A) -> O {
    fn recurse</*...*/>(f: /*...*/, a: A) -> O {
        /* ... */
    }
    move |a| recurse(&f, a)
}

The point is: rec1 returns a closure. That closure is |a| recurse(&f, a). The body of that closure only uses a reference to f, hence the compiler detemines that it only needs to capture f by reference. However that would limit the lifetime of the closure to the lifetime of f (which was passed by-value to rec1 so it would be dropped at the end of the body of rec1). This problem can be avoided if the closure captures f by value instead. If the closure does that, then f will not be dropped at the end of rec1 but it will be returned inside of the closure that’s returned.

To accomplish this, the move keyword is used. This keyword when placed in front of a closure expression tells the compiler that that closure should capture all the variables that it accesses by value (or in Rust terminology, “move” all the captured variables inside the closure).

By the way, the rust compiler might have answered your question, too. When removing move it even suggest adding it back in.

error[E0373]: closure may outlive the current function, but it borrows `f`, which is owned by the current function
 --> src/main.rs:6:6
  |
6 |      |a| recurse(&f, a)
  |      ^^^          - `f` is borrowed here
  |      |
  |      may outlive borrowed value `f`
  |
note: closure is returned here
 --> src/main.rs:2:59
  |
2 | pub fn rec1<A, O>(f: impl Fn(&dyn Fn(A) -> O, A) -> O) -> impl Fn(A) -> O {
  |                                                           ^^^^^^^^^^^^^^^
help: to force the closure to take ownership of `f` (and any other referenced variables), use the `move` keyword
  |
6 |      move |a| recurse(&f, a)
  |      ^^^^^^^^

error: aborting due to 2 previous errors
1 Like

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.