Можно ли сделать рекурсивное закрытие в Rust?

Ответ 1

Есть несколько способов сделать это.

Вы можете поместить замыкания в структуру и передать эту структуру замыканию. Вы даже можете определить структуры, встроенные в функцию:

fn main() {
    struct Fact<'s> { f: & Fn(&Fact, u32) -> u32 }
    let fact = Fact {
        f: &|fact, x| if x == 0 {1} else {x * (fact.f)(fact, x - 1)}
    };

    println!("{}", (fact.f)(&fact, 5));
}

Это позволяет обойти проблему наличия бесконечного типа (функция, которая принимает себя в качестве аргумента) и проблему, заключающуюся в том, что fact еще не определен внутри самого замыкания, когда кто-то пишет let fact = |x| {...} let fact = |x| {...} и поэтому там нельзя ссылаться на это.

Это работает в Rust 1.17, но, возможно, в будущем станет незаконным, поскольку в некоторых случаях это опасно, как об этом говорится в сообщении в блоге "Случай повторяющегося закрытия". Здесь совершенно безопасно, поскольку мутации нет.

Другой вариант - просто написать рекурсивную функцию как элемент fn, который также может быть определен внутри функции:

fn main() {
    fn fact(x: u32) -> u32 { if x == 0 {1} else {x * fact(x - 1)} }

    println!("{}", fact(5));
}

Это прекрасно работает, если вам не нужно захватывать что-либо из окружающей среды.

Еще один вариант - использовать решение fn item, но явно передать нужные аргументы args/environment.

fn main() {
    struct FactEnv { base_case: u32 }
    fn fact(env: &FactEnv, x: u32) -> u32 {
        if x == 0 {env.base_case} else {x * fact(env, x - 1)}
    }

    let env =  FactEnv { base_case: 1 };
    println!("{}", fact(&env, 5));
}

Все они работают с Rust 1.17 и, вероятно, работали с версии 0.6. Значения fn определенные внутри fn, не отличаются от тех, которые определены на верхнем уровне, за исключением того, что они доступны только в пределах fn они определены.

Ответ 2

Вот действительно уродливое и многословное решение, которое я придумал:

use std::{
    cell::RefCell,
    rc::{Rc, Weak},
};

fn main() {
    let weak_holder: Rc<RefCell<Weak<dyn Fn(u32) -> u32>>> =
        Rc::new(RefCell::new(Weak::<fn(u32) -> u32>::new()));
    let weak_holder2 = weak_holder.clone();
    let fact: Rc<dyn Fn(u32) -> u32> = Rc::new(move |x| {
        let fact = weak_holder2.borrow().upgrade().unwrap();
        if x == 0 {
            1
        } else {
            x * fact(x - 1)
        }
    });
    weak_holder.replace(Rc::downgrade(&fact));

    println!("{}", fact(5)); // prints "120"
    println!("{}", fact(6)); // prints "720"
}

Преимущества этого состоят в том, что вы вызываете функцию с ожидаемой сигнатурой (дополнительные аргументы не требуются), это замыкание, которое может захватывать переменные (путем перемещения), оно не требует определения каких-либо новых структур, и закрытие может быть возвращено из функции или иным образом сохранено в месте, которое переживает область, в которой оно было создано (как Rc<Fn...>), и оно все еще работает.