¿Cuál es la forma estándar de optimizar la recursión mutua en F #/Scala?

Question

Estos lenguajes no son compatibles con la optimización mutuamente recursiva de funciones 'nativamente', así que supongo que debe ser trampolín o ... heh ... reescribiendo como un bucle) ¿Extraño algo?

ACTUALIZACIÓN: Parece que me he mentido acerca de FSharp, pero simplemente no vi un ejemplo de cola-llamadas mutuos, mientras que buscando en Google

Answer 1

En primer lugar, F # soporta funciones mutuamente recursivas de forma nativa, ya que puede beneficiarse de la instrucción tailcall que está disponible en .NET IL (MSDN). Sin embargo, esto es un poco complicado y puede no funcionar en algunas implementaciones alternativas de .NET (por ejemplo, Frameworks compactos), por lo que a veces puede necesitar lidiar con esto a mano.

En general, lo que hay un par de maneras de tratar con él:

• Trampolín - una excepción cuando el nivel de recursividad es demasiado alto e implementar un bucle de nivel superior que las manijas la excepción (la excepción llevaría información para reanudar la llamada). En lugar de una excepción, también puede devolver un valor que especifique que se debe llamar nuevamente a la función.

• desenrolla mediante temporizador - cuando el nivel de recursividad es demasiado alto, se crea un temporizador y darle una devolución de llamada que será llamado por el temporizador después de un tiempo muy corto (el temporizador continuará la recursividad, pero el la pila usada se eliminará).

  Lo mismo podría hacerse utilizando una pila global que almacena el trabajo que debe hacerse. En lugar de programar un temporizador, agregaría función a la pila. En el nivel superior, el programa elegiría funciones de la pila y las ejecutaría.

Para dar un ejemplo específico de la primera técnica, en Fa # podría escribir esto:

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

Esto puede ser usado para funciones mutuamente recursivas también. El ciclo imperativo simplemente llamaría a la función f almacenada en Call(f) hasta que produzca Done con el resultado final. Creo que esta es probablemente la forma más limpia de implementar esto.

Estoy seguro de que hay otras técnicas sofisticadas para manejar este problema, pero esas son las dos que conozco (y que yo utilicé).

Answer 2

sólo para tener a mano el código para cuando Bing para F # recursión mutua:

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) 

Esto Stackoverflow si compila sin llamadas de cola (el valor por defecto en el modo de "depuración", que preserva las pilas para la depuración más fácil), pero funciona bien cuando se compila con llamadas finales (el valor predeterminado en el modo "Versión"). El compilador realiza llamadas de forma predeterminada (consulte --tailcalls option), y las implementaciones de .NET en la mayoría de las plataformas lo respetan.

Answer 3

En 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