maximo - Generando números de Fibonacci en Haskell?
take haskell (8)
Aquí hay una función simple que calcula el n ° número de Fibonacci:
fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
La función en tu pregunta funciona así:
Supongamos que ya tiene una lista infinita de los números de Fibonacci:
[ 1, 1, 2, 3, 5, 8, 13, .... ]
La tail de esta lista es
[ 1, 2, 3, 5, 8, 13, 21, .... ]
zipWith dos listas elemento por elemento usando el operador dado:
[ 1, 1, 2, 3, 5, 8, 13, .... ]
+ [ 1, 2, 3, 5, 8, 13, 21, .... ]
= [ 2, 3, 5, 8, 13, 21, 34, .... ]
Entonces la lista infinita de números de Fibonacci puede calcularse anteponiendo los elementos 1 y 1 al resultado de comprimir la lista infinita de números de Fibonacci con la cola de la lista infinita de números de Fibonacci usando el operador + .
Ahora, para obtener el n. º número de Fibonacci, solo obtenga el n-ésimo elemento de la lista infinita de números de Fibonacci:
fib n = fibs !! n
La belleza de Haskell es que no calcula ningún elemento de la lista de números de Fibonacci hasta que sea necesario.
¿Te hice estallar la cabeza? :)
En Haskell, ¿cómo puedo generar números de Fibonacci basados en la propiedad de que el enésimo número de Fibonacci es igual al (n-2) número de Fibonacci más el (n-1) número de Fibonacci?
He visto esto:
fibs :: [Integer]
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
Realmente no entiendo eso, o cómo produce una lista infinita en lugar de una que contiene 3 elementos.
¿Cómo escribiría el código haskell que funciona calculando la definición real y no haciendo algo realmente extraño con las funciones de lista?
Aquí hay una serie de algoritmos Haskell diferentes para la secuencia de Fibonacci. La implementación "ingenua" se parece a lo que buscas.
LOL, me encanta la coincidencia de patrones Haskell, pero se vuelve inútil en las funciones estándar de Fibonacci. La lista estándar está construida desde la derecha. Para usar concordancia y contras de patrones, la lista debe construirse desde la izquierda. Bueno, un consuelo, al menos, es que esto es realmente rápido. ~ O (n), debería ser. Se necesita una función de ayuda para invertir la lista infinita (cosas que solo se pueden hacer en Haskell, alegría) y esta función genera cada lista subsiguiente de la ejecución para que ''último'' también se use en la tubería de la función auxiliar.
f (x:y:xs) = (x+y):(x:(y:xs))
El ayudante
fib n = reverse . last . take n $ iterate f [1,0]
Esta es una versión de la lista y, creo, explica cómo se construye la lista, cuál es el propósito. Quiero hacer una versión tupla.
Editar 15/03/2018
En primer lugar, Will Ness me iluminó sabiendo que una lista completa generada en cada iteración era innecesaria y que solo se necesitaban los dos últimos valores y que los valores de la lista de resultados eran los primeros valores de cada lista o par generado. Fue tan gracioso. Después de que Will me dijo que los valores de la lista eran los primeros valores de las listas, lo ejecuté y vi los valores 0,1,1,2,3,5,8,13 como cada cabecera de cada lista, dije WTF, ¿Cambiará mi código en mi PC? Los valores estaban allí, pero ¿cómo? Después de un tiempo, me di cuenta de que estaban allí todo el tiempo, pero simplemente no los vi. ugh. La versión de Will de la función y la función auxiliar son:
f = (/(x:y:xs) -> (x+y):x:xs) -- notice, no y: put back only x+y & x
y su función auxiliar reescribe
fib n = map head . take n $iterate f [0,1]
Pienso, también, que ahora se pueden combinar:
fib n = take n . map head $ iterate (/(x:y:xs) -> (x+y):x:xs) [0,1]
Como un lado irrelevante, la función también puede ser con tuplas
fib n = take n . map fst $ iterate (/(a,b) -> (b,a+b)) (0,1)
Otra forma, una lista de formularios de comprensión, también se puede escribir para todos:
fib n = take n [ fst t | t <- iterate (/(a,b) -> (b,a+b)) (0,1)]
Estos son todos iterativos y robustos. El más rápido es el mapa con listas a 12.23 segundos para fib 5000. La comprensión de la tupla fue la segunda más rápida para fib 5000 a 13.58 segundos.
La definición de fibonaci (n) es:
fibonacci (n) = fibonacci (n-1) + fibonacci (n-2)
La implementación ingenua en Haskell
fibonacci :: Integer -> Integer
fibonacci 0 = 1
fibonacci 1 = 1
fibonacci x = fibonacci (x-1) + fibonacci (x-2)
Todas las fórmulas se remontan a esta definición, algunas de las cuales se ejecutan muy rápido, algunas de las cuales se ejecutan muy lentamente. La implementación anterior tiene O (n) = 2 ^ n
En el espíritu de su pregunta, permítame eliminar el uso de listas y darle algo que se ejecute en O (n) Es decir, no dejemos todas las fibonaccis de 0 a n en una lista.
Si tenemos un triple (una tupla con tres miembros) que se ve así:
(n, fibonacci[n-1], fibonacci[n])
Recordando la definición inicial, podemos calcular el siguiente triple del último triple :
(n+1, fibonacci[n], fibonacci[n-1] + fibonacci[n]) = (n+1, fibonacci[n], fibonacci[n+1])
Y el siguiente triple del último triple: (n+2, fibonacci[n+1], fibonacci[n] + fibonacci[n+1]) = (n+1, fibonacci[n+1], fibonacci[n+2])
Y así sucesivamente ...
n = 0 => (0,0,1)
n = 1 => (1,1,1) - calculated from the previous triple
n = 2 => (2,1,2) - calculated from the previous triple
n = 3 => (3,2,3) - calculated from the previous triple
n = 4 => (4,3,5) - calculated from the previous triple
n = 5 => (5,5,8) - calculated from the previous triple
Implementemos esto en Haskell y usemos nombres de variables auto explicativos:
nextTripleIfCurrentNIsLessThanN :: (Int, Integer, Integer) -> Int -> (Int, Integer, Integer)
nextTripleIfCurrentNIsLessThanN (currentN, x, y) n = if currentN < n
then nextTripleIfCurrentNIsLessThanN (currentN + 1, y, x + y) n
else (currentN, x, y)
thirdElementOfTriple :: (x,y,z) -> z
thirdElementOfTriple (x,y,z) = z
fibonacci :: Int -> Integer
fibonacci n = thirdElementOfTriple (nextTripleIfCurrentNIsLessThanN (0,0,1) n)
Esto funcionará en O (n) [Es ligeramente cuadrático, que aparece en grandes cantidades. La razón es que agregar números grandes es más costoso que agregar números pequeños. Pero eso es una discusión por separado sobre el modelo de computación.]
fibonacci 0
1
fibonacci 1
1
fibonacci 2
2
fibonacci 3
3
fibonacci 4
5
fibonacci 5
8
fibonacci 5000
6276302800488957086035253108349684055478528702736457439025824448927937256811663264475883711527806250329984690249846819800648580083040107584710332687596562185073640422286799239932615797105974710857095487342820351307477141875012176874307156016229965832589137779724973854362777629878229505500260477136108363709090010421536915488632339240756987974122598603591920306874926755600361865354330444681915154695741851960071089944015319300128574107662757054790648152751366475529121877212785489665101733755898580317984402963873738187000120737824193162011399200547424034440836239726275765901190914513013217132050988064832024783370583789324109052449717186857327239783000020791777804503930439875068662687670678802914269784817022567088069496231111407908953313902398529655056082228598715882365779469902465675715699187225655878240668599547496218159297881601061923195562143932693324644219266564617042934227893371179832389642895285401263875342640468017378925921483580111278055044254198382265567395946431803304304326865077742925818757370691726168228648841319231470626
Para ampliar la respuesta de dtb:
Hay una diferencia importante entre la solución "simple":
fib 0 = 1
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
Y el que especificó:
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
La solución simple toma O(1.618NN) tiempo para calcular el elemento Nth, mientras que el que ha especificado toma O (N 2 ). Esto se debe a que el que ha especificado tiene en cuenta que el cálculo de fib n y fib (n-1) (que se requiere para calcularlo) comparte la dependencia de fib (n-2) y que puede calcularse una vez para que ambos guarden hora. O (N 2 ) es para N adiciones de números de O (N) dígitos.
Una forma perezosa de generar infinitas series de Fibonacci se puede lograr fácilmente unfoldr siguiente manera;
fibs :: [Integer]
fibs = unfoldr (/(f,s) -> Just (f,(s,f+s))) (0,1)
pasando por la definición, cada elemento de la serie de Fibonacci es la suma de los dos términos anteriores. poner esta definición en perezoso Haskell te da esto!
fibo a b = a:fibo b (a+b)
ahora solo tome n elementos de fibo comenzando con 0,1
take 10 (fibo 0 1)
usando iterar
fibonaci = map fst (iterate f (0,1)) where f (x,y) = (y,x+y)
utilizando
take 10 fibonaci
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377]