By now, only fibState works. All other functions cause memory overflow.

gistfile1.hs

{-
    Different ways to implement Fibonacci function in Haskell.
    F(0)=0 F(1)=1 F(n)=F(n-1)+F(n-2) 
-}

import Control.Monad.State.Strict
import Control.Monad.ST.Strict
import Data.STRef.Strict
import System.TimeIt

-- Naive recursive implementation. Very slow.
fibNaive :: Int -> Int
fibNaive 0 = 0
fibNaive 1 = 1
fibNaive n = fibNaive (n - 1) + fibNaive (n - 2)

-- Lazy evaluation.
fibLazy :: Int -> Int
fibLazy = (!!) fiblist where fiblist = 0:1:zipWith (+) fiblist (tail fiblist)

-- Memoization with a list. Also works in a strict language.
fibList :: Int -> Int
fibList = head . makelist where
    makelist 0 = [0]
    makelist 1 = [1,0]
    makelist k = head nextlist + head (tail nextlist):nextlist where nextlist = makelist $ k - 1

-- Iteration with a State monad. Looks like imperative, but purely functional.
fibState :: Int -> Int
fibState n = flip evalState (0,1) $ do
    forM_ [1..n] $ const $ do
        (a,b) <- get
        put (b,a+b)
    (a,_) <- get
    return a

-- Iteration with an ST monad. In-place memory updates happen under the hood.
fibST :: Int -> Int
fibST n = runST $ do
    ref <- newSTRef (0,1)
    forM_ [1..n] $ const $ do
        (a,b) <- readSTRef ref
        writeSTRef ref (b,a+b)
    (a,_) <- readSTRef ref
    return a

fibST' :: Int -> Int
fibST' n = runST $ do
    ref <- newSTRef ((0,0,1)::(Int,Int,Int))
    let loop = do
        (i,a,b) <- readSTRef ref
        if i==n then return a else do
            writeSTRef ref (i+1,b,a+b)
            loop
    loop

main :: IO ()
main = timeIt $ print $ fibState 1000000000

Now we know that adding bang patterns can fix the memory leak.