我有一个这样的可区分联合树:
type rbtree =
| LeafB of int
| LeafR of int
| Node of int*rbtree*rbtree
我要做的是搜索树中存在的每个 LeafB,所以我使用了这个递归函数:
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)
但是当我尝试测试它时,我得到了堆栈溢出异常,我不知道如何修改它才能正常工作。
最佳答案
正如@kvb 所说,您的更新版本并不是真正的尾部记录,也可能导致计算器溢出。
您可以做的是使用 continuations,本质上是使用堆空间而不是堆栈空间。
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
如果我们查看 ILSpy
中生成的代码它看起来基本上是这样的:
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);
}
因此,正如 F# 中的尾递归函数所预期的那样,它被转换为 while
。环形。如果我们看一下非尾递归函数:
// 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));
}
我们在函数末尾看到递归调用Operators.op_Append<int>(Program.searchB(left), Program.searchB(right));
所以尾递归函数分配延续函数而不是创建新的栈帧。我们仍然可以用完堆,但堆比堆栈多得多。
演示 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
关于f# - 如何避免此 F# 程序中的堆栈溢出(递归树搜索)?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42162649/