Haskell – Fibonacci sequence in haskell returning all the values

fibonaccihaskell

I need help for my assignment using haskell which return a list up to the nth number in the Fibonacci sequence.

Main> fib 5
[0,1,1,2,3,5]
Main> fib 15
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610]

I understand this

fib::Int->Int
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

but I don't know how to produce list that containing all the value up to the nth number.

Thank you

Best Answer

There are a few cool ways to do it, first the simplest

fib::Int->Int
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
fibList n = map fib [1..n]

or we can merge this into one

fib::Int->[Int]
fib 0 = [0]
fib 1 = [1, 0]
fib n = (head (fib (n-1)) + head (fib (n-2))) : fib (n-1)

So here we're just combining the list building with the recursion. Now we take a step towards the crazy

fib n = take n fiblist
  where fiblist = 0:1:(zipWith (+) fiblist (tail fiblist))

Here fiblist is an infinite list of Fibonacci numbers. All we're doing is grabbing the appropriate amount. This is possible because Haskell is "lazy". If you're new to Haskell, just smile and nod.

Lastly, for kicks and giggles

fib = flip take . fix $ \f -> 0 : 1 : (zipWith (+) f (tail f))

This is the same of above except point-free and with a fixed point instead of recursion.

Again if you're new to haskell, the first 2 are a little easier to grok, come back to the last 2 in a few weeks :)

Write Fib sequence formula to infinite

In math, it's given in a recursive form:

$fibonacci from wikipedia$

In programming, infinite doesn't exist. You can use a recursive form translating the math form directly in your language, for example in Python it becomes:

def F(n):
    if n == 0: return 0
    elif n == 1: return 1
    else: return F(n-1)+F(n-2)

Try it in your favourite language and see that this form requires a lot of time as n gets bigger. In fact, this is O(2ⁿ) in time.

Go on on the sites I linked to you and will see this (on wolfram):

This one is pretty easy to implement and very, very fast to compute, in Python:

from math import sqrt
def F(n):
    return ((1+sqrt(5))**n-(1-sqrt(5))**n)/(2**n*sqrt(5))

An other way to do it is following the definition (from wikipedia):

The first number of the sequence is 0, the second number is 1, and each subsequent number is equal to the sum of the previous two numbers of the sequence itself, yielding the sequence 0, 1, 1, 2, 3, 5, 8, etc.

If your language supports iterators you may do something like:

def F():
    a,b = 0,1
    while True:
        yield a
        a, b = b, a + b

Display startNumber to endNumber only from Fib sequence.

Once you know how to generate Fibonacci Numbers you just have to cycle trough the numbers and check if they verify the given conditions.

Suppose now you wrote a f(n) that returns the n-th term of the Fibonacci Sequence (like the one with sqrt(5) )

In most languages you can do something like:

def SubFib(startNumber, endNumber):
    n = 0
    cur = f(n)
    while cur <= endNumber:
        if startNumber <= cur:
            print cur
        n += 1
        cur = f(n)

In python I'd use the iterator form and go for:

def SubFib(startNumber, endNumber):
    for cur in F():
        if cur > endNumber: return
        if cur >= startNumber:
            yield cur

for i in SubFib(10, 200):
    print i

My hint is to learn to read what you need. Project Euler (google for it) will train you to do so :P Good luck and have fun!

Best Answer

Related Solutions

Computational complexity of Fibonacci Sequence

Python – How to write the Fibonacci Sequence

Write Fib sequence formula to infinite

Display startNumber to endNumber only from Fib sequence.

Related Topic