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

[Dan Weston]

Brent Yorgey wrote:
> 
> On Nov 5, 2007 5:22 PM, gitulyar <gitulyar at gmail.com 
> <mailto: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

Close, I believe Brent actually meant

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

In any case, to answer your question more specifically, the memoization 
of *constants* is essential to the efficient implementation of lazy 
evaluation, and GHC certainly does it. You can just unroll the loop 
yourself to see. The following runs as fast as you'd expect:

fib00 = 0
fib01 = 1
fib02 = fib00 + fib01
fib03 = fib01 + fib02
fib04 = fib02 + fib03
fib05 = fib03 + fib04
fib06 = fib04 + fib05
fib07 = fib05 + fib06
fib08 = fib06 + fib07
fib09 = fib07 + fib08
fib10 = fib08 + fib09
fib11 = fib09 + fib10
fib12 = fib10 + fib11
fib13 = fib11 + fib12
fib14 = fib12 + fib13
fib15 = fib13 + fib14
fib16 = fib14 + fib15
fib17 = fib15 + fib16
fib18 = fib16 + fib17
fib19 = fib17 + fib18
fib20 = fib18 + fib19
fib21 = fib19 + fib20
fib22 = fib20 + fib21
fib23 = fib21 + fib22
fib24 = fib22 + fib23
fib25 = fib23 + fib24
fib26 = fib24 + fib25
fib27 = fib25 + fib26
fib28 = fib26 + fib27
fib29 = fib27 + fib28
fib30 = fib28 + fib29

main = putStrLn . show $ fib30

The key insight is that by pure syntactic transformation, you can create 
a graph of fib## that has only (##+1) nodes in it.

For a parametrized function fib n, no mere syntactic transformation can 
be so made. You actually have to evaluate the values (n-1) and (n-2) 
before you know how to wire the graph, putting it out of reach of a 
compile-time graph generator.