[Haskell-cafe] Fibonacci numbers generator in Haskell

[Mathew Mills]

How about the closed form ;)

> -- fib x returns the x'th number in the fib sequence

> fib :: Integer -> Integer

> fib x = let phi = ( 1 + sqrt 5 ) / 2

>         in truncate( ( 1 / sqrt 5 ) * ( phi ^ x - phi' ^ x ) )


Seems pretty quick to me, even with sqrt and arbitrarily large numbers.


On 6/15/06 9:33 AM, "Vladimir Portnykh" <vportnykh at hotmail.com> wrote:

> Fibonacci numbers implementations in Haskell one of the classical examples.
> An example I found is the following:
> 
> fibs :: [Int]
> fibs = 0 : 1 : [ a + b | (a, b) <- zip fibs (tail fibs)]
> 
> To get the k-th number you do the following:
> Result = fibs !! k
> 
> It is elegant but creates a list of all Fibonacci numbers less than k-th,
> and the code is not very readable :).
> 
> I wrote my own Fibonacci numbers generator:
> 
> fib :: Int -> [Int]
> fib 0 = [0,0]
> fib 1 = [1,0]
> fib n = [sum prevFib, head prevFib] where a = fib (n - 1)
> 
> To get the k-th number you do the following:
> 
> result = head (fib k)
> 
> It does not generate full list of Fibonacci numbers, but keeps only 2
> previous numbers, and has only one recursive call.
> Because the list always has only 2 elements using the functions head and sum
> is a bit overkill.
> 
> Can we do better?
> 
> _________________________________________________________________
> Are you using the latest version of MSN Messenger? Download MSN Messenger
> 7.5 today! http://join.msn.com/messenger/overview
> 
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe