Como essa função de fibonacci é memorizada?

114

Por qual mecanismo essa função de fibonacci é memorizada?

fib = (map fib' [0..] !!)                 
     where fib' 1 = 1                                                        
           fib' 2 = 1                                                        
           fib' n = fib (n-2) + fib (n-1)                    

E em uma nota relacionada, por que esta versão não é?

fib n = (map fib' [0..] !! n)                                               
     where fib' 1 = 1                                                        
           fib' 2 = 1                                                        
           fib' n = fib (n-2) + fib (n-1)                    
bjornars
fonte
13
Ligeiramente não relacionado, fib 0não termina: você provavelmente quer que os casos-base fib'sejam fib' 0 = 0e fib' 1 = 1.
junho
1
Observe que a primeira versão pode ser mais concisa: fibs = 1:1:zipWith (+) fibs (tail fibs)e fib = (fibs !!).
Bastian

Respostas:

95

O mecanismo de avaliação em Haskell é por necessidade : quando um valor é necessário, ele é calculado e mantido pronto para o caso de ser solicitado novamente. Se definirmos alguma lista, xs=[0..]e depois pedirmos seu 100º elemento,, xs!!99o 100º slot na lista será "desenvolvido", segurando o número 99agora, pronto para o próximo acesso.

Isso é o que aquele truque, "passar por uma lista", está explorando. Na definição normal de Fibonacci duplamente recursiva fib n = fib (n-1) + fib (n-2), a própria função é chamada, duas vezes a partir do topo, causando a explosão exponencial. Mas, com esse truque, estabelecemos uma lista para os resultados provisórios e examinamos "a lista":

fib n = (xs!!(n-1)) + (xs!!(n-2)) where xs = 0:1:map fib [2..]

O truque é fazer com que essa lista seja criada e que essa lista não desapareça (por meio de coleta de lixo) entre as chamadas para fib. A maneira mais fácil de fazer isso é nomear essa lista. "Se você der um nome, ele vai ficar."


Sua primeira versão define uma constante monomórfica e a segunda define uma função polimórfica. Uma função polimórfica não pode usar a mesma lista interna para diferentes tipos que ela pode precisar servir, portanto, nenhum compartilhamento , ou seja, nenhuma memoização.

Com a primeira versão, o compilador está sendo generoso conosco, retirando essa subexpressão constante ( map fib' [0..]) e tornando-a uma entidade compartilhável separada, mas não tem nenhuma obrigação de fazer isso. e há casos em que não queremos que isso aconteça para nós automaticamente.

( editar :) Considere estas reescritas:

fib1 = f                     fib2 n = f n                 fib3 n = f n          
 where                        where                        where                
  f i = xs !! i                f i = xs !! i                f i = xs !! i       
  xs = map fib' [0..]          xs = map fib' [0..]          xs = map fib' [0..] 
  fib' 1 = 1                   fib' 1 = 1                   fib' 1 = 1          
  fib' 2 = 1                   fib' 2 = 1                   fib' 2 = 1          
  fib' i=fib1(i-2)+fib1(i-1)   fib' i=fib2(i-2)+fib2(i-1)   fib' i=f(i-2)+f(i-1)

Portanto, a verdadeira história parece ser sobre as definições de escopo aninhadas. Não há escopo externo com a 1ª definição, e a 3ª tem o cuidado de não chamar o escopo externo fib3, mas o mesmo nível f.

Cada nova invocação de fib2parece criar suas definições aninhadas novamente, porque qualquer uma delas poderia (em teoria) ser definida de forma diferente dependendo do valor de n(graças a Vitus e Tikhon por apontar isso). Com a primeira definição não há do nque depender e com a terceira há uma dependência, mas cada chamada separada para fib3chamadas em fque tem o cuidado de chamar apenas as definições do escopo de mesmo nível, interno a esta invocação específica de fib3, para que o mesmo xsseja reutilizado (isto é, compartilhado) para essa invocação de fib3.

Mas nada impede o compilador de reconhecer que as definições internas em qualquer uma das versões acima são de fato independentes da nligação externa , para realizar o levantamento de lambda, afinal, resultando em memoização completa (exceto para as definições polimórficas). Na verdade, isso é exatamente o que acontece com todas as três versões quando declaradas com tipos monomórficos e compiladas com o sinalizador -O2. Com declarações de tipo polimórfico, fib3exibe compartilhamento local e fib2nenhum compartilhamento.

Em última análise, dependendo de um compilador e das otimizações do compilador usadas e de como você o testa (carregando arquivos em GHCI, compilados ou não, com -O2 ou não, ou autônomo), e se obtém um tipo monomórfico ou polimórfico, o comportamento pode mude completamente - se exibe compartilhamento local (por chamada) (ou seja, tempo linear em cada chamada), memoização (ou seja, tempo linear na primeira chamada e tempo 0 nas chamadas subsequentes com o mesmo argumento ou menor), ou nenhum compartilhamento ( tempo exponencial).

A resposta curta é, é uma coisa do compilador. :)

Will Ness
fonte
4
Só para corrigir um pequeno detalhe: a segunda versão não recebe qualquer partilha principalmente porque a função local fib'é redefinido para cada ne, portanto, fib'em fib 1fib'em fib 2, o que implica também as listas são diferentes. Mesmo se você corrigir o tipo para ser monomórfico, ele ainda exibirá esse comportamento.
Vitus
1
wherecláusulas introduzem compartilhamento muito parecido com letexpressões, mas tendem a esconder problemas como este. Reescrevendo-o um pouco mais explicitamente, você obtém isto: hpaste.org/71406
Vitus
1
Outro ponto interessante sobre a sua reescrita: se você der a eles o tipo monomórfico (isto é Int -> Integer), então fib2é executado em tempo exponencial, fib1e fib3ambos são executados em tempo linear, mas fib1também são memoizados - novamente porque fib3as definições locais são redefinidas para cada n.
Vitus
1
@misterbee Mas, de fato, seria bom ter algum tipo de garantia do compilador; algum tipo de controle sobre a residência da memória de uma entidade específica. Às vezes queremos compartilhar, às vezes queremos evitar. Eu imagino / espero que seja possível ...
Will Ness
1
@ElizaBrandt o que eu quis dizer é que às vezes queremos recalcular algo pesado para que não seja retido para nós na memória - ou seja, o custo do recálculo é menor do que o custo de uma grande retenção de memória. um exemplo é a criação do conjunto de poderes: pwr (x:xs) = pwr xs ++ map (x:) pwr xs ; pwr [] = [[]]queremos pwr xsser calculados independentemente, duas vezes, para que possa ser coletado como lixo em tempo real à medida que é produzido e consumido.
Will Ness
23

Não estou totalmente certo, mas aqui está um palpite:

O compilador assume que fib npoderia ser diferente em um diferente ne, portanto, precisaria recalcular a lista a cada vez. Afinal, os bits dentro da wheredeclaração podem depender n. Ou seja, neste caso, toda a lista de números é essencialmente uma função de n.

A versão sem n pode criar a lista uma vez e envolvê-la em uma função. A lista não pode depender do valor de npassado e isso é fácil de verificar. A lista é uma constante que é então indexada. É, claro, uma constante que é avaliada preguiçosamente, então seu programa não tenta obter a lista inteira (infinita) imediatamente. Por ser uma constante, ela pode ser compartilhada nas chamadas de função.

É memorizado porque a chamada recursiva precisa apenas procurar um valor em uma lista. Como a fibversão cria a lista uma vez preguiçosamente, ela apenas calcula o suficiente para obter a resposta sem fazer cálculos redundantes. Aqui, "preguiçoso" significa que cada entrada na lista é uma conversão (uma expressão não avaliada). Quando você não avaliar a conversão, torna-se um valor, então acessá-lo na próxima vez que não repetir o cálculo. Como a lista pode ser compartilhada entre chamadas, todas as entradas anteriores já são calculadas no momento em que você precisa da próxima.

É essencialmente uma forma inteligente e barata de programação dinâmica baseada na semântica preguiçosa do GHC. Acho que o padrão especifica apenas que não deve ser estrito , portanto, um compilador compatível poderia potencialmente compilar esse código para não memoize. No entanto, na prática, todo compilador razoável será preguiçoso.

Para obter mais informações sobre por que o segundo caso funciona, leia Compreendendo uma lista definida recursivamente (fibs em termos de zipWith) .

Tikhon Jelvis
fonte
você quis dizer " fib' npoderia ser diferente em um diferente n", talvez?
Will Ness
Acho que não fui muito claro: o que quis dizer é que tudo dentro fib, inclusive fib', pode ser diferente em cada diferente n. Eu acho que o exemplo original é um pouco confuso porque fib'também depende dele próprio nque sombreia o outro n.
Tikhon Jelvis
20

Primeiro, com ghc-7.4.2, compilado com -O2, a versão não memoised não é tão ruim, a lista interna de números Fibonacci ainda memoised para cada chamada de nível superior para a função. Mas não é, e não pode ser razoavelmente, memoised em diferentes chamadas de nível superior. No entanto, para a outra versão, a lista é compartilhada entre as chamadas.

Isso se deve à restrição do monomorfismo.

O primeiro é limitado por uma associação de padrão simples (apenas o nome, sem argumentos), portanto, pela restrição de monomorfismo, deve obter um tipo monomórfico. O tipo inferido é

fib :: (Num n) => Int -> n

e tal restrição é padronizada (na ausência de uma declaração padrão dizendo o contrário) para Integer, fixando o tipo como

fib :: Int -> Integer

Portanto, há apenas uma lista (do tipo [Integer]) para memorizar.

O segundo é definido com um argumento de função, portanto, permanece polimórfico e, se as listas internas fossem memoizadas entre as chamadas, uma lista teria que ser memoizada para cada tipo em Num. Isso não é prático.

Compile as duas versões com a restrição de monomorfismo desabilitada ou com assinaturas de tipo idênticas e ambas exibirão exatamente o mesmo comportamento. (Isso não era verdade para as versões mais antigas do compilador, não sei qual versão fez isso primeiro.)

Daniel Fischer
fonte
Por que não é prático memorizar uma lista para cada tipo? Em princípio, o GHC poderia criar um dicionário (bem como para chamar funções restritas de classe de tipo) para conter listas parcialmente computadas para cada tipo de Num encontrado durante o tempo de execução?
misterbee
1
@misterbee Em princípio, poderia, mas se o programa chamar fib 1000000vários tipos, isso consumirá uma tonelada de memória. Para evitar isso, seria necessária uma heurística que listasse itens para serem descartados do cache quando ele se tornasse muito grande. E essa estratégia de memoisação também se aplicaria a outras funções ou valores, presumivelmente, de modo que o compilador teria que lidar com um número potencialmente grande de coisas para memorizar para muitos tipos em potencial. Acho que seria possível implementar o memoisation polimórfico (parcial) com uma heurística razoavelmente boa, mas duvido que valha a pena.
Daniel Fischer
5

Você não precisa da função memoize para Haskell. Apenas a linguagem de programação empirativa precisa dessas funções. No entanto, Haskel é uma linguagem funcional e ...

Portanto, este é um exemplo de algoritmo de Fibonacci muito rápido:

fib = zipWith (+) (0:(1:fib)) (1:fib)

zipWith é uma função do Prelude padrão:

zipWith :: (a->b->c) -> [a]->[b]->[c]
zipWith op (n1:val1) (n2:val2) = (n1 + n2) : (zipWith op val1 val2)
zipWith _ _ _ = []

Teste:

print $ take 100 fib

Resultado:

[1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170,1836311903,2971215073,4807526976,7778742049,12586269025,20365011074,32951280099,53316291173,86267571272,139583862445,225851433717,365435296162,591286729879,956722026041,1548008755920,2504730781961,4052739537881,6557470319842,10610209857723,17167680177565,27777890035288,44945570212853,72723460248141,117669030460994,190392490709135,308061521170129,498454011879264,806515533049393,1304969544928657,2111485077978050,3416454622906707,5527939700884757,8944394323791464,14472334024676221,23416728348467685,37889062373143906,61305790721611591,99194853094755497,160500643816367088,259695496911122585,420196140727489673,679891637638612258,1100087778366101931,1779979416004714189,2880067194370816120,4660046610375530309,7540113804746346429,12200160415121876738,19740274219868223167,31940434634990099905,51680708854858323072,83621143489848422977,135301852344706746049,218922995834555169026,354224848179261915075,573147844013817084101]

Tempo decorrido: 0,00018s

Валерий Кобзарь
fonte
Esta solução é incrível!
Larry