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

12

(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?

Café elétrico
fonte
1
você poderia esclarecer o que você quer dizer com the calculation catches up? BTW, memoization não é específico para Haskell: en.wikipedia.org/wiki/Memoization
Simon Bergot
ver a minha explicação em resposta de Killan
café eléctrica
2
Ame sua pergunta; Apenas uma nota rápida: A técnica é chamada memo i zação, não memo ri zação.
Racheet

Respostas:

11

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.

Daniel Gratzer
fonte
você poderia fornecer um exemplo de como os valores na lista se comportam em uma sequência curta? Eu acho que isso pode aumentar a visualização de como deve funcionar ... E, embora seja verdade que se eu ligar memo_fibcom o mesmo valor duas vezes, a segunda vez será instantânea, mas se eu chamar com um valor 1 maior, ainda leva uma eternidade para avaliar (como dizem que vai de 30 a 31)
Eléctrico Coffee
@ElectricCoffee Adicionado
Daniel Gratzer
@ElectricCoffee Não, desde então, memo_fib 29e memo_fib 30já foi avaliado, levará exatamente o tempo necessário para adicionar esses dois números :) Depois que algo é avaliado, ele é avaliado.
precisa
1
@ElectricCoffee Seu recursão tem que percorrer a lista, caso contrário, você não ganhar qualquer desempenho
Daniel Gratzer
2
@ElectricCoffee Sim. mas o 31º elemento da lista não está usando cálculos anteriores, você está memorizando sim, mas de uma maneira bastante inútil. Os cálculos repetidos não são computados duas vezes, mas você ainda tem recursão em árvore para cada novo valor que é muito, muito lento
Daniel Gratzer
1

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.

Kilian Foth
fonte
oh, eu entendo o ponto, simplesmente não entendo como funciona, como pelo que posso ver no código, é que, quando você escreve, memorized_fib 20por exemplo, está escrevendo map fib [0..] !! 20, ele ainda precisa calcular o valor intervalo inteiro de números até 20, ou estou faltando alguma coisa aqui?
Electric Coffee
1
Sim, mas apenas uma vez para cada número. A implementação ingênua calcula com fib 2tanta frequência que fará sua cabeça girar - vá em frente, anote a árvore da chamada com apenas um pequeno valor n==5. Você nunca mais esquecerá a memorização depois de ver o que ela salva.
Kilian Foth
@ElectricCoffee: Sim, ele calculará uma fib de 1 a 20. Você não ganha nada com essa ligação. Agora tente calcular a fib 21 e verá que, em vez de calcular 1-21, você pode calcular 21 porque já possui 1-20 calculado e não precisa fazer isso novamente.
Phoshi
Estou tentando escrever a árvore de chamadas n = 5e, atualmente, cheguei ao ponto em que n == 3, até agora tudo bem, mas talvez seja apenas a minha mente imperativa pensando isso, mas isso não significa apenas para n == 3você map fib [0..]!!3? que então entra no fib nramo do programa ... onde exatamente eu recebo o benefício dos dados pré-computados?
Electric Coffee
1
Não, memoized_fibestá bem. É slow_fibisso que fará você chorar se você rastrear.
Kilian Foth