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

Question

Estos lenguajes no son compatibles con funciones mutuamente recursivas optimización 'nativa', así que supongo que debe ser el trampolín o .. je .. volver a escribir como un bucle) Do Me he perdido algo?

ACTUALIZACIÓN: Parece que lo hice mentira sobre FSharp, pero simplemente no vio un ejemplo de cola-llamadas mutuos, mientras que buscando en Google

Answer 1

En primer lugar, F # admite funciones mutuamente recursivas de forma nativa, ya que pueden beneficiarse de la instrucción tailcall que está disponible en el .NET IL ( MSDN ). Sin embargo, esto es un poco complicado y puede no funcionar en algunas implementaciones alternativas de .NET (por ejemplo compactos Marcos), por lo que a veces puede que tenga que hacer frente a 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 controla la excepción (la excepción sería llevar la información para reanudar la llamada). En lugar de excepción también puede simplemente devolver un valor que especifica que la función debe ser llamada de nuevo.

• 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 recursión, pero la pila usada será dado de baja).

  Lo mismo podría hacerse utilizando una pila global que almacena el trabajo que hay que hacer más. En lugar de programar un temporizador, debería añadir la función a la pila. En el nivel superior, el programa recogería las funciones de la pila y ejecutarlos.

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 recursivos también. El bucle imperativo simplemente llamar a la función f almacenada en Call(f) hasta que se produce 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 hacer frente a este problema, pero esos son los dos que sé sobre (y que he usado).

Answer 2

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

Answer 3

Sólo para tener el código a mano 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 corre muy bien cuando se compila con las llamadas de cola (por defecto en el modo de "Release"). El compilador hace llamadas de cola por defecto (véase el --tailcalls opción ) y .NET implementaciones en la mayoría de las plataformas de honor.