-- 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) with
-- negative argument handling: F(-n) = F(n)*(-1)^(n+1)
f n | n < 0 && rem n 2 == 0 = negate (fib (negate n))
    | n < 0 && rem n 2 /= 0 = fib (negate n)
    | otherwise = fib n
    where fib n | n  < 2    = n
                | otherwise = fib (n-1) + fib (n-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: f1a <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 )
-- fibs is the infinite list of Fibonacci numbers
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
-- function f calculates the nth fibonacci number
f n | n < 0 && rem n 2 == 0 = negate (f (negate n))
    | n < 0 && rem n 2 /= 0 = f (negate n)
    | otherwise = fibs!!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, implemented as
-- sub-function fib
f n | n < 0 && rem n 2 == 0 = negate (f (abs n))
    | otherwise = fib 0 1 (abs n) where
      fib a b c = if c<1 then a else fib (a+b) a (c-1)

-- 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.

module Main where
import List(transpose)
-- Function f returns the n'th Fibonacci number
-- It uses ALGORITHM 3A: MATRIX EQUATION
f n = head (head (mp [[1,1],[1,0]] n))
-- Function mm performs matrix multiplication.
-- I don't know the original author of this one-liner.
mm a b  = [[sum$zipWith (*) row col | col <- transpose a] | row <-b]
-- Function mp raises a matrix m into nth power (for n>0)
mp m n | n <= 1 = m
       | otherwise = if (mod n 2)==1 then mm (mm a a) m else mm a a
		             where a = mp m (div n 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 = f_print 1000000

module Main where
-- Function f returns the n'th Fibonacci number
-- It uses ALGORITHM 3B: FAST RECURSION
f n = fst (l n) where
   l n |  n<2 = (1,1)
       | n==2 = (2,1)
       |  n>2 = if (rem n 2)==1 then ( k1*(k1+k2)+k1*k2    ,  k1*k1+k2*k2    )
                                else ((l1+l2)*(l1+l2)+l1*l1, (l1+l2)*l1+l1*l2)
       where (k1,k2) = l (div (n-1) 2)
             (l1,l2) = l ((div n 2)-1)
-- 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 = f_print 500000

module Main where
-- Function f returns the n'th Fibonacci number
-- It uses ALGORITHM 3C: BINET'S FORMULA
f n = round((phi**(x+1)-(1-phi)**(x+1))/(sqrt 5))
	  where phi = (1+sqrt 5)/2
	        x = (fromInteger n)::Float
-- 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 = f_print 30