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.