algorithm - paradigmas - programacion funcional ventajas y desventajas
¿Qué algoritmos son difíciles de implementar en lenguajes funcionales? (3)
Estoy incursionando en lenguajes funcionales y he encontrado que algunos algoritmos (especialmente aquellos que usan programación dinámica) son más difíciles de escribir y, a veces, menos eficientes en el peor tiempo de ejecución. ¿Existe una clase de algoritmos que sean menos eficientes en lenguajes funcionales con variables inmutables y, por lo tanto, efectos secundarios?
¿Y hay una referencia a la que alguien pueda señalarme que ayude con los algoritmos más difíciles de escribir (tal vez aquellos optimizados por el estado compartido)?
Gracias
En primer lugar, como puede que sepa o no, algunos idiomas, incluido Haskell, implementan el uso compartido, lo que alivia algunos de los problemas que podría pensar.
Si bien la respuesta de Andrew apunta a la integridad de Turing, en realidad no responde a la pregunta de qué algoritmos son difíciles de implementar en lenguajes funcionales. En lugar de preguntar qué algoritmos son difíciles de implementar en lenguajes funcionales, las personas generalmente preguntan qué estructuras de datos son difíciles de implementar en lenguajes funcionales.
La respuesta simple a esto: cosas que involucran punteros.
No hay un equivalente funcional a los punteros cuando profundiza hasta el nivel de la máquina, hay un mapa y puede compilar ciertas estructuras de datos de forma segura en arrays o cosas implementadas como punteros, pero a un nivel alto, simplemente no puede expresar cosas. Usar estructuras de datos basadas en punteros tan fácilmente como sea posible en lenguajes imperativos.
Para solucionar esto, se han hecho una serie de cosas:
- Dado que los punteros forman la base de una tabla hash, y como las tablas hash realmente solo implementan un mapa, los mapas funcionales eficientes se han estudiado exhaustivamente. De hecho, Chris Okasaki tiene un libro ("Estructuras de datos puramente funcionales") que detalla muchas, muchas formas de implementar mapas funcionales, deques, etc.
- Dado que los punteros se pueden usar para representar nodos dentro del recorrido de una estructura de datos más grande, también se ha trabajado en esta área. El producto es la cremallera , una estructura eficiente que representa de manera sucinta el equivalente funcional de la técnica de "puntero dentro de una estructura más profunda".
- Dado que los punteros se pueden usar para implementar cálculos de efectos secundarios, las mónadas se han utilizado para expresar este tipo de cálculo de una manera bonita. Debido a que es difícil hacer malabarismos con el seguimiento del estado, un uso para las mónadas es permitirle enmascarar una parte del programa que se comporta como un imperativo feo y usar el sistema de tipos para asegurarse de que el programa esté encadenado correctamente (mediante enlaces monádicos).
Si bien me gustaría decir que cualquier algoritmo se puede traducir de un imperativo a uno muy fácilmente, este no es el caso. Sin embargo, estoy bastante convencido de que el problema no son los algoritmos en sí, sino las estructuras de datos que manipulan, basadas en una noción imperativa de estado. Puede encontrar una larga lista de estructuras de datos funcionales en esta publicación.
La otra cara de todo esto es que si comienza a usar un estilo más puramente funcional, la complejidad de su programa disminuye y desaparecen muchas necesidades de estructuras de datos muy imperativas (por ejemplo, un uso muy común de punteros en imperativo). lenguajes es implementar patrones de diseño desagradables, que generalmente se traducen en usos inteligentes de polimorfismo y tipografías en el nivel funcional).
EDITAR: Creo que la esencia de esta pregunta tiene que ver con cómo expresar el cálculo de una manera funcional. Sin embargo, debe tenerse en cuenta que hay formas de definir el cálculo con estado de una manera funcional. O, más bien, es posible usar técnicas funcionales para razonar acerca de la computación con estado. Por ejemplo, el proyecto Ynot hace esto utilizando una mónada parametrizada donde los datos sobre el montón (en forma de lógica de separación) son rastreados por los enlaces monádicos.
Por cierto, incluso en ML, no veo por qué la programación dinámica es tan difícil. Parece que los problemas de programación dinámica, que generalmente acumulan colecciones de alguna secuencia para calcular una respuesta final, pueden acumular los valores construidos mediante argumentos a la función, lo que quizás requiera una continuación en algunas circunstancias. Al usar la recursión de la cola, no hay razón para que esto no sea tan bonito y eficiente como en los idiomas imperativos. Ahora seguro, puede encontrarse con el argumento de que si estos valores son listas (por ejemplo), imperativamente podemos implementarlos como matrices, pero para eso, vea el contenido de la publicación propiamente dicha :-)
Recuerde que la mayoría de los lenguajes funcionales permiten alguna noción de efectos secundarios; pueden estar mal vistos, restringidos al uso local, etc., pero aún puede usarlos. En OCaml, Haskell, F #, Scala o Clojure, puede utilizar matrices mutables si lo necesita.
Entonces, si encuentra un algoritmo para el que tiene una formulación que utiliza matrices mutables y necesita reproducirlo en uno de estos idiomas, ¡simplemente use matrices mutables!
No hay razón para obligarse a uno mismo a hacer todo usando un solo paradigma de programación; hay algunos dominios problemáticos donde la programación imperativa es (dado nuestro conocimiento actual) la herramienta más adecuada para el trabajo, al igual que hay dominios donde la programación lógica es excelente. Si le ahorra tiempo y esfuerzo para hacer un uso local y encapsulado de uno de estos paradigmas, no debe dudar en usarlos.
Por ejemplo, el Tamiz de Eratóstenes es trivial de implementar con arreglos mutables, y es mucho más difícil de imitar (razonablemente eficiente) de una manera puramente funcional: consulte el artículo de Melissa O''Neill para obtener más detalles.
Por otro lado, encontrar soluciones inmutables a un problema dado puede ser un ejercicio interesante y esclarecedor. El libro "Estructuras de datos puramente funcionales" de Crhis Okasaki es un buen ejemplo de muy buenas reformulaciones de algoritmos de una manera puramente funcional. Si está interesado en el algoritmo por sí mismo (en lugar de su aplicación a su problema), esta puede ser una actividad muy interesante.
(Para ver ejemplos de usos de compartir para optimizar un algoritmo puramente funcional, vea Perla funcional de Richard Bird y Ralf Hinze 2003 : Trouble Shared es Trouble Half a la mitad ).
Uno puede implementar características imperativas con un bajo costo asintótico, por lo que en un sentido abstracto no hay dificultad esencial para traducir el código imperativo al universo puramente funcional. En la práctica, por supuesto, hay. :-) Echa un vistazo a "Pure versus Impure Lisp" de Pippenger y los documentos que lo citan .