Alguém pode explicar o conceito por trás da memorização de Haskell?

(observe que estou colocando a pergunta aqui porque se trata da mecânica conceitual dela, e não de um problema de codificação)

Eu estava trabalhando em um pequeno programa, que usava uma sequência de números de fibonacci em sua equasão, mas notei que, se eu superasse um certo número, ele ficaria dolorosamente lento, pesquisando um pouco, encontrei uma técnica em Haskell conhecida como Memoization: eles mostraram código funcionando assim:

-- Traditional implementation of fibonacci, hangs after about 30
slow_fib :: Int -> Integer
slow_fib 0 = 0
slow_fib 1 = 1
slow_fib n = slow_fib (n-2) + slow_fib (n-1)

-- Memorized variant is near instant even after 10000
memoized_fib :: Int -> Integer
memoized_fib = (map fib [0 ..] !!)
   where fib 0 = 0
         fib 1 = 1
         fib n = memoized_fib (n-2) + memoized_fib (n-1)

Então, minha pergunta para vocês é: como ou melhor, por que isso funciona?

É porque, de alguma maneira, ele consegue percorrer a maior parte da lista antes que o cálculo o recupere? Mas se o haskell é preguiçoso, não há realmente nenhum cálculo que precise ser alcançado ... Então, como isso funciona?

Apenas para explicar a mecânica por trás da memorização real,

memo_fib = (map fib [1..] !!)

produz uma lista de "thunks", cálculos não avaliados. Pense neles como presentes fechados, desde que não os tocemos, eles não serão executados.

Agora, quando avaliamos um thunk, nunca mais o avaliamos. Esta é realmente a única forma de mutação no haskell "normal", os thunks sofrem mutações uma vez avaliadas para se tornarem valores concretos.

Então, voltando ao seu código, você tem uma lista de thunks e ainda faz essa recursão em árvore, mas você recorre usando a lista e, uma vez que um elemento da lista é avaliado, ele nunca é computado novamente. Assim, evitamos a recursão da árvore na função ingênua da fib.

Como uma nota tangencialmente interessante, isso é especialmente rápido em uma série de números de fibonnaci são calculados, pois essa lista é avaliada apenas uma vez, o que significa que se você calcular memo_fib 10000duas vezes, a segunda vez deve ser instantânea. Isso ocorre porque Haskell avaliou apenas argumentos para funções uma vez e você está usando um aplicativo parcial em vez de um lambda.

TLDR: Armazenando cálculos em uma lista, cada elemento da lista é avaliado uma vez; portanto, cada número de fibonnacci é calculado exatamente uma vez durante todo o programa.

Visualização:

 [THUNK_1, THUNK_2, THUNK_3, THUNK_4, THUNK_5]
 -- Evaluating THUNK_5
 [THUNK_1, THUNK_2, THUNK_3, THUNK_4, THUNK_3 + THUNK_4]
 [THUNK_1, THUNK_2, THUNK_1 + THUNK_2, THUNK_4, THUNK_3 + THUNK_4]
 [1, 1, 1 + 1, THUNK_4, THUNK_3 + THUNK_4]
 [1, 1, 2, THUNK_4, 2 + THUNK4]
 [1, 1, 2, 1 + 2, 2 + THUNK_4]
 [1, 1, 2, 3, 2 + 3]
 [1, 1, 2, 3, 5]

Assim, você pode ver como a avaliação THUNK_4é muito mais rápida, pois suas subexpressões já foram avaliadas.

O objetivo da memorização nunca é calcular a mesma função duas vezes - isso é extremamente útil para acelerar cálculos puramente funcionais, ou seja, sem efeitos colaterais, porque para aqueles o processo pode ser totalmente automatizado sem afetar a correção. Isso é particularmente necessário para funções como fibo, que levam à recursão em árvore , ou seja, esforço exponencial, quando implementadas ingenuamente. (Essa é uma das razões pelas quais os números de Fibonacci são realmente um exemplo muito ruim para o ensino de recursão - quase todas as implementações de demonstração encontradas em tutoriais ou livros são inutilizáveis ​​para grandes valores de entrada.)

Se você rastrear o fluxo de execução, verá que, no segundo caso, o valor para fib xestará sempre disponível quando fib x+1for executado, e o sistema de tempo de execução poderá simplesmente lê-lo da memória, e não através de outra chamada recursiva, enquanto o A primeira solução tenta calcular a solução maior antes que os resultados para valores menores estejam disponíveis. Em última análise, isso ocorre porque o iterador [0..n]é avaliado da esquerda para a direita e, portanto, inicia com 0, enquanto a recursão no primeiro exemplo começa com ne só então pergunta sobre n-1. É isso que leva a muitas, muitas chamadas de funções duplicadas desnecessárias.