F＃递归绑定计算表达式和尾递归

我试图理解如何在计算表达式中调用正确的递归函数，并且不会发生堆栈溢出异常。 据我了解这是相当知名的问题，但仍然无法把握这个概念。 也许有人对此有简单的解释或例子。

在这里，我想要的跟踪生成器的示例具有类似于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。 表达式应该被编译

let iterRec xopt = 
    combine (None, (fun () ->
              bind(xopt, fun x -> iterRec(Some(x+ 1)))

看起来在这种情况下，iterRec调用不是尾递归，所以为什么stackoveflow，是否有可能实现这个逻辑尾递归？

阅读这些链接，仍然无法弄清楚解决方案：

（如何）我可以使这个monadic绑定尾递归？

这里建议如何使用FsControl lib解决问题，但是否可以使用常规计算表达式来解决问题？

计算表达式中的递归函数

避免堆栈溢出（使用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 ）来了解发生的事情会更容易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>>)

不幸的是，并不是所有的.tail都关心.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上都能正常执行。

另一种方法是实现蹦床模式来为堆空间交换堆栈空间。

链接地址: http://www.djcxy.com/p/80535.html

上一篇: F# recursive bind in computational expressions and tail recursiveness

下一篇: F# performance difference between tail recursion and Seq library