¿Generando números de Fibonacci en Haskell?

Siguiendo 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 le 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)

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 especificaste:

fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

La solución simple toma O (1.618^NN) tiempo para calcular el Enésimo elemento, mientras que el especificado toma O (N²). Esto se debe a que la que especificó tiene en cuenta que la computación fib n y fib (n-1) (que se requiere para calcularla) comparten la dependencia de fib (n-2), y que se puede calcular una vez para ahorrar tiempo. O(N²) es para N adiciones de números de O(N) dígitos.

Hay una serie de diferentes algoritmos de Haskell para la secuencia de Fibonacci aquí. La implementación "ingenua" se parece a lo que buscas.

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 que se ejecutan muy rápidamente, 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ítanme eliminar el uso de listas y darle algo que se ejecuta en O(n) Es decir, no mantengamos todos los fibonaccis de 0 a n en una lista.

Si tiene un triple (una tupla con tres miembros) que se parece a:

(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 autoexplicativos:

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 suavemente cuadrática que aparece en grandes números. La razón de esto es que agregar números grandes es más costoso que agregar números pequeños. Pero esa es una discusión separada 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

Una forma perezosa de generar series infinitas de Fibonacci se puede lograr fácilmente por unfoldr de la siguiente manera;

fibs :: [Integer]
fibs = unfoldr (\(f,s) -> Just (f,(s,f+s))) (0,1)

LOL, me encanta la coincidencia de patrones de Haskell, pero se vuelve inútil en las funciones estándar de Fibonacci. La lista estándar se construye desde la derecha. Para usar coincidencia de patrones y cons, la lista debe construirse desde la izquierda. Bueno, un consuelo, al menos, es que esto es muy rápido. -O (n), debería serlo. Se necesita una función auxiliar para revertir la lista infinita (cosas que solo puede hacer en Haskell, joy) y esta función genera cada lista posterior de la ejecución, por lo que 'last' también se usa en el canalización de funciones auxiliares.

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 lista y, creo, explica cómo se construye la lista, cuál es el propósito. Quiero hacer una versión de tupla.

Editar 15/3/2018

En primer lugar, Will Ness me iluminó con el conocimiento de que una lista completa que se generaba en cada iteración era innecesaria y que solo se necesitaban los dos últimos valores utilizados y que los valores para la lista de resultados eran los primeros valores de cada lista o par generado. Fue tan divertido. 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 cabeza 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 ayudante reescribir

fib n = map head . take n $iterate f [0,1]

Creo, también, que ellos ahora se puede combinar:

fib n = take n . map head $ iterate (\(x:y:xs) -> (x+y):x:xs) [0,1]

Como un aparte irrelevante, la función puede ser con tuplas, también

fib n = take n . map fst $ iterate (\(a,b) -> (b,a+b)) (0,1)

Otra forma, una forma de comprensión de lista, también se puede escribir para todos:

fib n = take n [ fst t | t <- iterate (\(a,b) -> (b,a+b)) (0,1)]

Todos estos son iterativos y robustos. El más rápido es el mapa con listas a 12.23 segundos para fib 5000. La comprensión de tupla fue la segunda más rápida para fib 5000 a 13.58 segundos.

Usando iteración

fibonaci = map fst (iterate f (0,1)) where f (x,y) = (y,x+y)

Usando

take 10 fibonaci

[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377]