Liaison r # recursive dans les expressions de calcul et la récursivité de queue

Question

J'essaie de comprendre comment appeler des fonctions correctement récursives dans des expressions de calcul et ne pas obtenir d'exception de dépassement de pile. Si je comprends bien ce problème est connu, mais ne peut toujours pas saisir le concept. Peut-être que quelqu'un a des explications ou des exemples simples pour cela.

Voici mon exemple je veux constructeur tracer ont un comportement similaire à seq mais ne fonctionne pas avec seq monade au lieu d'une autre, par exemple option et le retour ne dernière valeur non Aucun de la boucle récursive. C'est possible ?

Ceci est par exemple juste, le code fonctionnera à l'infini, mais il est ne devrait pas être exception stackowerflow

Si je comprends un problème de débordement de pile dans Combiner la méthode, le code juste continuer à appeler la fonction f() dans la boucle récursive, et je veux éviter ceci et rendre cette queue d'invocation récursive, ie le code devrait être compilé en boucle régulière.

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 

Code de réflexion dans comp. expression doit est compilé

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

Et ressemble dans ce cas d'invocation iterRec est pas récursive queue, ce qui est donc pourquoi stackoveflow, est-il possible de mettre en œuvre cette récursive de queue logique?

Lisez ces liens, ne peut toujours pas comprendre la solution:

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

Voici la suggestion comment résoudre le problème en utilisant FsControl lib, mais est-il possible de résoudre le problème en utilisant des expressions régulières de calcul?

Recursive functions in computation expressions

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

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

Answer 1

J'ai enlevé les parties du code que je ressentais était pas nécessaire pour la question. Notez que je trouve également votre définition Combine confuse. Il pourrait être mignon, mais il me jetterait complètement comme Combine devrait se comporter de manière similaire à Bind en ce que deux opérations sont enchaînées ensemble. L'opération Combine est proche de ce qui est normalement une opération OrElse.

Quoi qu'il en soit:

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 lancers francs StackOverflowException dans Debug et la frousse qui ne reconnaît pas l'attribut .tail.

Il est un peu plus facile de comprendre ce qui se passe en regardant iterRec démontées (en utilisant ILSpy pour instance`)

iterRec est égal à:

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); 
    } 
} 

Les deux fonctions sont mutuellement récursive mais Release builds l'attribut .tail aide la gigue à éviter de développer la pile. On voit l'attribut .tail lors du démontage à IL.

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>>) 

Malheureusement, tous les Jitters se soucient de .tail ce qui explique pourquoi je suis hesistant compter sur elle et réécrivaient iterRec à une fonction récursive de queue qui F# est capable de décompresser:

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 

Si vous cochez cette fonction en 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; 
} 

Non plus cette fonction récursive exécutera bien sur Debug Jitters ainsi que mono.

Une autre approche consiste à implémenter un modèle de trampoline pour échanger l'espace de pile pour l'espace de tas.