Рекурсивная привязка F # в вычислительных выражениях и хвостовая рекурсивность

Я удалил части кода, которые, как мне казалось, не были необходимы для решения проблемы. Обратите внимание, что я также нахожу ваше 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.

Другой подход - реализовать паттерн-трамплин для обмена пространства стека на пространство кучи.