haskell - serie - sucesion de fibonacci ejercicios

¿Cómo se memora esta función de fibonacci?

Question

¿Por qué mecanismo se memoriza esta función de Fibonacci?

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

Y en una nota relacionada, ¿por qué esta versión no?

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

Answer 1

El mecanismo de evaluación en Haskell es por necesidad : cuando se necesita un valor, se calcula y se mantiene listo en caso de que se solicite nuevamente. Si definimos una lista, xs=[0..] y luego preguntamos por su centésimo elemento, xs!!99 , la centésima ranura de la lista se "completa", manteniendo el número 99 ahora, listo para el próximo acceso.

Eso es lo que está explotando ese truco, "ir a través de una lista". En la definición de Fibonacci doblemente recursiva, fib n = fib (n-1) + fib (n-2) , la función se llama, dos veces desde la parte superior, lo que provoca la explosión exponencial. Pero con ese truco, establecemos una lista para los resultados provisionales, y vamos "a través de la lista":

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

El truco es hacer que esa lista se cree, y hacer que esa lista no desaparezca (por medio de recolección de basura) entre las llamadas a fib . La forma más fácil de lograr esto es nombrar esa lista. "Si lo llamas, permanecerá".

Su primera versión define una constante monomórfica, y la segunda define una función polimórfica. Una función polimórfica no puede usar la misma lista interna para los diferentes tipos que podría necesitar servir, por lo que no se comparte , es decir, no hay memoria.

Con la primera versión, el compilador está siendo generoso con nosotros, sacando esa subexpresión constante ( map fib'' [0..] ) y convirtiéndola en una entidad compartible por separado, pero no tiene ninguna obligación de hacerlo. ^{y en realidad hay casos en los que no queremos que lo haga automáticamente.}

( editar:) Considere estas reescrituras:

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)

Entonces la historia real parece ser sobre las definiciones de alcance anidadas. No hay un ámbito externo con la 1ª definición, y el 3º tiene cuidado de no llamar al campo exterior fib3 , sino al mismo nivel f .

Cada nueva invocación de fib2 parece crear de nuevo sus definiciones anidadas porque cualquiera de ellas podría (en teoría) definirse de manera diferente según el valor de n (gracias a Vitus y Tikhon por señalarlo). Con la primera definición no hay n qué depender, y con el tercero hay una dependencia, pero cada llamada separada a fib3 llama a f que tiene cuidado de llamar solo las definiciones del alcance del mismo nivel, internas a esta invocación específica de fib3 , entonces el mismo xs se reutiliza (es decir, se comparte) para esa invocación de fib3 .

Pero nada impide que el compilador reconozca que las definiciones internas en cualquiera de las versiones anteriores son, de hecho, independientes del enlace n externo, para llevar a cabo el levantamiento lambda después de todo, lo que da como resultado la memorización completa (excepto las definiciones polimórficas). De hecho, eso es exactamente lo que sucede con las tres versiones cuando se declara con tipos monomórficos y se compila con el indicador -O2. Con las declaraciones de tipo polimórfico, fib3 exhibe compartir local y fib2 no compartir en absoluto.

En última instancia, dependiendo de un compilador, y de las optimizaciones del compilador utilizadas, y cómo lo prueba (cargar archivos en GHCI, compilado o no, con -O2 o no, o independiente), y si obtiene un tipo monomórfico o polimórfico, el comportamiento podría cambiar completamente - si muestra compartimiento local (por llamada) (es decir, tiempo lineal en cada llamada), memorización (es decir, tiempo lineal en la primera llamada y 0 en llamadas posteriores con el mismo argumento o menor), o no compartir nada ( tiempo exponencial).

La respuesta corta es que es un compilador. :)

Answer 2

No estoy del todo seguro, pero aquí hay una suposición educada:

El compilador supone que fib n puede ser diferente en una n diferente y, por lo tanto, debería volver a calcular la lista cada vez. Los bits dentro de la sentencia where podrían depender de n , después de todo. Es decir, en este caso, toda la lista de números es esencialmente una función de n .

La versión sin n puede crear la lista una vez y envolverla en una función. La lista no puede depender del valor de n pasado y esto es fácil de verificar. La lista es una constante que luego se indexa. Es, por supuesto, una constante que se evalúa con pereza, por lo que su programa no intenta obtener la lista completa (infinita) de inmediato. Como es una constante, se puede compartir a través de las llamadas a funciones.

Se ha memorizado porque la llamada recursiva solo tiene que buscar un valor en una lista. Dado que la versión fib crea la lista de forma perezosa, solo calcula lo suficiente para obtener la respuesta sin hacer un cálculo redundante. Aquí, "perezoso" significa que cada entrada en la lista es un thunk (una expresión no evaluada). Cuando evalúas el thunk, se convierte en un valor, por lo que acceder a él la próxima vez no repite el cálculo. Como la lista se puede compartir entre llamadas, todas las entradas anteriores ya están calculadas para cuando necesite la siguiente.

Es esencialmente una forma inteligente y de bajo costo de programación dinámica basada en la semántica perezosa de GHC. Creo que el estándar solo especifica que no debe ser estricto , por lo que un compilador compatible podría compilar este código para no memorizar. Sin embargo, en la práctica, cada compilador razonable va a ser flojo.

Para obtener más información acerca de por qué el segundo caso funciona, lea Entender una lista definida recursivamente (fibs en términos de zipWith) .

Answer 3

No necesitas la función de memoria para Haskell. Solo el lenguaje de programación empírica necesita esas funciones. Sin embargo, Haskel es funcional lang y ...

Entonces, este es un ejemplo del algoritmo de Fibonacci muy rápido:

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

zipCon la función del Preludio estándar:

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

Prueba:

print $ take 100 fib

Salida:

[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]

Tiempo transcurrido: 0.00018s

Answer 4

Primero, con ghc-7.4.2, compilado con -O2 , la versión no memorable no es tan mala, la lista interna de números de Fibonacci aún se recuerda para cada llamada de nivel superior a la función. Pero no es, y no puede razonablemente, memorable a través de diferentes llamadas de alto nivel. Sin embargo, para la otra versión, la lista se comparte entre llamadas.

Eso se debe a la restricción de monomorfismo.

El primero está vinculado por un enlace de patrón simple (solo el nombre, sin argumentos), por lo tanto, por la restricción de monomorfismo debe obtener un tipo monomórfico. El tipo inferido es

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

y dicha restricción se predetermina (a falta de una declaración predeterminada que diga lo contrario) a Integer , fijando el tipo como

fib :: Int -> Integer

Por lo tanto, solo hay una lista (del tipo [Integer] ) para memorizar.

El segundo se define con un argumento de función, por lo que sigue siendo polimórfico, y si las listas internas se registraron en llamadas, una lista tendría que ser memorada para cada tipo en Num . Eso no es práctico.

Compile ambas versiones con la restricción de monomorfismo desactivada, o con firmas de tipo idénticas, y ambas exhiben exactamente el mismo comportamiento. (Eso no era cierto para versiones anteriores de compiladores, no sé qué versión primero lo hizo).