Quelle est la méthode standard pour optimiser récursion mutuelle en F # / Scala?

Question

Ces langues ne supportent pas l'optimisation des fonctions mutuellement récursive « nativement », donc je suppose qu'il doit être trampoline ou .. heh .. réécriture en boucle) Ai-je raté quelque chose?

Mise à jour: Il semble que je l'ai fait mentir au sujet de FSharp, mais je ne vois pas un exemple de queue des appels communs tout en googler

Answer 1

Tout d'abord, F # prend en charge les fonctions mutuellement récursives nativement, car il peut bénéficier de l'instruction de tailcall qui est disponible dans l'IL .NET ( MSDN ). Cependant, cela est un peu délicat et peut ne pas fonctionner sur certaines implémentations alternatives de .NET (par exemple des cadres compacts), de sorte que vous devrez peut-être parfois face à cette main.

En général, je qu'il ya deux façons d'y faire face:

• Trampoline - jeter une exception lorsque la profondeur de récursivité est trop élevée et mettre en œuvre une boucle de niveau supérieur qui gère l'exception (l'exception effectuerait des informations pour reprendre l'appel). Au lieu d'exception, vous pouvez également revenir simplement une valeur indiquant que la fonction doit être appelée à nouveau.

• Déroulez utilisant timer - lorsque la profondeur de récursivité est trop élevée, vous créez une minuterie et lui donner un rappel qui sera appelé par la minuterie après un certain temps très court (la minuterie poursuivre la récursion, mais la pile utilisée sera supprimée).

  La même chose pourrait être fait à l'aide d'une pile globale qui stocke le travail à faire. Au lieu de programmer une minuterie, vous devez ajouter la fonction à la pile. Au plus haut niveau, le programme choisirait les fonctions de la pile et de les exécuter.

Pour donner un exemple spécifique de la première technique, en F # vous pouvez écrire ceci:

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

Ceci peut être utilisé pour des fonctions mutuellement récursives ainsi. La boucle impératif serait simplement appeler la fonction f stockée dans Call(f) jusqu'à ce qu'il produit Done avec le résultat final. Je pense que cela est probablement la façon la plus propre à mettre en œuvre.

Je suis sûr qu'il ya d'autres techniques sophistiquées pour faire face à ce problème, mais ce sont les deux que je connais (et que je).

Answer 2

Le 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

Juste pour avoir le code pratique lorsque vous Bing pour F # récursion mutuelle:

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)

Ceci StackOverflow si vous compilez sans appel de queue (la valeur par défaut en mode « Mise au point », qui conserve des piles pour le débogage plus facile), mais exécuter très bien lorsqu'il est compilé avec appels de la queue (par défaut en mode « Release »). Le compilateur fait des appels de la queue par défaut (voir l'option --tailcalls ) , et les implémentations .NET sur la plupart des plates-formes honorent.