algorithm - ¿La programación funcional(pura) es antagónica con los "algoritmos clásicos"?

functional-programming taocp

Question

Los clásicos libros de algoritmos (TAOCP, CLR) (y no tan clásicos, como el fxtbook ) están llenos de algoritmos imperativos . Esto es más obvio con algoritmos cuya implementación está fuertemente basada en matrices, como la generación combinatoria (donde se usan tanto el índice de matriz como el valor de matriz en el algoritmo) o el algoritmo de búsqueda de unión.

El peor análisis de complejidad de estos algoritmos depende de que los accesos a la matriz sean O (1). Si reemplaza las matrices con estructuras persistentes de array-ish, como lo hace Clojure, los accesos a la matriz ya no son O (1), y el análisis de complejidad de esos algoritmos ya no es válido.

Lo que me lleva a las siguientes preguntas: ¿la programación funcional pura es incompatible con la literatura de algoritmos clásicos?

Answer 1

Con respecto a las estructuras de datos, Chris Okasaki ha realizado importantes investigaciones para adoptar estructuras de datos clásicas en un entorno puramente funcional, ya que muchas de las estructuras de datos estándar ya no funcionan cuando se utilizan actualizaciones destructivas. Su libro "Estructuras de datos puramente funcionales" muestra cómo algunas estructuras, como montones binomiales y árboles rojos / negros, se pueden implementar bastante bien en un entorno funcional, mientras que otras estructuras básicas como matrices y colas deben implementarse con conceptos más elaborados.

Si está interesado en seguir esta rama de los algoritmos centrales, su libro sería un excelente punto de partida.

Answer 2

La respuesta corta es que, siempre que el algoritmo no tenga efectos que puedan observarse después de que finalice (aparte de lo que devuelve), entonces es puro. Esto se mantiene incluso cuando haces cosas como actualizaciones de matriz destructiva o mutación.

Si tuvieras un algoritmo como por ejemplo:

function zero(array):
    ix <- 0
    while(ix < length(array)):
       array[ix] <- 0
       ix <- ix+1
    return array

Suponiendo que nuestro pseudocódigo anterior tiene un alcance léxico, siempre que el parámetro de la matriz se copie primero y la matriz devuelta sea algo completamente nuevo, este algoritmo representa una función pura (en este caso, la función Haskell fmap (const 0) probablemente funcione ) La mayoría de los algoritmos "imperativos" que se muestran en los libros son funciones realmente puras, y está perfectamente bien escribirlos de esa manera en un entorno puramente funcional utilizando algo como ST.

Recomendaría buscar en Mercury o en el Compilador Disciplinado de Discípulos para ver lenguajes puros que todavía prosperan en la destrucción.

Answer 3

No lo es. Pero es cierto que uno puede ver en muchos algoritmos de libros que parecen ser solo utilizables en lenguajes imperativos. La razón principal es que la programación funcional pura se restringió al uso académico durante mucho tiempo. Luego, los autores de estos algoritmos se basaron en gran medida en las características imperativas para estar en la corriente principal. Ahora, considere dos algoritmos ampliamente difundidos: clasificación rápida y clasificación por fusión. El ordenamiento rápido es más "imperativo" que el tipo de combinación; una de sus ventajas es estar en su lugar. La clasificación de fusión es más "pura" que la clasificación rápida (de alguna manera) ya que necesita copiar y mantener sus datos persistentes. En realidad, muchos algoritmos pueden implementarse en una programación funcional pura sin perder demasiada eficiencia. Esto es cierto para muchos algoritmos en el famoso Dragon Book, por ejemplo.

Answer 4

Puede que le interese esta pregunta relacionada: Eficiencia de la programación puramente funcional .

¿Hay algún problema para el cual el algoritmo no destructivo mejor conocido sea asintóticamente peor que el algoritmo destructivo más conocido y, en caso afirmativo, cuánto?