GHC inlines past lambda in do-notation
a friend of mine discovered this weird behaviour:
The program, when run on the attached file, takes quite some time.
import System.IO import Control.Monad import qualified Data.Map as M main :: IO () main = do n <- read `fmap` getLine q <- read `fmap` getLine mts <- replicateM n $ do [a,b] <- words `fmap` getLine return (a,b) let mtdb2 = M.fromList mts --M.null mtdb2 `seq` return () replicateM_ q $ do a <- getLine print $ M.lookup a mtdb2 return ()
But if I uncomment the use of
mtdb2 outside the replicate, it runs fast. My conclusion is that GHC inlines
mtdb2 into the body of the loop, repeating the construction of the map over and over.
forM [1..q] $ \_ -> do is used instead, this does not happen – probably because GHC does not inline past that lambda.
(I didn’t attempt to understand the core yet)