En la programación funcional, ¿tener la mayoría de las estructuras de datos inmutables requiere más uso de memoria?

La única respuesta correcta a esto es "a veces". Hay muchos trucos que los lenguajes funcionales pueden usar para evitar perder memoria. La inmutabilidad hace que sea más fácil compartir datos entre funciones, e incluso entre estructuras de datos, ya que el compilador puede garantizar que los datos no serán modificados. Los lenguajes funcionales tienden a fomentar el uso de estructuras de datos que pueden usarse de manera eficiente como estructuras inmutables (por ejemplo, árboles en lugar de tablas hash). Si agrega la pereza a la mezcla, como hacen muchos lenguajes funcionales, eso agrega nuevas formas de ahorrar memoria (también agrega nuevas formas de perder memoria, pero no voy a entrar en eso).

  

En la programación funcional, ya que casi toda la estructura de datos es inmutable, cuando el estado tiene que cambiar, se crea una nueva estructura. ¿Esto significa mucho más uso de memoria?

Eso depende de la estructura de datos, los cambios exactos que realizó y, en algunos casos, el optimizador. A modo de ejemplo, consideremos prepagarse a una lista:

list2 = prepend(42, list1) // list2 is now a list that contains 42 followed
                           // by the elements of list1. list1 is unchanged

Aquí el requisito de memoria adicional es constante, al igual que el costo en tiempo de ejecución de llamar a prepend . ¿Por qué? Porque prepend simplemente crea una nueva celda que tiene 42 como cabecera y list1 como cola. No tiene que copiar ni iterar sobre list2 para lograr esto. Es decir, a excepción de la memoria requerida para almacenar 42 , list2 reutiliza la misma memoria que usa list1 . Dado que ambas listas son inmutables, este intercambio es perfectamente seguro.

De manera similar, cuando se trabaja con estructuras de árbol equilibradas, la mayoría de las operaciones requieren solo una cantidad logarítmica de espacio adicional porque todo, pero una ruta del árbol puede ser compartida.

Para matrices, la situación es un poco diferente. Es por eso que, en muchos idiomas de PF, las matrices no se usan tan comúnmente. Sin embargo, si haces algo como arr2 = map(f, arr1) y arr1 nunca se usa de nuevo después de esta línea, un optimizador inteligente puede crear código que mute a arr1 en lugar de crear una nueva matriz (sin afectar el comportamiento del programa). En ese caso, el rendimiento será como en un lenguaje imperativo, por supuesto.

Las implementaciones ingenuas de hecho expondrían este problema: cuando creas una nueva estructura de datos en lugar de actualizar una existente en el lugar, debes tener un poco de sobrecarga.

Los diferentes idiomas tienen diferentes maneras de lidiar con esto, y hay algunos trucos que utiliza la mayoría de ellos.

Una estrategia es recolección de basura . En el momento en que se haya creado la nueva estructura, o poco después, las referencias a la estructura anterior queden fuera del alcance, y el recolector de basura lo recogerá instantáneamente o lo suficientemente pronto, según el algoritmo del GC. Esto significa que si bien todavía hay una sobrecarga, es solo temporal y no crecerá de manera lineal con la cantidad de datos.

Otro es escoger diferentes tipos de estructuras de datos. Donde los arreglos son la estructura de datos de la lista de acceso en lenguajes imperativos (generalmente envueltos en algún tipo de contenedor de reasignación dinámica, como std::vector en C ++), los lenguajes funcionales a menudo prefieren listas enlazadas. Con una lista vinculada, una operación de prepend ("contras") puede reutilizar la lista existente como la cola de la nueva lista, por lo que todo lo que realmente se asigna es el nuevo encabezado de la lista. Existen estrategias similares para otros tipos de estructuras de datos: conjuntos, árboles, lo que sea.

Y luego está la evaluación perezosa, à la Haskell. La idea es que las estructuras de datos que creas no se crean completamente de inmediato; en su lugar, se almacenan como "thunks" (puede pensar en éstas como recetas para construir el valor cuando sea necesario). Solo cuando se necesita el valor, el procesador se amplía a un valor real. Esto significa que la asignación de memoria se puede diferir hasta que la evaluación sea necesaria, y en ese momento, se pueden combinar varios thunks en una asignación de memoria.

Solo sé un poco sobre Clojure y es Estructuras de datos inmutables .

  

Clojure proporciona un conjunto de listas, vectores, conjuntos y mapas inmutables.   Ya que no se pueden cambiar, 'agregar' o 'eliminar' algo de un   colección inmutable significa crear una nueva colección al igual que la antigua   Uno pero con el cambio necesario. Persistencia es un término usado para describir   La propiedad en la que la versión antigua de la colección es todavía   disponible después del 'cambio', y que la colección mantiene su   Garantías de rendimiento para la mayoría de las operaciones. Específicamente, esto significa   que la nueva versión no se puede crear utilizando una copia completa, ya que   requeriría tiempo lineal. Inevitablemente, las colecciones persistentes son   implementado utilizando estructuras de datos vinculadas, para que las nuevas versiones puedan   compartir estructura con la versión anterior.

Gráficamente, podemos representar algo como esto:

(def my-list '(1 2 3))

    +---+      +---+      +---+
    | 1 | ---> | 2 | ---> | 3 |
    +---+      +---+      +---+

(def new-list (conj my-list 0))

              +-----------------------------+
    +---+     | +---+      +---+      +---+ |
    | 0 | --->| | 1 | ---> | 2 | ---> | 3 | |
    +---+     | +---+      +---+      +---+ |
              +-----------------------------+

Además de lo que se ha dicho en otras respuestas, me gustaría mencionar el lenguaje de programación Clean, que admite los llamados tipos únicos . No conozco este idioma, pero supongo que los tipos únicos admiten algún tipo de "actualización destructiva".

En otras palabras, mientras que la semántica de actualizar un estado es que creas un nuevo valor a partir de uno antiguo aplicando una función, la restricción de unicidad puede permitir que el compilador reutilice objetos de datos internamente porque sabe que el valor antiguo no se podrá volver a consultar en el programa después de que se haya producido el nuevo valor.

Para más detalles, ver, por ejemplo, la página de inicio de Clean y esto artículo de wikipedia