Brent Yorgey wrote:
On Nov 5, 2007 5:22 PM, gitulyar <[EMAIL PROTECTED]
<mailto:[EMAIL PROTECTED]>> 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.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
