Given the definition of the Haskell function len in this chapter, prove by induction the following:

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

The correctness of this function can be proved quickly, since it is a direct transcription of the familiar mathematical definition below, and since the Haskell type Integer is an infinite set:

Give an induction proof of conectness for fl bSl ow.

Transcribed Image Text:

len (reverse xs) - len xs len (reverse xs) - len xs