lazy vs ST

lazy_vs_st.hs

{-# LANGUAGE BangPatterns, ViewPatterns #-}
import System.Environment (getArgs)
import Control.Monad
import Control.Monad.ST
import Data.STRef
import GHC.Int

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

fib2 :: Int -> Integer
fib2 n = fst $ fib' n
  where fib' 0 = (1, 1)
        fib' n = sum $ fib' (n-1)
        sum (!a, !b) = (b, a + b)

fib3 :: Int -> Integer
fib3 n = runST $ do
    a <- newSTRef 1
    b <- newSTRef 1
    replicateM_ (n-1) $ do
        !a' <- readSTRef a
        !b' <- readSTRef b
        writeSTRef a b'
        writeSTRef b $! a'+b'
    readSTRef b

fib4 :: Int -> Integer
fib4 n = runST $ do
    a <- newSTRef 1
    b <- newSTRef 1
    replicateM_ (n-1) $ do
        !a' <- readSTRef a
        !b' <- readSTRef b
        if (a' > b')
        then writeSTRef b $! a'+b'
        else writeSTRef a $! a'+b'
    a'' <- readSTRef a
    b'' <- readSTRef b
    if a'' > b''
    then return a''
    else return b''

main = do
    [flag, read -> n] <- getArgs
    case flag of
        "1" -> print $ fib1 n
        "2" -> print $ fib2 n
        "3" -> print $ fib3 n
        "4" -> print $ fib4 n

---------------------------------------------------------------------
-- $ time python fib.py 100000 >/dev/null 
-- 
-- real	0m0.243s
-- user	0m0.230s
-- sys	0m0.010s
--
-- $ time ./fib 1 100000 >/dev/null 
-- 
-- real	0m0.397s
-- user	0m0.367s
-- sys	0m0.027s
--
-- $ time ./fib 2 100000 >/dev/null 
-- 
-- real	0m0.074s
-- user	0m0.070s
-- sys	0m0.003s
--
-- $ time ./fib 3 100000 >/dev/null 
-- 
-- real	0m0.058s
-- user	0m0.053s
-- sys	0m0.003s
--
-- $ time ./fib 4 100000 >/dev/null 
-- 
-- real	0m0.061s
-- user	0m0.060s
-- sys	0m0.000s
--
--
--
--
-- fib.py
-- import sys
-- def fib2(n):
--     a = b = 1
--     for i in range(n-1):
--         (a, b) = (b, a + b)
--     return b
-- 
-- if __name__ == '__main__':
--     print(fib2(int(sys.argv[1])))
---------------------------------------------------------------------