In functional programming since almost all data structure are immutable, when the state has to change a new structure is created. Does this mean a lot more memory usage?
Isso depende da estrutura de dados, das alterações exatas que você realizou e, em alguns casos, do otimizador. Como um exemplo, vamos considerar a inclusão de uma lista:
list2 = prepend(42, list1) // list2 is now a list that contains 42 followed
// by the elements of list1. list1 is unchanged
Aqui, o requisito de memória adicional é constante - assim como o custo de tempo de execução da chamada de prepend
. Por quê? Porque prepend
simplesmente cria uma nova célula que tem 42
como sua cabeça e list1
como sua cauda. Ele não precisa copiar ou iterar list2
para conseguir isso. Ou seja, com exceção da memória necessária para armazenar 42
, list2
reutiliza a mesma memória usada por list1
. Como as duas listas são imutáveis, esse compartilhamento é perfeitamente seguro.
Da mesma forma, ao trabalhar com estruturas de árvore balanceadas, a maioria das operações requer apenas uma quantidade logarítmica de espaço adicional, porque tudo, mas um caminho da árvore pode ser compartilhado.
Para matrizes, a situação é um pouco diferente. É por isso que, em muitas linguagens FP, os arrays não são tão usados. No entanto, se você fizer algo como arr2 = map(f, arr1)
e arr1
nunca é usado novamente após essa linha, um otimizador inteligente pode realmente criar um código que altere arr1
em vez de criar uma nova matriz (sem afetar o comportamento do programa). Nesse caso, o desempenho será como em uma linguagem imperativa, é claro.