scala - ejemplos - Programación Funcional-Mucho énfasis en la recursión, ¿por qué?

programacion funcional

Question

Me están presentando la Programación Funcional [FP] (usando Scala). Una cosa que está surgiendo de mis conocimientos iniciales es que los MF dependen en gran medida de la recursividad. Y también parece que, en FP puros, la única forma de hacer cosas iterativas es escribiendo funciones recursivas.

Y debido al uso intensivo de la recursividad parece que lo siguiente de lo que los FP tenían que preocuparse era StackoverflowExceptions normalmente debido a llamadas recursivas de larga duración. Esto se abordó introduciendo algunas optimizaciones (optimizaciones relacionadas con la recursividad de cola en el mantenimiento de fotogramas de pila y anotación @tailrec de Scala v2.8 en adelante)

¿Puede alguien por favor aclararme por qué la recursión es tan importante para el paradigma de programación funcional? ¿Hay algo en las especificaciones de los lenguajes de programación funcionales que se "viole" si hacemos cosas iterativamente? Si es así, entonces estoy interesado en saber eso también.

PD: Tenga en cuenta que soy un novato en la programación funcional, así que siéntase libre de dirigirme a los recursos existentes si ellos explican / responden mi pregunta. También entiendo que Scala en particular proporciona soporte para hacer cosas iterativas también.

Answer 1

Evitar los efectos secundarios es uno de los pilares de la programación funcional (el otro está utilizando funciones de orden superior).

Imagine cómo puede utilizar el control de flujo imperativo sin depender de la mutación. ¿Es posible?

Por supuesto, for (var i = 0; i < 10; i++) ... depende de la mutación ( i++ ). De hecho, cualquier construcción de bucle condicional sí lo hace. En while (something) ... el something dependerá de algún estado mutable. Claro, while (true) ... no usa la mutación. Pero si alguna vez quieres salir de ese ciclo necesitarás un if (something) break . En realidad, trate de pensar en un mecanismo de bucle (no infinito) que no sea la recursión que no se base en la mutación.

¿Qué pasa for (var x in someCollection) ... ? Ahora nos estamos acercando a la programación funcional. La x puede considerarse como un parámetro para el cuerpo del bucle. Reutilizar el nombre no es lo mismo que reasignar un valor. Tal vez en el cuerpo del bucle yield return los valores de yield return como una expresión en términos de x (sin mutación).

Exactamente de manera equivalente, puedes mover el cuerpo del bucle for al cuerpo de una función foo (x) ... y luego mapear eso sobre una someCollection usando una función de orden superior - reemplazando tu construcción de bucle con algo como Map(foo, someCollection) .

Pero entonces, ¿cómo se implementa el Map función de biblioteca sin mutación? Bueno, usando la recursión, por supuesto! Está hecho para ti. Se vuelve menos común tener que implementar funciones recursivas usted mismo una vez que comienza a hacer uso del segundo pilar de funciones de orden superior para reemplazar sus construcciones de bucle.

Además, con la optimización de la cola de llamada, una definición recursiva es equivalente a un proceso iterativo. También puede disfrutar de esta publicación en el blog: http://blogs.msdn.com/b/ashleyf/archive/2010/02/06/recursion-is-the-new-iteration.aspx

Answer 2

Hay dos propiedades que considero esenciales para la programación funcional:

1. Las funciones son miembros de primera clase (solo relevantes, porque para que sea útil, se necesita la segunda propiedad)

2. Las funciones son puras, es decir, una función llamada con los mismos argumentos devuelve el mismo valor.

Ahora bien, si programa en un estilo imperativo, debe usar la asignación.

Considera un ciclo for. Tiene un índice y en cada iteración el índice tiene un valor diferente. Entonces, podrías definir una función que devuelva este índice. Si llama a esa función dos veces, puede obtener resultados diferentes. Así rompiendo el principio no 2.

Si se rompe el principio n. ° 2, pasar por las funciones (principio n. ° 1) se convierte en algo extremadamente peligroso, porque ahora el resultado de la función puede depender de cuándo y con qué frecuencia se llama a una función.

Answer 3

La última vez que usé un lenguaje funcional (Clojure) nunca tuve la tentación de usar la recursividad. Todo se podía tratar como un conjunto de cosas, a las que se aplicaba una función para obtener productos de la parte, a los que se aplicaba otra función, hasta que se alcanzaba el resultado final.

La recursividad es solo de una manera, y no necesariamente la más clara, para manejar los múltiples elementos que generalmente debe manejar para manejar cualquier g

Answer 4

La característica que provoca el requisito de que haga las cosas de forma recursiva son las variables inmutables.

Considere una función simple para calcular la suma de una lista (en pseudocódigo):

fun calculateSum(list):
    sum = 0
    for each element in list: # dubious
        sum = sum + element # impossible!
    return sum

Ahora, el element en cada iteración de la lista es diferente, pero podemos reescribir esto para usar una función foreach con un argumento lambda para deshacerse de este problema:

fun calculateSum(list):
    sum = 0
    foreach(list, lambda element:
        sum = sum + element # impossible!
    )
    return sum

Aún así, el valor de la variable sum tiene que ser alterado en cada ejecución de la lambda. Esto es ilegal en un lenguaje con variables inmutables, por lo que debe volver a escribirlo de una manera que no mutee el estado:

fun calculateSum([H|T]):
    return H + calculateSum(T)

fun calculateSum([]):
    return 0

Ahora, esta implementación requerirá mucho empujones y saltos desde la pila de llamadas, y un programa donde todas las operaciones pequeñas harían esto no se ejecutaría muy rápido. Por lo tanto, lo reescribimos como recursivo de cola, por lo que el compilador puede hacer una optimización de la cola de llamadas:

fun calculateSum([H|T], partialSum):
    return calculateSum(T, H + partialSum)

fun calculateSum([], partialSum):
    return partialSum

fun calculateSum(list):
    return calculateSum(list, 0)

Por supuesto, si desea hacer un ciclo indefinidamente, absolutamente necesita una llamada recursiva de cola, o de lo contrario apilaría desbordamiento.

La anotación @tailrec en Scala es una herramienta que te ayuda a analizar qué funciones son recursivas de cola. Usted afirma "Esta función es recursiva de cola" y luego el compilador puede decirle si está equivocado. Esto es especialmente importante en Scala en comparación con otros lenguajes funcionales porque la máquina en la que se ejecuta, la JVM, no es compatible con la optimización de la cola de llamadas, por lo que no es posible obtener una optimización de la cola en Scala en las mismas circunstancias que se obtendrían en otros idiomas funcionales.

Answer 5

La programación funcional pura significa programación sin efectos secundarios. Lo que significa que, si escribes un bucle, por ejemplo, el cuerpo de tu bucle no puede producir efectos secundarios. Por lo tanto, si desea que su ciclo haga algo, debe reutilizar el resultado de la iteración anterior y producir algo para la siguiente iteración. Por lo tanto, el cuerpo de su ciclo es una función, tomando como parámetro el resultado de la ejecución previa y llamándose a sí mismo para la próxima iteración con su propio resultado. Esto no tiene una gran ventaja sobre escribir directamente una función recursiva para el ciclo.

Un programa que no hace algo trivial tendrá que iterar sobre algo en algún punto. Para la programación funcional esto significa que el programa tiene que usar funciones recursivas.

Answer 6

No hay nada "especial" en la recursión. Es una herramienta generalizada en programación y matemática y nada más. Sin embargo, los lenguajes funcionales son generalmente minimalistas. Introducen muchos conceptos sofisticados como la coincidencia de patrones, el sistema de tipos, la comprensión de listas, etc., pero no es más que azúcar sintáctico para herramientas muy generales y muy poderosas, pero simples y primitivas. Estas herramientas son: abstracción de funciones y aplicación de funciones. Esta es una elección consciente, ya que la simplicidad del núcleo del lenguaje hace que el razonamiento al respecto sea mucho más fácil. También hace que escribir compiladores sea más fácil. La única forma de describir un bucle en términos de estas herramientas es utilizar la recursión, por lo que los programadores imperativos pueden pensar que la programación funcional se trata de la recursión. No lo es, simplemente se requiere imitar esos loops de lujo para los pobres que no pueden dejar caer este azúcar sintáctico sobre la afirmación de goto , por lo que es una de las primeras cosas en las que se metieron.

Otro punto donde (puede ser indirecta) la recursión requerida es el procesamiento de estructuras de datos definidas recursivamente. El ejemplo más común es la list ADT. En FP generalmente se define como esta data List a = Nil | Branch a (List a) data List a = Nil | Branch a (List a) . Como la definición del ADT aquí es recursiva, la función de procesamiento también debe ser recursiva. Nuevamente, la recursión aquí no es de ninguna manera especial: el procesamiento de tal ADT en forma recursiva se ve naturalmente tanto en los lenguajes imperativos como en los funcionales. Bueno, en el caso de los bucles imperativos ADT de tipo lista todavía se pueden adoptar, pero en el caso de diferentes estructuras arbóreas no pueden.

Entonces no hay nada especial en la recursión. Es simplemente otro tipo de aplicación de función. Sin embargo, debido a las limitaciones de los sistemas informáticos modernos (que provienen de decisiones de diseño mal hechas en lenguaje C, que de facto es el ensamblador multiplataforma estándar) las llamadas a funciones no pueden anidarse infinitamente, incluso si son llamadas finales. Debido a esto, los diseñadores de lenguajes de programación funcionales tienen que limitar las llamadas de cola permitidas a la recurrencia de cola (scala) o usar técnicas complicadas como trampolín (antiguo ghc codegen) o compilar directamente a asm (ghc codegen moderno).

TL; DR: No hay nada especial en recursividad en FP, no más que en IP al menos, sin embargo, la recursividad de cola es el único tipo de llamadas de cola permitidas en scala debido a las limitaciones de JVM.

Answer 7

Por el bien de los nuevos estudiantes de FP, me gustaría agregar mis 2 centavos. Como se menciona en algunas de las respuestas, la recursividad es su uso de variables inmutables, pero ¿por qué tenemos que hacer eso? es porque hace que sea más fácil ejecutar el programa en múltiples núcleos en paralelo, pero ¿por qué queremos eso? ¿No podemos ejecutarlo en un solo núcleo y ser felices como siempre lo hemos sido? No porque el contenido para procesar está aumentando día a día y el ciclo del reloj de la CPU no se puede aumentar tan significativamente como para agregar más núcleos. Desde la última década, la velocidad del reloj ha sido de hasta 2,7 ghz a 3,0 ghz para las computadoras de consumo y los diseñadores de chips tienen problemas para instalar más y más transistores en sus redes. También la FP ha sido desde hace mucho tiempo, pero no ya que usaba recursividad y la memoria era muy costosa en esos días, pero como las velocidades de reloj aumentaban año tras año, la comunidad decidió continuar con OOP Edit: era bastante rápido, solo tenía unos minutos

Answer 8

La tesis de Church Turing destaca la equivalencia entre diferentes modelos de computabilidad.

Usando recursión no necesitamos un estado mutable mientras resolvemos algún problema, y ​​esto hace posible especificar una semántica en términos más simples. Por lo tanto, las soluciones pueden ser más simples, en un sentido formal.

Creo que Prolog muestra mejor que los lenguajes funcionales la efectividad de la recursión (no tiene iteración) y los límites prácticos que encontramos al usarla.

Answer 9

TL; DR : recursión se utiliza para manejar datos definidos inductivamente, que son omnipresentes.

La recursión es natural cuando opera en niveles más altos de abstracción. La programación funcional no se trata solo de codificar con funciones; se trata de operar en niveles más altos de abstracción, donde naturalmente utilizas funciones. Usando funciones, es natural reutilizar la misma función (llamarla de nuevo), desde cualquier contexto donde tenga sentido.

El mundo se construye mediante la repetición de bloques de construcción similares / mismos. Si cortas un trozo de tela en dos, tienes dos piezas de tela. La inducción matemática está en el corazón de las matemáticas. Nosotros, los humanos, contamos (como en, 1,2,3 ... ). Cualquier cosa definida inductivamente (como, {números de 1} son {1 y números de 2} ) es natural de manejar / analizar por una función recursiva, de acuerdo con los mismos casos en que esa cosa se define / construye.

La recursión está en todas partes. Cualquier bucle iterativo es una recursión disfrazada de todos modos, porque cuando vuelves a ingresar ese bucle, vuelves a ingresar al mismo bucle nuevamente (solo con quizás variables de bucle diferentes). Por lo tanto, no es como inventar nuevos conceptos sobre informática, sino más bien descubrir las bases y hacerlo explícito .

Entonces, la recursión es natural. Simplemente escribimos algunas leyes sobre nuestro problema, algunas ecuaciones que involucran la función que estamos definiendo, que conservan algo invariable (bajo el supuesto de que la función está definida coherentemente), vuelven a especificar el problema en términos simplificados y ¡voilá! Tenemos la solución.

Un ejemplo, una función para calcular la longitud de la lista (un tipo de datos recursivos definidos inductivamente). Asuma que está definido, y devuelve la longitud de la lista, no sorprendentemente. ¿Cuáles son las leyes que debe obedecer? ¿Qué invariante se conserva bajo qué simplificación de un problema?

El más inmediato es separar la lista de su elemento principal, y el resto, también conocido como la cola de la lista (según cómo se define / construye una lista). La ley es,

length (x:xs) = 1 + length xs

¡Oh! Pero ¿qué pasa con la lista vacía? Debe ser que

length [] = 0

Entonces, ¿cómo escribimos tal función? ... Espera ... ¡Ya lo hemos escrito! (En Haskell, si se preguntaba, donde la aplicación de funciones se expresa mediante yuxtaposición, los paréntesis se usan solo para agrupar, y (x:xs) es una lista con x su primer elemento y xs el resto de ellos).

Todo lo que necesitamos de un lenguaje que permita este estilo de programación es que tiene TCO (y tal vez, un poco lujoso, TRMCO ), por lo que no hay explosión de pila, y estamos listos.

Otra cosa es la pureza: la inmutabilidad de las variables de código y / o la estructura de datos (campos de registros, etc.).

Lo que hace, además de liberar nuestras mentes de tener que rastrear qué cambia cuando, hace que el tiempo sea explícitamente aparente en nuestro código, en lugar de esconderse en nuestras variables / datos variables "cambiantes". Solo podemos "cambiar" en el código imperativo el valor de una variable a partir de ahora ; no podemos cambiar su valor en el pasado, ¿verdad?

Y así terminamos con listas de historial de cambios registrados, con cambios explícitamente aparentes en el código: en lugar de x := x + 2 escribimos let x2 = x1 + 2 . Hace que razonar sobre el código sea mucho más fácil.

Para abordar la inmutabilidad en el contexto de la recursividad de cola con TCO , considere esta repetición recursiva de cola de la length de la función anterior bajo el paradigma de argumento de acumulador:

length xs = length2 0 xs              -- the invariant: 
length2 a []     = a                  --     1st arg plus
length2 a (x:xs) = length2 (a+1) xs   --     length of 2nd arg

Aquí TCO significa reutilización de cuadro de llamada, además del salto directo, por lo que la cadena de llamada para la length [1,2,3] se puede ver como mutando realmente las entradas del marco de la pila de llamadas correspondientes a los parámetros de la función:

length [1,2,3]
length2 0 [1,2,3]       -- a=0  (x:xs)=[1,2,3]
length2 1 [2,3]         -- a=1  (x:xs)=[2,3]
length2 2 [3]           -- a=2  (x:xs)=[3]
length2 3 []            -- a=3  (x:xs)=[]
3

En un lenguaje puro, sin primitivas mutantes de valor, la única forma de expresar el cambio es pasar los valores actualizados como argumentos a una función para su posterior procesamiento. Si el procesamiento posterior es el mismo que antes, de forma natural tenemos que invocar la misma función para eso, pasándole los valores actualizados como argumentos. Y eso es recursividad.

Y el siguiente hace que toda la historia del cálculo de la longitud de una lista de argumentos sea explícita (y disponible para su reutilización, si es necesario):

length xs = last results
  where
     results = length3 0 xs
     length3 a []     = [a]
     length3 a (x:xs) = a : length3 (a+1) xs

En Haskell esto se conoce de forma variable como recursión protegida o corecursion (al menos creo que lo es).