Na programação funcional, ter a maioria das estruturas de dados imutáveis requer mais uso de memória?

A única resposta correta para isso é "às vezes". Há muitos truques que linguagens funcionais podem usar para evitar o desperdício de memória. A imutabilidade facilita o compartilhamento de dados entre funções e até mesmo entre estruturas de dados, já que o compilador pode garantir que os dados não serão modificados. As linguagens funcionais tendem a encorajar o uso de estruturas de dados que podem ser usadas eficientemente como estruturas imutáveis (por exemplo, árvores em vez de tabelas hash). Se você adicionar preguiça à mistura, como muitas linguagens funcionais, isso adiciona novas maneiras de economizar memória (ela também adiciona novas maneiras de desperdiçar memória, mas eu não vou entrar nisso).

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.

Implementações ingênuas de fato expõem esse problema - quando você cria uma nova estrutura de dados em vez de atualizar uma existente no local, você precisa ter alguma sobrecarga.

Línguas diferentes têm maneiras diferentes de lidar com isso, e há alguns truques que a maioria deles usa.

Uma estratégia é a coleta de lixo . No momento em que a nova estrutura é criada, ou logo após, as referências à estrutura antiga saem do escopo, e o coletor de lixo a capta instantaneamente ou em breve, dependendo do algoritmo do GC. Isso significa que, embora ainda exista uma sobrecarga, ela é apenas temporária e não crescerá linearmente com a quantidade de dados.

Outra é escolher diferentes tipos de estruturas de dados. Onde arrays são a estrutura de dados da lista de acesso em linguagens imperativas (geralmente agrupadas em algum tipo de contêiner de realocação dinâmica, como std::vector em C ++), as linguagens funcionais geralmente preferem listas vinculadas. Com uma lista encadeada, uma operação de prefácio ('cons') pode reutilizar a lista existente como a cauda da nova lista, então tudo que realmente é alocado é o novo cabeçalho da lista. Estratégias semelhantes existem para outros tipos de estruturas de dados - conjuntos, árvores, o nome dele.

E depois há avaliação preguiçosa, à la Haskell. A ideia é que as estruturas de dados que você cria não são totalmente criadas imediatamente; em vez disso, eles são armazenados como "thunks" (você pode pensar neles como receitas para construir o valor quando necessário). Somente quando o valor é necessário, a conversão é expandida para um valor real. Isso significa que a alocação de memória pode ser adiada até que a avaliação seja necessária e, nesse ponto, vários thunks podem ser combinados em uma alocação de memória.

Eu só sei um pouco sobre o Clojure e ele Estruturas de dados imutáveis .

Clojure provides a set of immutable lists, vectors, sets and maps. Since they can't be changed, 'adding' or 'removing' something from an immutable collection means creating a new collection just like the old one but with the needed change. Persistence is a term used to describe the property wherein the old version of the collection is still available after the 'change', and that the collection maintains its performance guarantees for most operations. Specifically, this means that the new version can't be created using a full copy, since that would require linear time. Inevitably, persistent collections are implemented using linked data structures, so that the new versions can share structure with the prior version.

Graficamente, podemos representar algo assim:

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

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

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

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

Além do que foi dito em outras respostas, gostaria de mencionar a linguagem de programação Clean, que suporta os chamados tipos exclusivos . Eu não conheço essa linguagem, mas suponho que tipos únicos suportam algum tipo de "atualização destrutiva".

Em outras palavras, enquanto a semântica de atualizar um estado é que você cria um novo valor de um antigo aplicando uma função, a restrição de unicidade pode permitir que o compilador reutilize objetos de dados internamente, pois sabe que o valor antigo será não ser mais referenciado no programa depois que o novo valor tiver sido produzido.

Para mais detalhes, veja por exemplo a página inicial do Clean e este artigo da wikipedia