Fibonacci numbers with initial two values as parameters

Question

I have been trying to make a infinite fibonacci list producing function that can take first 2 values as parameters.

Without specifying the first two values it is possible like this

fib = 1 : 1 : zipWith (+) fib (tail fib)

Suppose I wanted to start the fibonacci sequence with 5 and 6 instead of 1,1 or 0,1 then I will have to change the above code. But when trying to make a lazy list generator in which I can specify the first 2 values of fibonacci sequence I am stumped. I came up with this but that didn't work.

fib a b = a : b : zipWith (+) fib (tail fib)

The problem is obvious. I am trying to convert the use of list in the hard-coded one. How can I solve that?

Answer 1

How about

fib a b = fibs where fibs = a : b : zipWith (+) fibs (tail fibs)

? Use the same method, but with your parameters in scope.

I should add that, in case you are tempted by

fib a b = a : b : zipWith (+) (fib a b) (tail (fib a b))  -- worth trying?

the where fibs version ensures that only one infinite stream is generated. The latter risks generating a fresh stream for each recursive invocation of fib. The compiler might be clever enough to spot the common subexpression, but it is not wise to rely on such luck. Try both versions in ghci and see how long it takes to compute the 1000th element.

Answer 2

The simplest way to do that is:

fib a b = a: fib b (a+b)

This stems from the inductive definition of the Fibonacci series: suppose we have a function that can produce a stream of Fibonacci numbers from F_i onwards, given F_i and F_i+1. What could that function look like? Well, F_i is given, and the rest of the stream can be computed using this function to produce a stream of Fibonacci numbers from F_i+1 onwards, if we can provide F_i+1 and F_i+2. F_i+1 is given, so we only need to work out F_i+2. The definition of series gives us F_i+2=F_i+F_i+1, so, there.