Was ist der normale Weg gegenseitige Rekursion in F # / Scala zu optimieren?

Question

Diese Sprachen nicht gegenseitig rekursive Funktionen Optimierung unterstützen ‚nativ‘, so dass ich denke, es Trampolin oder sein muss .. heh .. Umschreiben als Loop) Muss ich etwas verpasst?

UPDATE: Es scheint, dass ich es tat Lüge über FSharp, aber ich habe gerade kein Beispiel der gegenseitigen tail-Anrufe sehen, während Googeln

Answer 1

Zu allererst F # unterstützt sich gegenseitig rekursive Funktionen nativ, weil es von der tailcall Anweisung profitieren, die in .NET IL verfügbar ist ( MSDN ). Dies ist jedoch ein bisschen schwierig ist und möglicherweise nicht auf einigen alternativen Implementierungen von .NET (zum Beispiel Compact Frameworks), so dass man manchmal mit diesem von Hand beschäftigen muß.

Generell ich, dass es ein paar Möglichkeiten, damit umzugehen:

• Trampoline - eine Ausnahme aus, wenn die Rekursionstiefe zu hoch sind und implementieren eine Top-Level-Schleife, dass Griffe der Ausnahme (Ausnahme Information tragen würde das Gespräch wieder aufzunehmen). Statt Ausnahme können Sie auch einfach einen Wert zurückgeben Angabe, dass die Funktion sollte wieder aufgerufen werden.

• Unwind mit Timer - wenn die Rekursionstiefe zu hoch ist, erstellen Sie einen Timer und geben ihm einen Rückruf, der durch den Timer nach einiger sehr kurzer Zeit (der Timer aufgerufen wird wird weiterhin die Rekursion, aber der verwendete Stapel wird fallen gelassen werden).

  Das Gleiche getan werden könnte, einen globalen Stapel dass speichert die Arbeit mit, dass getan werden muss. Anstatt einen Timer planen, würden Sie Funktion zum Stapel hinzufügen. Auf der obersten Ebene, würde das Programm Funktionen vom Stapel holen und sie läuft.

Um ein konkretes Beispiel für die erste Technik zu geben, in F # Sie können schreiben:

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

Dies kann auch für beide Seiten rekursiven Funktionen verwendet werden. Der Imperativ Schleife würde rufen Sie einfach die f Funktion in Call(f) gespeichert, bis sie Done mit dem Endergebnis erzeugt. Ich denke, das ist wahrscheinlich der sauberste Weg, dies zu realisieren.

Ich bin sicher, es gibt andere anspruchsvolle Techniken für Umgang mit diesem Problem, aber das sind die beiden kenne ich (und ich verwendet).

Answer 2

Auf 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

Sie einfach den Code praktisch haben, wenn Sie Bing nach F # gegenseitige Rekursion:

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)

Dies wird Stackoverflow, wenn Sie ohne Endrekursion (Standardeinstellung in „Debug“ -Modus, der Stapel für eine einfachere Fehlersuche bewahrt) kompilieren, aber nur gut laufen, wenn sie mit Endrekursion (die Standardeinstellung in „Release“ Modus) erstellt. Der Compiler tut Endrekursion standardmäßig (siehe --tailcalls Option ) und .NET-Implementierungen auf den meisten Plattformen ehren.