En primer lugar, ya que puede o no puede estar al tanto, algunos idiomas, como Haskell, implementar el intercambio, lo que alivia algunos de los problemas que podría imaginar.
Si bien la respuesta de Andrew apunta a la completitud de Turing, en realidad no responde a la pregunta de qué algoritmos son hard para implementar en lenguajes funcionales. En lugar de preguntar qué son los algoritmos difíciles de implementar en los lenguajes funcionales, la gente suele preguntar qué estructuras de datos son difíciles de implementar en los lenguajes funcionales.
La respuesta simple a esto: cosas que involucran punteros.
No hay un equivalente funcional a los punteros cuando se profundiza en el nivel de la máquina, hay un mapa y puede compilar ciertas estructuras de datos de forma segura en arreglos o cosas implementadas como punteros, pero en un nivel alto, puede Exprese cosas usando estructuras de datos basadas en punteros tan fácilmente como sea posible en idiomas imperativos.
Para evitar esto, una serie de cosas se han hecho:
- Desde punteros son la base de una tabla hash, y puesto que las tablas hash realmente sólo implementan un mapa, mapas funcionales eficientes han sido estudiados 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 algunos más grandes estructura de datos, también ha habido trabajo en esta área. El producto es cremallera, una estructura eficiente que representa sucintamente el equivalente funcional de la técnica "puntero dentro de una estructura más profunda".
- Dado que los punteros se pueden utilizar para implementar cálculos de efectos secundarios, mónadas se han utilizado para expresar este tipo de cálculos de una manera bonita. Como es difícil hacer un seguimiento del estado, un uso para las mónadas es permitirle a máscara comportarse como parte de su programa y usar el sistema de tipos para asegurarse de que el programa esté encadenado correctamente (mediante enlaces monádicos) .
Si bien yo había como decir que cualquier algoritmo puede ser traducido a partir de uno imprescindible para una funcional muy fácilmente, esto simplemente no es el caso. Sin embargo, estoy bastante convencido de que el problema no son los algoritmos per se, sino las estructuras de datos que manipulan, que se basan en una noción imperativa de estado.Puede encontrar una larga lista de estructuras de datos funcionales en this post.
La otra cara de todo esto es que si comienza a utilizar un estilo más puramente funcional, gran parte de la complejidad de su programa disminuye, y muchas necesidades de mucho las estructuras de datos imperativas desaparecen (por ejemplo, un uso muy común de punteros en lenguajes imperativos es implementar patrones desagradables de diseño, que generalmente se traducen en usos inteligentes del polimorfismo y las clases de tipo a nivel funcional).
EDIT: Creo que la esencia de esta pregunta se refiere a 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 del cálculo con estado. Por ejemplo, el proyecto Ynot hace esto usando una mónada parametrizada donde los hechos 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 que difícil. Parece que los problemas de programación dinámica, que generalmente crean colecciones de alguna secuencia para calcular una respuesta final, pueden acumular los valores construidos mediante argumentos a la función, lo que tal vez requiera una continuación en algunas circunstancias. Usando la repetición de la cola no hay razón para que esto no sea tan bonito y eficiente como en los lenguajes imperativos. Ahora, seguro, puede encontrarse con el argumento de que si estos valores son listas (por ejemplo), podemos implementarlos de forma imperativa como matrices, pero para eso, consulte el contenido de la publicación propiamente dicha :-)
http: // stackoverflow.com/questions/1990464/efficiency-of-pure-functional-programming –
Si bien es relativamente frecuente la pérdida de rendimiento al intentar utilizar el mismo * algoritmo * en un lenguaje funcional frente a uno imperativo, ese es el caso menos frecuente cuando considere diferentes algoritmos que resuelvan el mismo problema del mundo real. Si eres un programador imperativo con experiencia y estás incursionando en lenguajes funcionales, entonces toda tu experiencia pensando en algoritmos estará sesgada hacia aquellos adecuados en un contexto imperativo. – Ben