CODEWITHSUNDEEP
haskellfibonacci
James Crowley
James Crowley

Reputation: 4081

Calculating fib using List construction in Haskell - speed differences

If we've defined the following:

lazyFib x y = x:(lazyFib y (x + y))
fib = lazyFib 1 1

(from the 7 languages in 7 weeks book). Why does

fibNth x = head (drop (x-1) fib)

evaluate slower than 

fibNth2 x = head (drop (x-1) (take (x) fib)

? Clearly the second one terminates the infinite list as soon as required - but intuitively I expected the (head) call to terminate the evaluation the moment one item comes through the "drop", regardless of whether there was a take limit on fib? Can anyone explain?

(updated with timings for reference):

> :set +s
> fibNth 100000
259740693472217241661550340212759154148804853865176...
(1.16 secs, 458202824 bytes)
> fibNth2 100000
259740693472217241661550340212759154148804853865176....
(0.09 secs, 12516292 bytes)

Upvotes: 2

Views: 131

Answers (1)

András Kovács
András Kovács

Reputation: 30103

If you flip the order of the two functions in your source file or the interpreter, you would see that the second function is a lot faster.

The reason? fib is a top level value that gets evaluated only once. On the first call you evaluate it as far as needed, on the second call you just breeze through the list.

You can look at this SO question for notes on when such evaluation behaviour is to be expected. In a nutshell, values with non-polymorphic types are memoized, while polymorphic values and function applications are not.

Upvotes: 7

Related Questions