Otimização de chamadas de função em Haskell - otimização, haskell, ghc, memoization, transparência referencial

Não sei exatamente o que fazer no google para esta pergunta, então eu a publicarei diretamente no SO:

1. Variáveis ​​em Haskell são imutáveis
2. Funções puras devem resultar nos mesmos valores para os mesmos argumentos

Desses dois pontos, é possível deduzir que, se você chamar somePureFunc somevar1 somevar2 no seu código duas vezes, só faz sentidocalcule o valor durante a primeira chamada. O valor resultante pode ser armazenado em algum tipo de tabela hash gigante (ou algo parecido) e consultado durante chamadas subseqüentes à função. Eu tenho duas perguntas:

1. O GHC realmente faz esse tipo de otimização?
2. Em caso afirmativo, qual é o comportamento no caso em que é realmente mais barato repetir o cálculo do que procurar os resultados?

Obrigado.

Respostas:

O GHC não faz automático memorização. Veja as Perguntas frequentes do GHC sobre Eliminação de subexpressão comum (não exatamente a mesma coisa, mas acho que o raciocínio é o mesmo) e a resposta para essa questão.

Se você mesmo deseja memorizar, dê uma olhada em Data.MemoCombinators.

Outra maneira de ver a memorização é usarpreguiça de tirar proveito da memorização. Por exemplo, você pode definir uma lista em termos de si mesma. A definição abaixo é uma lista infinita de todos os números de Fibonacci (extraídos do Wiki do Haskell)

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Como a lista é realizada preguiçosamente, é semelhante a ter valores pré-computados (memorizados) pré-computados. fibs !! 10 criará os dez primeiros elementos de modo que fibs 11 é muito mais rápido.

Salvar todos os resultados das chamadas de funções (cf. mistura de hash) é válido, mas pode ser um vazamento de espaço gigante e, em geral, também atrasa bastante o programa. Muitas vezes custa mais para verificar se você tem algo na tabela do que realmente calculá-lo.