Podemos fazer tudo em linguagens imperativas com uma linguagem funcional se ela não permitir um 'estado'?

Eu estava lendo Estrutura e Interpretação de Programas de Computador (SICP), MIT. O que eu entendi é que na linguagem de programação funcional pura, não existe um estado local. SICP, página 230 diz:

"A programação sem qualquer uso de atribuições, como fizemos nos dois últimos capítulos deste livro, é conhecida como programação funcional".

Eu venho de uma formação imperativa em programação e não consigo compreender como projetar um programa que modela um sistema do mundo real (como um banco simples ou um software de gerenciamento de bibliotecas) sem a idéia de estado.

Se a programação funcional não tem a idéia de um estado, como fazemos isso?

A chave da programação funcional não é que não exista um estado, é que exista um estado explícito .

O que isso significa é que seu estado é passado como parâmetro para suas funções. É um valor real, que você pode obter, examinar e passar para outras funções.

Por exemplo, vejamos o método de programação dinâmica para calcular os números de Fibonacci. Em uma linguagem imperativa, você teria algo parecido com isto:

def fib(n):
  A = {}
  A[0] = 0
  A[1] = 1
  for i in [2 .. n+1]:
      A[i] = A[i-1] + A[i-2]
  return A[n]

Para fazer isso sem estado, basta passar explicitamente sua loja. Usando a sintaxe Haskell-ish:

fib n = fibHelper 2 n {(1,1), (0,0)}

fibHelper i end cache = 
  if 
    i > end
  then 
    lookup end cache
  else
    let
      newVal = (lookup (i-1) cache) + (lookup (i-2) cache)
      newCache = insert i newVal cache
    in
      fibHelper (i+1) end newCache

Agora, isso é um pouco artificial, já que você não precisa de toda a matriz para os números de Fibonacci, mas pode imaginar usá-la para problemas de programação dinâmica mais complicados, como o Knapsack, onde você precisa de todo o conjunto de valores calculados anteriormente.

O principal a entender aqui é que inserté uma função que pega uma loja e retorna uma nova loja, que é igual ao original com um novo valor agregado. O valor original de cachenão é destruído; portanto, se você tiver um aplicativo em que precise de algum tipo de operação "desfazer", poderá acompanhar o histórico do seu estado.

Você pode dizer "mas isso parece ineficiente! Você está criando uma loja totalmente nova a cada vez!" No entanto, geralmente em linguagens funcionais, essas coisas são implementadas de maneira inteligente usando referências, para que não haja cópias totalmente novas dos dados.

Também vale a pena mencionar que esse padrão de ter um parâmetro de estado, transmitindo-o à medida que o cálculo avança e modificando-o, é muito comum. As pessoas inventaram abstrações, como a mônada do Estado , que permite escrever coisas que parecem imperativas, mas que são puramente funcionais "sob o capô".