我试图理解如何在计算表达式中调用正确的递归函数,而不会得到堆栈溢出异常。据我所知,这是一个众所周知的问题,但仍然不能掌握的概念。也许有人能给出简单的解释或例子。
这是我的例子我希望跟踪生成器具有类似于seq
的行为,但不与seq monad一起工作,而是与其他一些人一起工作,例如option
,并从递归循环中仅返回最新的非None值。这可能吗?
这只是个例子,代码会无限运行但是不应该有stackowerflow异常
当我理解组合方法中的堆栈溢出问题时,代码只是保持调用f()函数在递归循环中,我想避免这种情况并使此调用尾递归,即代码应在常规循环中编译。
type TraceBuilder() =
member __.Bind (m: int Option, f: int -> int Option) : int Option =
match m with
| Some(v) -> f v
| None -> None
member this.Yield(x) = Some x
member this.YieldFrom(x) = x
member __.Delay(f) = f
member __.Run(f) = f()
member __.Combine (a, f) =
match a with
| Some _ -> a
| None -> f()
let trace = new TraceBuilder()
let rec iterRec (xopt: int Option) =
trace {
yield! None
let! x = xopt
yield! iterRec(Some(x + 1))
}
[<EntryPoint>]
let main argv =
let x = iterRec(Some(0))
//x = startFrom(0) |> Seq.take(5000) |> Seq.toList |> ignore
printfn "%A" x
认为comp. expression中的代码应该被编译
let iterRec xopt =
combine (None, (fun () ->
bind(xopt, fun x -> iterRec(Some(x+ 1)))
看起来在这种情况下,iterRec调用不是尾部递归,那么为什么stackoveflow,是可能实现这种逻辑尾部递归吗?
看了这些链接,还是想不出解决办法:
(如何)我可以使这个一元绑定尾递归?
这里建议如何使用FsControl库解决问题,但是否有可能使用正则计算表达式解决问题?
计算表达式中的递归函数
避免堆栈溢出(使用f#序列的无限序列)
https://fsharpforfunandprofit.com/posts/computation-expressions-builder-part5/我删除了我认为对这个问题不需要的部分代码。请注意,我也发现你的Combine
定义令人困惑。它可能很可爱,但它会把我完全扔掉,因为Combine
应该表现得类似于Bind
,因为两个操作被链接在一起。你的Combine
操作接近OrElse
操作。
:
module Trace =
let treturn a = Some a
let tbind a b =
match a with
| Some(v) -> b v
| None -> None
let (>>=) a b = tbind a b
open Trace
// Will throw on Debug (and most likely Mono)
let rec iterRec xopt l =
xopt >>= fun x -> if x < l then iterRec(Some(x + 1)) l else Some x
[<EntryPoint>]
let main argv =
let x = iterRec_(Some(0)) 100000
printfn "%A" x
0
iterRec
抛出StackOverflowException
在调试和抖动不识别.tail
属性。
通过查看iterRec
反汇编(以ILSpy
为例),更容易理解发生了什么
iterRec
=
public static FSharpOption<int> iterRec(FSharpOption<int> xopt, int l)
{
return Program.Trace.tbind<int, int>(xopt, new Program.iterRec@13(l));
}
internal class iterRec@13 : FSharpFunc<int, FSharpOption<int>>
{
public int l;
internal iterRec@13(int l)
{
this.l = l;
}
public override FSharpOption<int> Invoke(int x)
{
if (x < this.l)
{
return Program.iterRec(FSharpOption<int>.Some(x + 1), this.l);
}
return FSharpOption<int>.Some(x);
}
}
这两个函数是相互递归的,但是在Release
构建中,.tail
属性帮助Jitter避免堆栈增长。
当反汇编为IL
时,可以看到.tail
属性。
IL_0008: tail.
IL_000a: call class [FSharp.Core]Microsoft.FSharp.Core.FSharpOption`1<!!1> Program/Trace::tbind<int32, int32>(class [FSharp.Core]Microsoft.FSharp.Core.FSharpOption`1<!!0>, class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<!!0, class [FSharp.Core]Microsoft.FSharp.Core.FSharpOption`1<!!1>>)
不幸的是,并不是所有的Jitters都关心.tail
,这就是为什么我不愿意依赖它,并将iterRec
重写为F#
能够解包的尾部递归函数:
let rec iterRec_ xopt l =
// This F# unpacks into a while loop
let rec loop xo =
match xo with
| Some x -> if x < l then loop(Some(x + 1)) else xo
| None -> None
loop xopt
检查ILSpy
中的此功能:
internal static FSharpOption<int> loop@17(int l, FSharpOption<int> xo)
{
while (xo != null)
{
FSharpOption<int> fSharpOption = xo;
int x = fSharpOption.Value;
if (x >= l)
{
return xo;
}
int arg_1E_0 = l;
xo = FSharpOption<int>.Some(x + 1);
l = arg_1E_0;
}
return null;
}
不再递归,这个函数将在Debug
和mono
上执行得很好。
另一种方法是实现蹦床模式,将堆栈空间交换为堆空间。