programación funcional: inmutable eficiencia de la estructura de datos

Question

que no entiendo, cómo compiladores FP hacen que el código se trata de estructuras de datos inmutables, no estallar pila rápido, etc.

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

Answer 1

No tiene que copiar todo el árbol para hacer un cambio; puedes compartir la mayor parte de la estructura. Ver p. los diagramas en this blog, o this talk por Rich Hickey en Clojure (ver la discusión de los intentos de hash a la mitad).

Answer 2

Eche un vistazo a Zipper data structure.

Answer 3

El compilador realmente no optimizará esto, es algo que tiene que programar específicamente al codificar. Las técnicas para hacer esto se explican en las excelentes Estructuras de Datos Puramente Funcionales (book, thesis).

Answer 4

Si el recolector de basura hace su trabajo, las copias antiguas de la estructura de datos se recuperarán cuando ya no se utilicen.