Okay, apparently I didn't quite think this one through. I wasn't claiming that GHC memoizes values, but it does memoize thunks. I thought this algorithm would be getting some benefit from that, but having inserted some trace statements, I was apparently wrong.

Here's a version that really is memoized:

 import Control.Parallel
 import Control.Monad
 import Text.Printf

 cutoff = 35 
 fibs = [ fib n | n <- [0..] ]

 fib' :: Int -> Integer
 fib' 0 = 0
 fib' 1 = 1
 fib' n = fibs !! (n-1) + fibs !! (n-2)

 fib :: Int -> Integer
 fib n | n < cutoff = fib' n
       | otherwise  = r `par` (l `seq` l + r)
  where
     l = fibs !! (n-1)
     r = fibs !! (n-2)

 main = forM_ [0..45] $ \i ->
             printf "n=%d => %d\n" i (fib i)