While o Tail Recursion in F#, ¿qué usar cuando?

functional-programming while-loop

Question

Ok, solo en F # y así es como lo entiendo ahora:

• Algunos problemas son recursivos en la naturaleza (construir o leer una estructura de árbol para nombrar solo uno) y luego se usa la recursión. En estos casos, es preferible utilizar la recursión de cola para dar un descanso a la pila.

• Algunos lenguajes son puramente funcionales, por lo que debe usar la recursión en lugar de bucles while, incluso si el problema no es de naturaleza recursiva

Entonces, mi pregunta: dado que F # también es compatible con el paradigma imperativo, ¿usaría la recursión de la cola en F # para problemas que no son naturalmente recursivos? ¿Especialmente desde que leí que el compilador reconoce la recursión de la cola y simplemente la transforma en un bucle de tiempo de todos modos?

Si es así, ¿por qué?

Answer 1

para problemas que no son naturalmente recursivos ... simplemente se transforma en un bucle while de todos modos

Usted contestó esto usted mismo. Use la recursividad para los problemas recursivos y el bucle para cosas que no son funcionales por naturaleza. Solo piensa siempre: lo que se siente más natural, lo que es más legible.

Answer 2

En orden de preferencia y estilo de programación general, escribiré el siguiente código:

Mapa / pliegue si está disponible

let x = [1 .. 10] |> List.map ((*) 2)

Es simplemente conveniente y fácil de usar.

Función recursiva sin cola

> let rec map f = function
    | x::xs -> f x::map f xs
    | [] -> [];;

val map : (''a -> ''b) -> ''a list -> ''b list

> [1 .. 10] |> map ((*) 2);;
val it : int list = [2; 4; 6; 8; 10; 12; 14; 16; 18; 20]

La mayoría de los algoritmos son más fáciles de leer y expresar sin recursión de cola. Esto funciona particularmente bien cuando no es necesario realizar una investigación exhaustiva, por lo que es adecuado para muchos algoritmos de clasificación y la mayoría de las operaciones en estructuras de datos equilibradas.

Recuerde, el registro ₂ (1,000,000,000,000,000) ~ = 50, por lo que la operación de registro (n) sin recursión de cola no da ningún miedo.

Cola recursiva con acumulador.

> let rev l =
    let rec loop acc = function
        | [] -> acc
        | x::xs -> loop (x::acc) xs
    loop [] l

let map f l =
    let rec loop acc = function
        | [] -> rev acc
        | x::xs -> loop (f x::acc) xs
    loop [] l;;

val rev : ''a list -> ''a list
val map : (''a -> ''b) -> ''a list -> ''b list

> [1 .. 10] |> map ((*) 2);;
val it : int list = [2; 4; 6; 8; 10; 12; 14; 16; 18; 20]

Funciona, pero el código es torpe y la elegancia del algoritmo está ligeramente oculta. El ejemplo anterior no es tan malo como para leerlo, pero una vez que te metes en estructuras de datos en forma de árbol, realmente comienza a convertirse en una pesadilla.

Cola recursiva con paso de continuación.

> let rec map cont f = function
    | [] -> cont []
    | x::xs -> map (fun l -> cont <| f x::l) f xs;;

val map : (''a list -> ''b) -> (''c -> ''a) -> ''c list -> ''b

> [1 .. 10] |> map id ((*) 2);;
val it : int list = [2; 4; 6; 8; 10; 12; 14; 16; 18; 20]

Cada vez que veo un código como este, me digo a mí mismo "¡eso es un buen truco!". Al costo de la legibilidad, mantiene la forma de la función no recursiva, y la encontró realmente interesante para las inserciones recursivas de la cola en árboles binarios .

Probablemente sea mi mocada-fobia la que habla aquí, o quizás mi inherente falta de familiaridad con la llamada / cc de Lisp, pero creo que las ocasiones en que la CSP simplifica los algoritmos son pocas y distantes. Contra-ejemplos son bienvenidos en los comentarios.

Mientras bucles / para bucles

Se me ocurre que, aparte de las comprensiones de secuencias, nunca he usado mientras o para bucles en mi código F #. En todo caso...

> let map f l =
    let l'' = ref l
    let acc = ref []
    while not <| List.isEmpty !l'' do
        acc := (!l'' |> List.hd |> f)::!acc
        l'' := !l'' |> List.tl
    !acc |> List.rev;;

val map : (''a -> ''b) -> ''a list -> ''b list

> [1 .. 10] |> map ((*) 2);;
val it : int list = [2; 4; 6; 8; 10; 12; 14; 16; 18; 20]

Es prácticamente una parodia de la programación imperativa. Es posible que pueda mantener un poco de cordura declarando let mutable l'' = l lugar, pero cualquier función no trivial requerirá el uso de ref .

Answer 3

Honestamente, cualquier problema que pueda resolver con un bucle ya es recursivo, ya que puede traducir ambos saltos (generalmente condicionales) al final.

Creo que debería seguir con las llamadas de cola en casi todos los casos en los que debe escribir un bucle explícito. Simplemente es más versátil:

• Un bucle while lo restringe a un cuerpo de bucle, mientras que una llamada de cola puede permitirle cambiar entre muchos estados diferentes mientras se está ejecutando el "bucle".
• Un bucle while lo restringe a una condición para verificar la terminación, con la recursión de la cola puede tener una expresión de coincidencia arbitrariamente complicada esperando para desviar el flujo de control en otro lugar.
• Todas las llamadas de cola devuelven valores útiles y pueden producir errores de tipo útiles. Un bucle while no devuelve nada y depende de los efectos secundarios para hacer su trabajo.
• Mientras que los bucles no son de primera clase, las funciones con llamadas de cola (o mientras que los bucles en ellos) son. Los enlaces recursivos en el ámbito local pueden ser inspeccionados por su tipo.
• Una función recursiva de cola se puede dividir fácilmente en partes que usan llamadas de cola para llamarse entre sí en la secuencia necesaria. Esto puede hacer que las cosas sean más fáciles de leer y le ayudarán si descubre que desea comenzar en medio de un ciclo. Esto no es cierto de un bucle while.

En general, los bucles en F # solo valen la pena si realmente va a trabajar con un estado mutable, dentro de un cuerpo de función, haciendo lo mismo repetidamente hasta que se cumpla una determinada condición. Si el bucle es generalmente útil o muy complicado, es posible que desee incluirlo en algún otro enlace de nivel superior. Si los tipos de datos son en sí mismos inmutables (muchos de los tipos de valores .NET lo son), puede ganar muy poco al usar referencias mutables a ellos de todos modos.

Yo diría que solo debe recurrir a los bucles while para casos de nicho donde un bucle while es perfecto para el trabajo y es relativamente corto. En muchos lenguajes de programación imperativos, mientras que los bucles a menudo se retuercen en roles antinaturales, como manejar cosas repetidamente sobre una declaración de caso. Evite ese tipo de cosas y vea si puede usar las llamadas de cola o, mejor aún, una función de orden superior, para lograr los mismos fines.

Answer 4

La mejor respuesta es ''ni''. :)

Hay algo de fealdad asociada con ambos, mientras que los bucles y la recursión de la cola.

Mientras que los bucles requieren mutabilidad y efectos, y aunque no tengo nada en contra de usarlos con moderación, especialmente cuando están encapsulados en el contexto de una función local, a veces sientes como si estuvieras saturando / uglificando tu programa cuando comienzas a introducir efectos simplemente al bucle. .

La recursión de la cola a menudo tiene la desventaja de requerir un parámetro de acumulador adicional o un estilo de paso de continuación. Esto desordena el programa con una placa extra para masajear las condiciones de inicio de la función.

La mejor respuesta es no usar ni bucles ni recursión. Las funciones de orden superior y las lambdas son sus salvadores aquí, especialmente los mapas y los pliegues. ¿Por qué jugar con las estructuras de control desordenadas para hacer un bucle cuando puede encapsularlas en bibliotecas reutilizables y luego declarar la esencia de su cálculo de forma simple y declarativa?

Si adquiere el hábito de llamar a menudo "map / fold" en lugar de usar loops / recursión, además de proporcionar una función de "fold" junto con cualquier nuevo tipo de datos con estructura de árbol que introduzca, llegará muy lejos. :)

Para aquellos interesados ​​en aprender más sobre los pliegues en F #, ¿por qué no echa un vistazo a mis three first publicaciones de blog en una serie sobre el tema?

Answer 5

Muchos problemas tienen una naturaleza recursiva, pero pensar de forma imperativa durante mucho tiempo a menudo nos impide ver esto.

En general, usaría una técnica funcional siempre que sea posible en un lenguaje funcional: los bucles nunca son funcionales, ya que dependen exclusivamente de los efectos secundarios. Entonces, cuando se trata de un código o algoritmos imperativos, el uso de bucles es adecuado, pero en un contexto funcional, no se consideran muy buenos.

La técnica funcional no solo significa recursión sino también el uso de funciones apropiadas de orden superior.

Entonces, al sumar una lista, ni una función for-loop ni una función recursiva sino un fold es la solución para tener un código comprensible sin reinventar la rueda.