Qual è il modo standard per ottimizzare la ricorsione reciproca in F #/Scala?

Question

Questi linguaggi non supportano l'ottimizzazione delle funzioni reciprocamente ricorsive in modo "nativo", quindi suppongo che debba essere trampolino o ... heh .. riscrivere come un loop) Mi manca qualcosa?

UPDATE: Sembra che ho mentito su FSharp, ma io proprio non ho visto un esempio di coda chiamate reciproche mentre googling

Answer 1

Prima di tutto, F # supporta le funzioni mutuamente ricorsive in modo nativo, perché può beneficiare dall'istruzione tailcall disponibile in .NET IL (MSDN). Tuttavia, questo è un po 'complicato e potrebbe non funzionare su alcune implementazioni alternative di .NET (ad esempio Compact Framework), quindi a volte potrebbe essere necessario gestirli manualmente.

In generale, che ci sono un paio di modi per trattare con esso:

• Trampolino - un'eccezione quando la profondità di ricorsione è troppo alto e mettere in atto un ciclo di livello superiore che maniglie l'eccezione (l'eccezione porterebbe informazioni per riprendere la chiamata). Invece di eccezioni, puoi anche semplicemente restituire un valore che specifica che la funzione dovrebbe essere richiamata di nuovo.

• Rilassatevi con timer - quando la profondità di ricorsione è troppo alto, si crea un timer e dargli un callback che verrà chiamata dal timer dopo un certo tempo molto breve (il timer continuerà la ricorsione, ma il lo stack usato verrà eliminato).

  La stessa cosa potrebbe essere eseguita utilizzando uno stack globale che memorizza il lavoro che deve essere eseguito. Invece di programmare un timer, si aggiungerà la funzione allo stack. Al livello più alto, il programma sceglieva le funzioni dallo stack e le eseguiva.

Per dare un esempio specifico della prima tecnica, in F # si potrebbe scrivere questo:

type Result<´T> = 
    | Done of ´T 
    | Call of (unit -> ´T) 

let rec factorial acc n = 
    if n = 0 then Done acc 
    else Call(fun() -> factorial (acc * n) (n + 1)) 

questo può essere utilizzato per le funzioni ricorsive reciprocamente pure. Il ciclo imperativo chiamerebbe semplicemente la funzione f memorizzata in Call(f) finché non produce Done con il risultato finale. Penso che questo sia probabilmente il modo più pulito per implementarlo.

Sono sicuro che ci sono altre tecniche sofisticate per affrontare questo problema, ma quelle sono le due che conosco (e che ho usato).

Answer 2

solo per avere il codice a portata di mano per quando Bing per F # mutua ricorsione:

let rec isOdd x = 
    if x = 1 then true else isEven (x-1) 
and isEven x = 
    if x = 0 then true else isOdd (x-1) 

printfn "%A" (isEven 10000000) 

Questo vi StackOverflow se si compila senza chiamate di coda (l'impostazione predefinita in modalità "Debug", che conserva le pile per facilitare il debug), ma funziona bene quando viene compilato con chiamate tail (il default nella modalità "Release"). Il compilatore esegue le chiamate tail per impostazione predefinita (vedere --tailcalls option) e le implementazioni .NET sulla maggior parte delle piattaforme lo rispettano.

Answer 3

Su Scala 2.8, scala.util.control.TailCalls:

import scala.util.control.TailCalls._ 

def isEven(xs: List[Int]): TailRec[Boolean] = if (xs.isEmpty) 
    done(true) 
    else 
    tailcall(isOdd(xs.tail)) 

def isOdd(xs: List[Int]): TailRec[Boolean] = if (xs.isEmpty) 
    done(false) 
    else 
    tailcall(isEven(xs.tail)) 

isEven((1 to 100000).toList).result