-- This program calculates the nth fibonacci number
-- using alrogirhtm 1A: binary recursion
--
-- compiled:  ghc -O -o f1a f1a.hs
-- executed: ./f1a n
--
module Main( main ) where
import System( getArgs )

-- Naive binary recursion: F(n) = F(n-1) + F(n-2) 
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

-- negative argument handling: F(-n) = F(n)*(-1)^(n+1)
f n = (if n<0 && even n then -1 else 1) * fib (abs n)

-- Function f_print  prints the n'th Fibonacci number
f_print n = print(show n ++ "th Fibonacci number is " ++ show (f n))

-- Function main is the entry point of the program
main = do
    args <- getArgs
    if (length args /= 1)
        then putStr "Usage: f1a <n>"
        else (f_print (read (head args)))
    putStr "\n"

-- This program calculates the nth fibonacci number
-- using alrogirhtm 1B: binary recursion with memoization
--
-- compiled:  ghc -O -o f1b f1b.hs /usr/lib64/memotrie-0.4.1/ghc-6.10.4/libHSMemoTrie-0.4.1.a
-- executed: ./f1b n
--
module Main( main ) where
import System( getArgs )
import Data.MemoTrie

-- Naive binary recursion: F(n) = F(n-1) + F(n-2) with 
-- using memotrie from http://haskell.org/haskellwiki/MemoTrie
fib :: Int -> Integer
fib 0 = 0
fib 1 = 1
fib n = mfib (n-2) + mfib (n-1) where mfib = memo fib

-- negative argument handling: F(-n) = F(n)*(-1)^(n+1)
f n = (if n<0 && even n then -1 else 1) * fib (abs n)

-- Function f_print  prints the n'th Fibonacci number
f_print n = print(show n ++ "th Fibonacci number is " ++ show (f n))

-- Function main is the entry point of the program
main = do
    args <- getArgs
    if (length args /= 1)
        then putStr "Usage: f1b <n>"
        else (f_print (read (head args)))
    putStr "\n"

-- This program calculates the nth fibonacci number
-- using alrogirhtm 2A: cached linear recursion (as lazy infinite list)
--
-- compiled:  ghc -O -o f2a f2a.hs
-- executed: ./f2a n
--
module Main( main ) where
import System( getArgs )
-- classic infinite list of Fibonacci numbers
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
-- another way to do this, neater but slower:
-- fibs = 0 : scanl (+) 1 fibs

-- negative argument handling: F(-n) = F(n)*(-1)^(n+1)
f n = (if n<0 && even n then -1 else 1) * fibs!!abs n
-- Function f_print  prints the n'th Fibonacci number
f_print n = print(show n ++ "th Fibonacci number is " ++ show (f  n))
-- Function main is the entry point of the program
main = do
    args <- getArgs
    if (length args /= 1)
        then putStr "Usage: f2a <n>"
        else (f_print (read (head args)))
    putStr "\n"

-- This program calculates the nth fibonacci number
-- using alrogirhtm 2B: linear recursion with accumulator
--
-- compiled:  ghc -O -o f2b f2b.hs
-- executed: ./f2b n
module Main( main ) where
import System( getArgs )

-- function f calculates the nth fibonacci number
-- using simple recursion with accumulators
fib a b 0     = a
fib a b (c+1) = fib (a+b) a c

-- negative argument handling: F(-n) = F(n)*(-1)^(n+1)
f n = (if n<0 && even n then -1 else 1) * fib 0 1 (abs n)

-- Function f_print  prints the n'th Fibonacci number
f_print n = print(show n ++ "th Fibonacci number is " ++ show (f  n))
-- Function main is the entry point of the program
main = do
    args <- getArgs
    if (length args /= 1)
        then putStr "Usage: f2b <n>"
        else (f_print (read (head args)))
    putStr "\n"

Haskell does not support non-recursive loops.
Rewriting this algorithm in recursion produces ALGORITHM 2B.

-- This program calculates the nth fibonacci number
-- using alrogirhtm 3A: matrix multiplication
--
-- compiled:  ghc -O -o f3a f3a.hs
-- executed: ./f3a n
module Main( main ) where
import List( transpose )
import System( getArgs )

-- function f calculates the nth fibonacci number
-- by raising the [1,1],[1,0] matrix to n-1 power
fib 0 = 0
fib (n+1) = let [[a,_],_] = power mm u t n in a
            where u = [[1,0],[0,1]]
                  t = [[1,1],[1,0]]

-- negative argument handling: F(-n) = F(n)*(-1)^(n+1)
f n = (if n<0 && even n then -1 else 1) * fib (abs n)

-- matrix multiplication, using Lists
-- Using Arrays, as in Gentle Introduction to Haskell, is certainly faster, but this is
-- good enough for our 2x2 matrices and compares neatly to other functional languages.
mm a b  = [[sum$zipWith (*) row col | col <- transpose a] | row <-b]

-- tail-recursive generic exponentiation by repeated squaring
-- it raises b to the nth power using multiplication f and unity u
power f u b n | n <= 0 = u
power f u b n | even n = power f  u      (f b b) (n `div` 2)
power f u b n | odd n  = power f (f u b) (f b b) (n `div` 2)

-- Function f_print  prints the n'th Fibonacci number
f_print n = print(show n ++ "th Fibonacci number is " ++ show (f  n))
-- Function main is the entry point of the program
main = do
    args <- getArgs
    if (length args /= 1)
        then putStr "Usage: f3a <n>"
        else (f_print (read (head args)))
    putStr "\n"

-- This program calculates the nth fibonacci number
-- using alrogirhtm 3B: fast recursion
--
-- compiled:  ghc -O -o f3b f3b.hs
-- executed: ./f3b n
module Main( main ) where
import System( getArgs )

-- function fib calculates the nth fibonacci number according to
-- the recurrent relationship: 
-- F(2n-1) = F(n-1)^2 + F(n)^2
-- F(2n) = (2F(n-1) + F(n))F(n)
-- 
-- in this function, k1 = F(n-1), k2 = F(n), k3 = F(n+1)
fib 0 = (0, 0)
fib 1 = (1, 0)
fib n | even n = ( (k1+k3)*k2, k1^2+k2^2 )
      | odd n  = ( k3^2+k2^2, (k1+k3)*k2 )
      where (k2, k1) = fib$div n 2
            k3  = k2 + k1
        
-- negative argument handling: F(-n) = F(n)*(-1)^(n+1)
f n = (if n<0 && even n then -1 else 1) * (fst$fib$abs n)

-- Function f_print  prints the n'th Fibonacci number
f_print n = print(show n ++ "th Fibonacci number is " ++ show (f  n))
-- Function main is the entry point of the program
main = do
    args <- getArgs
    if (length args /= 1)
        then putStr "Usage: f3b <n>"
        else (f_print (read (head args)))
    putStr "\n"

-- This program calculates the nth fibonacci number
-- using alrogirhtm 3C: Binet's formula with rounding
--
-- compiled:  ghc -O -o f3c f3c.hs /usr/lib64/numbers-2009.8.9/ghc-6.10.4/libHSnumbers-2009.8.9.a
-- executed: ./f3c n
--
module Main( main ) where
import System( getArgs )
import Data.Number.CReal

-- function fib calculates nth fibonacci number as the closest integer to phi^n/sqrt(5)
-- this function uses CReal numbers from http://hackage.haskell.org/package/numbers
fib n = round (phi**x/(sqrt 5))
        where phi = (1+sqrt 5)/2
              x = (fromInteger n)::CReal

-- negative argument handling: F(-n) = F(n)*(-1)^(n+1)
f n = (if n<0 && even n then -1 else 1) * fib (abs n)

-- Function f_print  prints the n'th Fibonacci number
f_print n = print(show n ++ "th Fibonacci number is " ++ show (f n))

-- Function main is the entry point of the program
main = do
    args <- getArgs
    if (length args /= 1)
        then putStr "Usage: f3c <n>"
        else (f_print (read (head args)))
    putStr "\n"