Calculating fib using List construction in Haskell - speed differences

Question

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)

@sepp2k just updated the question with timings for comparison — James Crowley, Apr 06 '14 at 21:14
Try reloading ghci and running `fibNth2` first and then run `fibNth`. I suspect that you will find that the second function called always runs faster. — David Young, Apr 06 '14 at 21:17
@DavidYoung you are correct. Simple explanations are the best! Is there no advantage to the second version of the function? (which was listed in the book, instead of the first) — James Crowley, Apr 06 '14 at 21:25

score 7 · Accepted Answer · edited May 23 '17 at 11:57

7

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.

edited May 23 '17 at 11:57

Community

1
1

answered Apr 06 '14 at 21:17

András Kovács

29,931
3
53
99

Hah, weird. I could have sworn the first was slower (repeatedly), but with the timing on it would seem you are most correct! Thanks. I was thrown off because the author gave the second more complicated version and I wasn't sure why. – James Crowley Apr 06 '14 at 21:24

Calculating fib using List construction in Haskell - speed differences

1 Answers1