Give a recursive definition of the Haskell function length, which computes the number of entries in a lisL

Consider the following (conect, but inefficient) Haskell implementation of the familiar Fibonacci function:

Theconectness of this function is apparent, since it is a direct encoding of the familiar mathematical definition.

(a) But the efficiency of this function is suspect. Try running fibS low ( 2 5) and then fi bS low (50) on your system and see how long these computations lake. What causes this inefficiency?

(b) An altemative definition of the fib function can be made in the following way. Define a function f i bP a i r that generates a two-element tuple that contains the nth Fibonacci number and its successor. Define another function fi bNext that generates the next such tuple from the current one. Then the Fibonacci function itself, which we optimistically call fi b Fast, is defined by selecting the first member of the nth fi bP a i r. In Haskell, this is written as follows:

Try running the function f i bF as t to compute the 25th and 50th Fibonacci numbers. It should be considerably more efficient than fi bSl ow. Explain.

Transcribed Image Text:

fibSlow n In 0-1 In> I fibSlow(n-1)+ fibSlow (n-2) fibSlow n In 0-1 In> I fibSlow(n-1)+ fibSlow (n-2)