Ist es möglich, eine rekursive Schließung in Rust?

Dies ist ein sehr einfaches Beispiel, aber wie kann ich etwas tun, ähnlich:

let fact = |x: u32| {
    match x {
        0 => 1,
        _ => x * fact(x - 1),
    }
};

Ich weiß, dass dieses spezielle Beispiel kann leicht getan werden mit iteration, aber ich Frage mich, ob es möglich ist, eine rekursive Funktion in Rust für kompliziertere Dinge (wie die Traversierung von Bäumen) oder wenn ich benötigt, um meine eigenen stack statt.

  • Niko Matsakis schrieb ein wunderbarer post darüber, wie Sie potenziell (ab)Rekursion bei Verschlüssen gerade jetzt und warum diese sicherlich entfernt werden (wenn es nicht bereits in incoming). Natürlich können Sie eine Funktion definieren, die sich selbst aufruft, aber Sie nicht zu erfassen äußeren Variablen.
InformationsquelleAutor Undeterminant | 2013-06-05
  1. 28

    Gibt es ein paar Möglichkeiten, dies zu tun.

    Können Sie bringen Verschlüsse in ein struct und übergeben Sie diese Struktur, um die Schließung. Sie können sogar definieren, Strukturen inline-Funktion:

    fn main() {
    struct Fact<'s> { f: &'s 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));
}

    Diese umgeht das problem der unendlich-Typ (eine Funktion, die sich als argument) und das problem, dass fact ist noch nicht definiert innerhalb der Schließung sich, wenn man schreibt let fact = |x| {...} und so kann man nicht finden ihn dort.

    Diese Werke in Rust 1.17, aber möglicherweise illegal in der Zukunft, da es gefährlich ist, in einigen Fällen, wie beschrieben in der blog-post Der Fall der immer Wiederkehrenden Verschluss. Es ist ganz sicher hier, da es keine mutation jedoch.

    Weitere option ist es, nur schreiben Sie eine rekursive Funktion als eine fn Sache, die auch inline definiert in einer Funktion:

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

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

    Dies funktioniert gut, wenn Sie nicht brauchen, um zu erfassen, dass alles von der Umwelt.

    Eine weitere Möglichkeit ist die Verwendung des fn Element-Lösung, sondern explizit übergeben args/Umgebung Sie wollen.

    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));
}

    Alle diese arbeiten mit Rost 1.17 haben und wahrscheinlich arbeitete seit der version 0.6. Die fn's definiert, innerhalb fns nicht anders definiert, auf der obersten Ebene, außer Sie sind nur zugänglich innerhalb der fn Sie sind definiert im inneren.

    • Ist es tatsächlich der Fall, dass diese verboten werden in der Zukunft? Soweit ich sagen kann, das ist sicher, denn wir arbeiten mit Fn wir haben also keine Mutationen aliasing, und wenn Sie versucht etwas zu schreiben, die rekursiv mit FnMut ausleihen checker würden sich beschweren, weil der mehrere leiht der &mut FnMut() Referenz. Dass blog-post geschrieben wurde gegen eine sehr alte version von Rust, und wie es aussieht ist es gelöst durch die neueren Fn/FnMut/FnOnce Züge, wo früher &fn war tatsächlich veränderlich.
    InformationsquelleAutor huon
  2. 1

    Hier ist wirklich hässlich und die ausführliche Lösung, die ich kam mit:

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

    Die Vorteile dieser sind, rufen Sie die Funktion mit der erwarteten Signatur (keine zusätzlichen Argumente benötigt werden), es ist eine closure, die Erfassung von Variablen (durch Umzug), ist es nicht erforderlich die Festlegung von neuen Strukturen und der Verschluss kann von der Funktion zurückgegeben werden oder anderweitig an einem Ort gespeichert, der überlebt den Bereich, wo es erstellt wurde (als Rc<Fn...>) und es funktioniert immer noch.

    InformationsquelleAutor newacct
Schreibe einen Kommentar