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