As sugggested by its name, the efficiency of the fl bS 1 ow function in Exercise 18.17 is suspect.

(a) Try mm1ing fi bSl ow( 25) and then fi bSl ow( 50) on your system and see how long these computations take. What causes this inefficiency?

(b) An alternative definition of the Fibonacci calculation can be made in the following way. Define a function fib P a i r that generates a two-element pair that contains the nth Fibonacci number and its successor. Define another function fi bNext that generates the next such tuple from the cmTent one. Then the Fibonacci function itself, optimistically named fi bFast, can be defined by selecting the first member of the nth fib P a i r. In Haskell, this is written as follows:

Tty mnnmg the function fib Fast to compute the 25th and 50th Fibonacci numbers. It should be considerably more efficient than fi bSl ow. Explain.

(c) Prove by induction that Vn 2: 0 :fibFast(n) =fihSlow(n).

> fibPair n 10-0 > In>0 > > fibNext (n.n) (n.afn) >fibfast nfst(fibPair(n)) - (1.1) fibNext(fibPair(n-1))