Wie kann ich diese Funktion tail-rekursiv bekommen?

Question

Ich bin still versuchen, 2-3 Finger Bäume zu implementieren und ich machte gute Fortschritte (repository). Bei einigen Benchmarks fand ich heraus, dass mein recht einfaches toList in einem StackOverflowException resultiert, wenn der Baum ziemlich groß ist. Zuerst sah ich eine einfache Lösung und machte es tail-rekursiv.

Leider stellte sich heraus, dass toList nicht der Täter war aber viewr war:

/// Return both the right-most element and the remaining tree (lazily). 
let rec viewr<'a> : FingerTree<'a> -> View<'a> = function 
    | Empty -> Nil 
    | Single x -> View(x, lazyval Empty) 
    | Deep(prefix, deeper, One x) -> 
     let rest = lazy (
      match viewr deeper.Value with 
      | Nil -> 
       prefix |> Digit.promote 
      | View (node, lazyRest) -> 
       let suffix = node |> Node.toList |> Digit.ofList 
       Deep(prefix, lazyRest, suffix) 
     ) 
     View(x, rest) 
    | Deep(prefix, deeper, Digit.SplitLast(shorter, x)) -> 
     View(x, lazy Deep(prefix, deeper, shorter)) 
    | _ -> failwith Messages.patternMatchImpossible 

der Suche nach der einzigen rekursiven nennen es offensichtlich ist, dass dies nicht Schwanz-rekursiv. Irgendwie hoffte ich, dass dieses Problem nicht existieren würde, weil dieser Anruf in eine Lazy verpackt wird, die IMHO einer Fortsetzung ähnlich ist.

Ich hörte und las von Fortsetzungen, aber bis jetzt (nie) musste (d) sie benutzen. Ich denke, hier muss ich wirklich. Ich habe den Code ziemlich lange angeguckt, habe hier und da Funktionsparameter gesetzt und sie an anderen Orten aufgerufen ... Ich bin total verloren!

Wie kann das gemacht werden?

---

Update: Der Aufruf Code sieht wie folgt aus:

/// Convert a tree to a list (left to right). 
let toList tree = 
    let rec toList acc tree = 
     match viewr tree with 
     | Nil -> acc 
     | View(head, Lazy tail) -> tail |> toList (head::acc) 
    toList [] tree 

---

Update 2: Der Code, der den Absturz verursacht dieses ist.

let tree = seq {1..200000} |> ConcatDeque.ofSeq 
let back = tree |> ConcatDeque.toList 

Der Baum wird gut gebaut, ich habe überprüft und es ist nur 12 Ebenen tief. Es ist der Anruf in Zeile 2, der den Überlauf ausgelöst hat.

---

Update 3:kvb war richtig, dass pipe issue lief ich in zuvor hat etwas damit zu tun. Erneutes Testen des Cross-Produkts von Debug/Release und mit/ohne Pipe funktionierte es bis auf einen Fall: Der Debug-Modus mit dem Pipe-Operator stürzte ab. Das Verhalten war für 32 vs. 64 bit gleich.

Ich bin ziemlich sicher, dass ich Release-Modus ausgeführt habe, wenn Sie die Frage posten, aber heute funktioniert es. Vielleicht gab es noch einen anderen Faktor ... Tut mir leid.

---

Obwohl der Absturz gelöst ist, lasse ich die Frage aus theoretischem Interesse offen. Schließlich sind wir hier, um zu lernen, oder?

Lassen Sie mich die Frage anpassen:
Von Blick auf den Code, viewr definitiv nicht Schwanz-rekursiv ist. Warum explodiert es nicht immer und wie würde man es mit Fortsetzungen umschreiben?

Answer 1

Aufruf viewr nie führt zu einem sofortigen rekursiven Aufruf zu viewr (der rekursive Aufruf von lazy geschützt ist und nicht im Rest des Anrufs viewr gezwungen), so gibt es keine Notwendigkeit, es Schwanz rekursive zu machen das zu verhindern, Stapel von wachsen ohne gebunden.Das heißt, ein Anruf an viewr erstellt einen neuen Stapelrahmen, der dann sofort wieder geöffnet wird, wenn viewr seine Arbeit erledigt ist; Der Aufrufer kann dann den Lazy-Wert erzwingen, der zu einem neuen Stack-Frame für den verschachtelten viewr-Aufruf führt, der dann sofort erneut aufgerufen wird, usw., sodass das Wiederholen dieses Prozesses nicht zu einem Stack-Überlauf führt.