How can I implement Y-Combinator with FnMut in Rust?

Question

I found a implementation of Y-Combinator which supports Fn. However I want to have a version of FnMut.

However, FnMut can not be wrapped into Rc, so I wrap them in Rc<RefCell>. The following code can make a[i] = i in a recursive way. It is the simplest code I have found to test if we can call itself inside a closure.

// test code part

let mut a = vec![0; 5];
let n = a.len();

y_mut(Rc::new(RefCell::new(|f: Rc<RefCell<dyn FnMut(usize)>>| {
    move |i| {
        if i < n {
            a[i] = i;
            ((*f).borrow_mut())(i + 1);
        }
    }
})))(0);

println!("a is {:?}", a);

And this my version of y_mut, derived from the demo.

fn y_mut<A, O, F>(f: Rc<RefCell<dyn FnMut(Rc<RefCell<dyn FnMut(A) -> O>>) -> F>>) -> impl FnMut(A) -> O
    where
        F: FnMut(A) -> O,
        F: 'static,
        A: 'static,
        O: 'static,
{
    struct X<F>(Rc<RefCell<dyn FnMut(X<F>) -> F>>);

    impl<F> Clone for X<F> {
        fn clone(&self) -> Self {
            Self(Rc::clone(&self.0))
        }
    }

    impl<F> X<F> {
        fn call(&self, x: Self) -> F {
            ((*self.0).borrow_mut())(x)
        }
    }

    let f = Rc::new(RefCell::new(move |x: X<F>| {
        let mut ff = (*f).borrow_mut();
        ff(Rc::new(RefCell::new(move |a| (x.call(x.clone()))(a))))
    }));
    let x = X(f);
    (|x: X<F>| x.call(x.clone()))(x)
}

However, this code can't compile, since |f: Rc<RefCell<dyn FnMut(usize)>>| only implments FnOnce, rather than FnMut. I wonder how to fix that?

Answer 1

The move in your test code's closure makes it also move a into the closure. You can prevent that by making a a reference to the vector, and moving that:

y_mut(Rc::new(RefCell::new(|f: Rc<RefCell<dyn FnMut(usize)>>| {
    let a = &mut a;
    move |i| {
        ...
    }
})))(0);

but then the closure no longer satisfies the 'static bound, as it now borrows something from its environment. You can work around that by using another Rc, and cloning it in the outer and the inner closure. This version of test code compiles:

fn main() {
    let a = Rc::new(RefCell::new(vec![0; 5]));
    let n = a.borrow().len();

    y_mut(Rc::new(RefCell::new({
        let a = Rc::clone(&a);
        move |f: Rc<RefCell<dyn FnMut(usize)>>| {
            let a = Rc::clone(&a);
            move |i| {
                if i < n {
                    a.borrow_mut()[i] = i;
                    f.borrow_mut()(i + 1);
                }
            }
        }
    })))(0);

    println!("a is {:?}", a.borrow());
}

Playground

Of course, doing it this way means that you don't need an FnMut to begin with, so the Y combinator implementation could be simplified back to the non-mut version you started off of.