Description

• Files you should submit: Fibonacci.hs
This week we learned about Haskell’s lazy evaluation. This homework assignment will focus on one particular consequence of lazy evaluation, namely, the ability to work with infinite data structures.
Fibonacci numbers
The Fibonacci numbers Fn are defined as the sequence of integers, beginning with 0 and 1, where every integer in the sequence is the sum of the previous two. That is,
F = 0
F1 = 1
Fn = Fn 1+ Fn 2 (n 2)
For example, the first fifteen Fibonacci numbers are
Exercise 1
Translate the above definition of Fibonacci numbers directly into a
recursive function definition of type
fib :: Integer -> Integer
so that fib n computes the nth Fibonacci number Fn.
Now use fib to define the infinite list of all Fibonacci numbers,
fibs1 :: [Integer]
(Hint: You can write the list of all positive integers as [0..].)
Try evaluating fibs1 at the ghci prompt. You will probably get
bored watching it after the first 30 or so Fibonacci numbers, because
fib is ridiculously slow. Although it is a good way to define the Fi-
bonacci numbers, it is not a very good way to compute them—in order

• If we extend the Fibonacci sequence backwards (using the appropriate subtraction), we find . . . , 8, 5, 3, 2, 1, 1, 0, 1, 1, 2, 3, 5, 8 . . .
0 is the obvious center of this pattern, so if we let F0 = 0 then Fn and F n are either equal or of opposite signs, depending on the parity of n. If F0 = 1 then everything is off by two.
• If F0 = 0 then we can prove the
lovely theorem “If m evenly divides n if and only if Fm evenly divides Fn.” If F0 = 1 then we have to state this as “If m evenly divides n if and only if Fm 1 evenly divides Fn 1.” Ugh.

to compute Fn it essentially ends up adding 1 to itself Fn times! For example, shown at right is the tree of recursive calls made by evaluating fib 5.
As you can see, it does a lot of repeated work. In the end, fib has running time O(Fn), which (it turns out) is equivalent to O(jn), where j is the “golden ratio”. That’s right, the running time is exponential in n. What’s more, all this work is also repeated from each element of the list fibs1 to the next. Surely we can do better.
Exercise 2
When I said “we” in the previous sentence I actually meant “you”. Your task for this exercise is to come up with more efficient implementation. Specifically, define the infinite list fibs2 :: [Integer]
so that it has the same elements as fibs1, but computing the first n elements of fibs2 requires only O(n) addition operations. Be sure to use standard recursion pattern(s) from the Prelude as appropriate.
Streams
In particular, streams are like lists but with only a “cons” constructor— whereas the list type has two constructors, [] (the empty list) and (:) (cons), there is no such thing as an empty stream. So a stream is simply defined as an element followed by a stream.

Of course there are several billion Haskell implementations of the Fibonacci numbers on the web, and I have no way to prevent you from looking at them; but you’ll probably learn a lot more if you try to come up with something yourself first.

Exercise 3
• Define a data type of polymorphic streams, Stream.
• Write a function to convert a Stream to an infinite list, streamToList :: Stream a -> [a]
• To test your Stream functions in the succeeding exercises, it will be useful to have an instance of Show for Streams. However, if you put deriving Show after your definition of Stream, as one usually does, the resulting instance will try to print an entire Stream—which, of course, will never finish. Instead, you should make your own instance of Show for Stream,
instance Show a => Show (Stream a) where
show …
which works by showing only some prefix of a stream (say, the
first 20 elements).
Exercise 4
Let’s create some simple tools for working with Streams.
• Write a function streamRepeat :: a -> Stream a
which generates a stream containing infinitely many copies of the given element.
• Write a function streamMap :: (a -> b) -> Stream a -> Stream b which applies a function to every element of a Stream.
• Write a function streamFromSeed :: (a -> a) -> a -> Stream a
which generates a Stream from a “seed” of type a, which is the first element of the stream, and an “unfolding rule” of type a -> a which specifies how to transform the seed into a new seed, to be used for generating the rest of the stream.
Exercise 5
Now that we have some tools for working with streams, let’s create a few:
• Define the stream nats :: Stream Integer
which contains the infinite list of natural numbers 0, 1, 2, . . .
• Define the stream ruler :: Stream Integer which corresponds to the ruler function
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, . . .
divides n. Hint: define a function
interleaveStreams which alternates the elements from two streams. Can you use this function to implement ruler in a clever way that does not have to do any divisibility testing?
Fibonacci numbers via generating functions (extra credit)
This section is optional but very cool, so if you have time I hope you will try it. We will use streams of Integers to compute the Fibonacci numbers in an astounding way.
The essential idea is to work with generating functions of the form a0+ a1x + a2x2+ ··· + anxn + . . .
where x is just a “formal parameter” (that is, we will never actually substitute any values for x; we just use it as a placeholder) and all the coefficients ai are integers. We will store the coefficients a0, a1, a2, . . . in a Stream Integer.
Exercise 6 (Optional)
• First, define x :: Stream Integer by noting that x = 0 + 1x + 0x2+ 0x3+ . . . .
• Define an instance of the Num type class for Stream Integer.

Note that you will have to add

Here’s what should go in your Num instance:
– You should implement the fromInteger function. Note that n = n + 0x + 0x2+ 0x3+ . . . .
– You should implement negate: to negate a generating function, negate all its coefficients.
– You should implement (+), which works like you would expect:
(a0 + a1x + a2x2 + . . . )+(b0 + b1x + b2x2 + . . . ) = (a0 + b0)+ (a1+ b1)x +(a2+ b2)x2+ . . .
– Multiplication is a bit trickier. Suppose A = a0 + xA0 and B = b0 + xB0 are two generating functions we wish to multiply.
We reason as follows:
AB = (a0+ xA0)B
= a0B + xA0B
= a0(b0+ xB0)+ xA0B
= a0b0+ x(a0B0 + A0B)
That is, the first element of the product AB is the product of the first elements, a0b0; the remainder of the coefficient stream (the part after the x) is formed by multiplying every element in B0 (that is, the tail of B) by a0, and to this adding the result of multiplying A0 (the tail of A) by B.
{-# LANGUAGE FlexibleInstances #-} to the top of your .hs file in order for this instance to be allowed.
Note that there are a few methods of the Num class I have not told you to implement, such as abs and signum. ghc will complain that you haven’t defined them, but don’t worry about it. We won’t need those methods. (To turn off these warnings you can add
{-# OPTIONS_GHC -fno-warn-missing-methods #-} to the top of your file.)
If you have implemented the above correctly, you should be able to evaluate things at the ghci prompt such as
*Main> x^4
*Main> (1 + x)^5
*Main> (x^2 + x + 3) * (x – 5)
• The penultimate step is to implement an instance of the Fractional class for Stream Integer. Here the important method to define is division, (/). I won’t bother deriving it (though it isn’t hard), but
it turns out that if A = a0+ xA0 and B = b0+ xB0, then A/B = Q, where Q is defined as
Q = (a0/b0)+ x((1/b0)(A0 QB0)).
That is, the first element of the result is a0/b0; the remainder is formed by computing A0 QB0 and dividing each of its elements by b0.
Of course, in general, this operation might not result in a stream of Integers. However, we will only be using this instance in cases where it does, so just use the div operation where appropriate.
• Consider representing the Fibonacci numbers using a generating function,
F(x) = F0+ F1x + F2x2+ F3x3+ . . .
Notice that x + xF(x)+ x2F(x) = F(x):
x
F0x + F1x2 + F2x3 + F3x4 + . . .
F0x2 + F1x3 + F2x4 + . . .
0 + x + F2x2 + F3x3 + F4x4 + . . .
Thus x = F(x) xF(x) x2F(x), and solving for F(x) we find that
x
F(x) = 1 x x2 .
Translate this into an (amazing, totally sweet) definition fibs3 :: Stream Integer

Fibonacci numbers via matrices (extra credit)
It turns out that it is possible to compute the nth Fibonacci number with only O(log n) (arbitrary-precision) arithmetic operations. This section explains one way to do it.
Consider the 2 ⇥ 2 matrix F defined by
F .
Notice what happens when we take successive powers of F (see http://en.wikipedia.org/wiki/Matrix_multiplication if you forget how matrix multiplication works):
F
F
F
F
Curious! At this point we might well conjecture that Fibonacci numbers are involved, namely, that
Fn
for all n 1. Indeed, this is not hard to prove by induction on n.
The point is that exponentiation can be implemented in logarithmic time using a binary exponentiation algorithm. The idea is that to compute xn, instead of iteratively doing n multiplications of x, we compute
xnn even
😡 · (x( 1)/2)2 n odd
where xn/2 and x(n 1)/2 are recursively computed by the same method. Since we approximately divide n in half at every iteration, this method requires only O(log n) multiplications.
The punchline is that Haskell’s exponentiation operator (^) already uses this algorithm, so we don’t even have to code it ourselves!
Exercise 7 (Optional)
• Create a type Matrix which represents 2 ⇥ 2 matrices of Integers. • Make an instance of the Num type class for Matrix. In fact, you only have to implement the (*) method, since that is the only one we will use. (If you want to play around with matrix operations a bit more, you can implement fromInteger, negate, and (+) as well.)

Don’t worry about the warnings telling you that you have not implemented the

• We now get fast (logarithmic time) matrix exponentiation for free, since (^) is implemented using a binary exponentiation algorithm in terms of (*). Write a function fib4 :: Integer -> Integer
other methods. (If you want to disable the warnings you can add
{-# OPTIONS_GHC -fno-warn-missing-methods #-} to the top of your file.)

which computes the nth Fibonacci number by raising F to the nth power and projecting out Fn (you will also need a special case for zero). Try computing the one millionth or even ten millionth Fibonacci number.

On my computer the millionth Fibonacci number takes only 0.32 seconds to compute but more than four seconds to print on the screen—after all, it has just over two hundred thousand digits.