¿Cómo puedo saber si una función es recursiva cola en Fa #

me escribió la función siguientes aparatos:¿Cómo puedo saber si una función es recursiva cola en Fa #

let str2lst str = 
    let rec f s acc = 
     match s with 
     | "" -> acc 
     | _ -> f (s.Substring 1) (s.[0]::acc) 
    f str []

¿Cómo puedo saber si el F # compilador lo convirtió en un bucle? ¿Hay alguna manera de averiguarlo sin usar Reflector (no tengo experiencia con Reflector y no sé C#)?

Editar: Además, ¿es posible escribir una función recursiva de cola sin usar una función interna, o es necesario que resida el bucle?

Además, ¿existe una función en F # std lib para ejecutar una función determinada varias veces, dando cada vez el último resultado como entrada? Digamos que tengo una cadena, quiero ejecutar una función sobre la cadena y luego ejecutarla de nuevo sobre la cadena resultante y así sucesivamente ...

Fuente

2009-04-30 Dave Berk

Véase también http://stackoverflow.com/questions/5809683/is-my-rec-function-tail-recursive – Brian

Lamentablemente, no hay manera trivial.

No es demasiado difícil leer el código fuente y usar los tipos y determinar si algo es una llamada final por inspección (¿es 'lo último' y no en un bloque 'probar'), pero las personas son -explican y cometen errores. No hay una forma automatizada simple (que no sea, por ejemplo, inspeccionar el código generado).

Por supuesto, puede simplemente probar su función en una gran pieza de datos de prueba y ver si esta explota o no.

El compilador F # generará instrucciones .tail IL para todas las llamadas finales (a menos que se utilice el compilador para desactivarlas, se utiliza para cuando quiere mantener los marcos de pila para la depuración), con la excepción de que directamente recursivo las funciones se optimizarán en bucles. (EDITAR: Creo que hoy en día el compilador F # tampoco puede emitir .tail en los casos en que puede demostrar que no hay bucles recursivos a través de este sitio de llamada, esta es una optimización dado que el código de operación .tail es un poco más lento en muchas plataformas).

'tailcall' es una palabra clave reservada, con la idea de que una versión futura de F # puede permitirle escribir, por ejemplo

tailcall func args

y luego aparece una advertencia/error si no se trata de una llamada de cola.

Solo las funciones que no son naturalmente recursivas de cola (y por lo tanto necesitan un parámetro de acumulador adicional) lo "forzarán" a entrar en la expresión de "función interna".

Aquí está un ejemplo de código de lo que has pedido:

let rec nTimes n f x = 
    if n = 0 then 
     x 
    else 
     nTimes (n-1) f (f x) 

let r = nTimes 3 (fun s -> s^" is a rose") "A rose" 
printfn "%s" r

Fuente

2009-04-30 13:23:42 Brian

"tailcall" es interesante, ya que le permite especificar el sitio de llamada en lugar de lo que puede ser un más útil declaración "tailrec" en toda la función. ¿Puedes tener una función "parcialmente recursiva de la cola"? –

@StephenSwensen Usted absolutamente puede. Las ramas de flujo de control podrían conducir a una alternativa entre una llamada de cola y una llamada que no es una llamada de cola, y es posible que solo desee verificar la que realmente es una llamada de cola en tiempo de compilación. 'let rec f x = si x> 0 luego f (1 + x) else 0 + f (1 + x)' ilustra el concepto, aunque obviamente no terminaría. –

Me gusta la regla de oro Paul Graham formula en En Lisp: si hay trabajo por hacer, por ejemplo, manipulando la salida de llamada recursiva, entonces la llamada no es recursiva de cola.

Fuente

2012-04-17 11:48:44 vemv

¿Cómo puedo saber si una función es recursiva cola en Fa #

Respuesta

Cuestiones relacionadas