Fibonacci in haskell and CoffeeScript

blog_fibonacci.md

Here is the fibonacci sequence calculated in haskell (1 to 100):

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

prn = map fibo [1..100]

prn

and here it is in CoffeeScript

fibo = (n) ->
  if n is 0 or n is 1
    return n

  fibo(n-1) + fibo(n-2)

for i in [1..100]
    console.log fibo(i)

Both of these take forever to execute. Curiously the CoffeeScript version is an order of magnitude faster.

even just working it out for map fibo[20..20] would take 2.6million calls.

void Main()
{
    GetFib().Take(100).Dump();
    GetFib2(30).Dump();
    cnt.Dump();
}
int cnt;
long GetFib2(long n)
{
cnt++;
    if(n == 0)
        return 0;
    if(n ==1)
        return 1;

    return GetFib2(n-1) + GetFib2(n-2);
}
IEnumerable<long> GetFib()
{
    var n2 = 0L;
    var n1 = 1L;

    yield return n2;
    yield return n1;

    while(true)
    {
        var n0 = n1 + n2;
        yield return n0;
        n2 = n1;
        n1 = n0;
    }
}

Wonder about a function orientation solution.. dinner first

Faster imperative version:

fibo_imp = ->
  results = [0,1]
  for i in [1..100]
    next_term = results[i]+ results[i-1]
    results.push next_term
    console.log next_term

The haskell implementation using infinite lists is awesome :
http://en.literateprograms.org/Fibonacci_numbers_(Haskell)

The aforementioned fibonacci with haskell infinite lists:

fib :: Int -> Integer
fib n = fibs !! n
where
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

zipWith merges two lists (fibs and (tail fibs)) by applying a function (+). tail returns every element of a list after the first element.