# 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 ! 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).

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 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 ?

--
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

``````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.