functional programming - react - Programación funcional: eficiencia de la estructura de datos inmutable.

programacion funcional react

Question

No entiendo, cómo los compiladores de FP hacen que el código que trata con estructuras de datos inmutables sea rápido, no explotar pila, etc.

Por ejemplo, la operación de inserción en el árbol, tiene que copiar todo el árbol antes de agregar el nuevo nodo y devolver el árbol copiado, en lugar del imperativo couterpart que solo necesita agregar un indicador al nuevo nodo. Si la operación de inserción se ejecuta millones de veces, se necesitaría una carga de memoria y la copia será más lenta y más lenta cuando el árbol sea más grande. ¿Cómo los compiladores de FP realmente optimizan esto?

Answer 1

Echa un vistazo a la estructura de datos de la cremallera .

Answer 2

El compilador realmente no optimizará esto, es algo que tienes que programar específicamente para la codificación. Las técnicas para hacer esto se explican en las excelentes Estructuras de datos puramente funcionales ( book , thesis ).

Answer 3

No tienes que copiar todo el árbol para hacer un cambio; Puedes compartir la mayor parte de la estructura. Vea, por ejemplo, los diagramas en este blog , o esta charla de Rich Hickey en Clojure (vea la discusión de intentos de hash a mitad de camino).

Answer 4

Si el recolector de basura está haciendo su trabajo, las copias más antiguas de la estructura de datos se reclamarán cuando ya no se usen.