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

Question

Queste lingue non supporta le funzioni reciprocamente ricorsivo ottimizzazione 'nativo', quindi credo che deve essere trampolino o .. eh .. riscrivere come un loop) mi manca qualcosa?

UPDATE: Sembra che ho menzogna FSharp, ma semplicemente non vedere un esempio di coda chiamate reciproche mentre googling

Answer 1

Prima di tutto, F # supporta funzioni ricorsive reciprocamente in modo nativo, perché può beneficiare dell'istruzione tailcall che è 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 affrontare questo a mano.

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

• Trampolino - un'eccezione quando la profondità di ricorsione è troppo alto e implementare un ciclo di livello superiore che gestisce l'eccezione (l'eccezione porterebbe informazioni per riprendere la chiamata). Invece di eccezione si può anche semplicemente restituire un valore che specifica che la funzione deve essere chiamato 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 continuare la ricorsione, ma lo stack utilizzato verrà abbandonato).

  La stessa cosa potrebbe essere fatto utilizzando una pila globale che memorizza il lavoro che deve essere fatto. Invece di pianificazione di un timer, è necessario aggiungere la funzione alla pila. Al livello superiore, il programma avrebbe scelto funzioni dalla pila ed eseguirli.

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 funzioni mutuamente ricorsive pure. Il ciclo imperativo potrebbe semplicemente chiamare la funzione f memorizzato in Call(f) fino a produrre Done del risultato finale. Penso che questo è probabilmente il modo più pulito per implementare questa.

Sono sicuro che ci sono altre tecniche sofisticate per affrontare questo problema, ma questi sono i due che so di (e che ho usato).

Answer 2

In 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

Answer 3

Proprio 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 StackOverflow se si compila senza chiamate di coda (l'impostazione predefinita in modalità "Debug", che conserva le pile per facilitare il debug), ma esegue bene quando si compila con le chiamate di coda (l'impostazione predefinita in modalità "uscita"). Il compilatore fa chiamate coda di default (vedere la --tailcalls opzione ) e .NET implementazioni sulla maggior parte delle piattaforme di onorarlo.