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

Question

Я пытаюсь понять, как вызывать правильные рекурсивные функции в вычислительных выражениях и не получать исключение переполнения стека. Насколько я понимаю, это довольно известная проблема, но до сих пор не может понять концепцию. Может быть, у кого-то есть простые объяснения или примеры для этого.

Вот мой пример я хочу проследить строитель есть поведение, аналогичное seq но не работает с SEQ монады вместо с каким-то другим, например 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 

Мышление кода в соц. Выражение должно компилируется

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

И похоже, в этом случае iterRec вызова не хвостовая рекурсия, так почему, Что stackoveflow, можно реализовать эту логику хвостовая рекурсия?

Прочитайте эти ссылки, до сих пор не могу понять решение:

(How) can I make this monadic bind tail-recursive?

Вот предложение, как решить проблему с помощью FsControl LIB, но это можно решить проблему с помощью регулярных выражений вычислений?

Recursive functions in computation expressions

Avoiding stack overflow (with F# infinite sequences of sequences)

https://fsharpforfunandprofit.com/posts/computation-expressions-builder-part5/

Answer 1

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

Это немного легче понять, что происходит, глядя на iterRec разобранном (с использованием ILSpy для instance`)

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 помогает дрожанию избежать роста стека.

При разборке 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 поэтому я hesistant полагаться на него, и переписывал 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 Jitters, а также mono.

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