[Haskell-cafe] Fibbonachi numbers algorithm work TOO slow.

[Brent Yorgey]

On Nov 5, 2007 5:22 PM, gitulyar <gitulyar at gmail.com> wrote:

>
> Please help me. I'm new in Haskell programming, but wrote some things in
> Scheme. I make so function:
>
> fib 1 = 1
> fib 2 = 2
> fib n = fib (n-1) + fib (n-2)
>
> And when I call "fib 30" it works about 5 seconds. As for me it's really
> TOO
> SLOW.
>
> Tell me please if I have something missed, maybe some compiler
> (interpretaitor) options (I use ghc 6.6.1).
>
> P.S. As I understand function "fib n" should be calculated one time. For
> example if I call "fib 30" compiler builds tree in which call function
> "fib
> 28" 2 times and so on. But as for lazy calculation principle it should be
> calculated just ones and then it's value is used for all other calls of
> this
> function with the same argument. But it seems that this principle doesn't

work in this algorithm.


Lazy evaluation is not the same thing as memoization.  This algorithm for
calculating fibonacci numbers is just as inefficient in Haskell as it is in
any other language.  Lazy evaluation has to do with *when* things get
executed, not saving the values of function calls to be used in place of
other calls with the same arguments.

For a more efficient Haskell implementation of fibonacci numbers, try

fibs :: [Integer]
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

fib n = fibs !! n

-Brent
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20071105/2fbb28c5/attachment-0001.htm