Wie vermeidet man Stapelüberlauf in diesem F # -Programm (rekursive Baumsuche)?

Question

Ich habe eine diskriminiert Vereinigungs-Baum wie diese bekommen:

type rbtree = 
    | LeafB of int 
    | LeafR of int 
    | Node of int*rbtree*rbtree 

Und was muss ich tun, ist für jeden LeafB in dem Baum zu suchen, so kam ich mit dieser rekursiven Funktion:

let rec searchB (tree:rbtree) : rbtree list = 
    match tree with 
    | LeafB(n) -> LeafB(n)::searchB tree 
    | LeafR(n) -> [] 
    | Node(n,left,right) -> List.append (searchB left) (searchB right) 

Aber wenn ich versuche, es zu testen, bekomme ich Stapelüberlauf Ausnahme und ich habe keine Ahnung, wie man es ändert, um richtig zu arbeiten.

Answer 1

Wie @ kvb sagt Ihre aktualisierte Version ist nicht wirklich Schwanz-rec und könnte auch einen Stackoverflow verursachen.

Was Sie tun können, ist die Verwendung von Fortsetzungen im Wesentlichen mit Heap-Space anstelle von Stack-Space.

let searchB_ tree = 
    let rec tail results continuation tree = 
    match tree with 
    | LeafB v   -> continuation (v::results) 
    | LeafR _   -> continuation results 
    | Node (_, lt, rt) -> tail results (fun leftResults -> tail leftResults continuation rt) lt 
    tail [] id tree |> List.rev 

Wenn wir auf den generierten Code in ILSpy sieht es sieht im Wesentlichen wie folgt aus:

internal static a tail@13<a>(FSharpList<int> results, FSharpFunc<FSharpList<int>, a> continuation, Program.rbtree tree) 
{ 
    while (true) 
    { 
    Program.rbtree rbtree = tree; 
    if (rbtree is Program.rbtree.LeafR) 
    { 
     goto IL_34; 
    } 
    if (!(rbtree is Program.rbtree.Node)) 
    { 
     break; 
    } 
    Program.rbtree.Node node = (Program.rbtree.Node)tree; 
    Program.rbtree rt = node.item3; 
    FSharpList<int> arg_5E_0 = results; 
    FSharpFunc<FSharpList<int>, a> arg_5C_0 = new Program<a>.tail@17-1(continuation, rt); 
    tree = node.item2; 
    continuation = arg_5C_0; 
    results = arg_5E_0; 
    } 
    Program.rbtree.LeafB leafB = (Program.rbtree.LeafB)tree; 
    int v = leafB.item; 
    return continuation.Invoke(FSharpList<int>.Cons(v, results)); 
    IL_34: 
    return continuation.Invoke(results); 
} 

So erwartet als mit Schwanz rekursive Funktionen in F # in eine while Schleife tranformed wird. Wenn wir die nicht-Schwanz rekursive Funktion aussehen:

// Program 
public static FSharpList<int> searchB(Program.rbtree tree) 
{ 
    if (tree is Program.rbtree.LeafR) 
    { 
    return FSharpList<int>.Empty; 
    } 
    if (!(tree is Program.rbtree.Node)) 
    { 
    Program.rbtree.LeafB leafB = (Program.rbtree.LeafB)tree; 
    return FSharpList<int>.Cons(leafB.item, FSharpList<int>.Empty); 
    } 
    Program.rbtree.Node node = (Program.rbtree.Node)tree; 
    Program.rbtree right = node.item3; 
    Program.rbtree left = node.item2; 
    return Operators.op_Append<int>(Program.searchB(left), Program.searchB(right)); 
} 

Wir sehen den rekursiven Aufruf am Ende der Funktion Operators.op_Append<int>(Program.searchB(left), Program.searchB(right));

So ist die Schwanz-rekursive Funktion Fortsetzungen Funktionen ordnet stattdessen einen neuen Stapelrahmen zu schaffen, . Wir können immer noch keinen Heap mehr haben, aber es gibt viel mehr Heap als Stack.

Voll Beispiel demonstriert eine Stackoverflow:

type rbtree = 
    | LeafB of int 
    | LeafR of int 
    | Node of int*rbtree*rbtree 

let rec searchB tree = 
    match tree with 
    | LeafB(n) -> n::[] 
    | LeafR(n) -> [] 
    | Node(n,left,right) -> List.append (searchB left) (searchB right) 

let searchB_ tree = 
    let rec tail results continuation tree = 
    match tree with 
    | LeafB v   -> continuation (v::results) 
    | LeafR _   -> continuation results 
    | Node (_, lt, rt) -> tail results (fun leftResults -> tail leftResults continuation rt) lt 
    tail [] id tree |> List.rev 

let rec genTree n = 
    let rec loop i t = 
    if i > 0 then 
     loop (i - 1) (Node (i, t, LeafB i)) 
    else 
     t 
    loop n (LeafB n) 

[<EntryPoint>] 
let main argv = 
    printfn "generate left leaning tree..." 
    let tree = genTree 100000 
    printfn "tail rec" 
    let s  = searchB_ tree 
    printfn "rec" 
    let f  = searchB tree 

    printfn "Is equal? %A" (f = s) 

    0 

Answer 2

Oh, könnte ich kam mit einer Lösung:

let rec searchB (tree:rbtree) : rbtree list = 
match tree with 
| LeafB(n) -> LeafB(n)::[] 
| LeafR(n) -> [] 
| Node(n,left,right) -> List.append (searchB left) (searchB right) 

Jetzt sieht es aus wie richtig funktioniert, wenn ich es versuchen.