Vikrant

Few days back I started playing with Haskell. It took a while to get into pure functional paradigm. Going in this new programing world was fascinating as well as frightening! Frightening!..yeah..because it was a shock for python/C/Java programmer to imagine programming without destructive updates, to see that once assigned you can’t reassign values to variables! And many more surprises, I could not find loops! Loops have to be programmed using recursion! But after getting in here one feels Aha…. to see that your 2-3 lines code can do wonders, while equivalent code in C++/Java code fails to give that kick. So my journey in this wonderland started with Fibonacci numbers. Recently learned functional paradigm instantly gave me easy answer

– Usual recursive fibonaci
fib 1 = 1
fib 2 = 1
fib n = fib (n-1) + fib (n-2)

it was fine till I asked for fib 30, the programme took hours to compute fib 100! oooolaaa, I did the mistake. Memories went back to initial programming lessons. A student programmer is always advised by master programmer that although recursion is beautiful, it is not efficient, always try to put your recursion in the from of iterative loop. But then there are no loops in Haskell! Through some iterations I reached to following piece of code

-- fibonacci sequesnce generator
fibseries fibs n =
if length fibs < n 
    then fibseries ((fibs!!0 + fibs!!1):fibs) n
    else fibs

-- efficient fibonacci
fibonacci n = 
head (fibseries [1,1] n)

and then soon I improved to following

fibonacci n = fib n 1 1
   where
      fib 1 a _ = a
      fib 2 _ b = b
      fib n a b = fib (n-1) b (a+b)

Anand had given me idea about infinite lists in lisp long back. That time i was surprised to see something infinite on a computer. Today I felt enlightened after using it!

-- infinite series!
fibs = 1 : 1 : [ a+b | (a,b) <- zip fibs (tail fibs) ]

last updated 2 years ago #