f# - recursivas - recursividad de cola ejemplos

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

Question

Escribí la siguiente función:

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 compilador de F # lo convirtió en un ciclo? ¿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 el bucle resida?

Además, ¿existe una función en F # std lib para ejecutar una función dada varias veces, cada vez dándole 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 ...

Answer 1

Desafortunadamente no hay una 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 la gente adivina y cometer errores. No hay una forma automatizada simple (aparte de, por ejemplo, inspeccionar el código generado).

Por supuesto, puedes probar tu función en una gran parte de los datos de prueba y ver si 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 usa para cuando se quiere mantener las estructuras de pila para la depuración), con la excepción de que las funciones directamente recursivas 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 recibe una advertencia / error si no es 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í hay un ejemplo de código de lo que preguntaste:

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

Answer 2

Me gusta la regla empírica que Paul Graham formula en On Lisp : si queda trabajo por hacer , por ejemplo, manipular la salida de llamada recursiva, entonces la llamada no es recursiva de cola.