Überlauf Stapel beim Zusammenstellen von vielen Funktionen

Question

Hier ist eine Möglichkeit, einen binären Suchbaum flach zu machen. Sein Problem besteht darin, dass der Stapel überläuft, wenn die große Funktion, die er erstellt, schließlich auf [] angewendet wird. Ich würde gerne wissen, ob es einen vernünftigen Weg gibt, dieses Codefragment zu reparieren, ohne es komplett zu verändern. Zum Beispiel wäre es nicht hilfreich, einen benutzerdefinierten Composer zu erstellen, der eine Baumstruktur von Funktionen erstellt, und diese dann mithilfe eines expliziten Stacks auswertet (da das Problem bereits darin besteht, eine Struktur zu reduzieren).

let flatten_k t = 

    let rec f t (k:(list<'a>->list<'a>)->list<'a>) = 
     match t with 
     | Leaf -> 
      k (fun xs -> xs) 

     | Bin (l,x,r) -> 
      f l (fun fl -> f r (fun fr -> k (fl << (fun xs -> x::xs) << fr))) 

    f t (fun g -> g []) 

Es kann sein, dass es besser ist, über ein vereinfachtes Beispiel zu denken, obwohl es schwieriger sein kann, auf eine Lösung, um überzeugend darlegt (da es nichts tut, nahe an, obwohl es zumindest die Funktion Zusammensetzung überläuft zeigt der Stapel):

let test_composition() = 
    let mutable f = id 
    for i=0 to 1000000 do 
     f <- id << f // >> works fine for me 
    printf "Functions return %d" (f 123) 

Noch einmal, diese Frage geht nicht darum, wie man einen Baum flacht. Ich kann das leicht tun, wie folgt oder in irgendeiner Anzahl von rein zwingenden Mitteln. Ich möchte wissen, ob ein auf dem Akkumulieren einer großen Funktion basierender Ansatz für dieses spezielle Problem durchführbar gemacht werden kann. Danke vielmals.

let flatten t = 

    let rec f t acc cont = 
     match t with 
     | Leaf -> 
      cont acc 

     | Bin (l, x, r) -> 
      f r acc (fun rs -> f l (x::rs) cont) 

    f t [] id 

Answer 1

Ihr Baum Funktion Abflachung ist nicht Schwanz rekursiv.

Die Zusammensetzung der Funktionen ist nicht tail rekursiv. Dies ist leicht durch Entfalten Sie Ihre dreifache Zusammensetzung, um zu sehen:

original:    fl << cons << fr 
unfold compositions: fun a -> fl (cons (fr a)) 
unfold nested calls: fun a -> 
          let x = fr a 
          let y = cons x 
          fl y 

Wie Sie sehen können, ist diese Funktion ruft zuerst fr und dann etwas tut, nicht-trivial mit seinem Ergebnis. Der letzte Aufruf an fl ist Tail-rekursiv, aber die vorherigen zwei sind nicht. Die Rücksprungadresse muss auf dem Stapel gehalten werden, während fr und cons ausgeführt werden.

Dies ist keine Tail-Rekursion. Bei der Tail-Rekursion wird das Ergebnis des letzten Aufrufs an den Aufrufer übergeben. Dieses Ergebnis an eine weitere Funktion als Argument übergeben - das ist eine ganz andere Sache.

Wie Sie es beheben können - Sie können nicht, wenn Sie darauf bestehen, Funktion Zusammensetzung verwenden. Und wenn Sie nicht darauf bestehen - dann haben Sie bereits eine Lösung.

Soweit Ihr künstliches Beispiel - Ich denke, es scheitert, weil Sie es in FSI oder so ähnlich laufen. Ich habe es gerade jetzt verifiziert:

• Wenn Sie es normalerweise kompilieren, funktioniert es gut.
• Wenn Sie Optimierungen deaktivieren, schlägt der Stack-Überlauf fehl.
• Wenn Sie id durch einige nicht-tail-rekursive Funktion ersetzen (z. B. fun x -> x+1), schlägt es auch fehl.