CODEWITHSUNDEEP
performancehaskellmonadsghcmemoization
user348716
user348716

Reputation:

How to control automatic memoisation in Haskell (GHC)?

Here's a small program that prints the first 40 fibonacci numbers thrice -

module Main where

fib :: Int -> Int
fib 1 = 1
fib 2 = 1
fib n = fib (n-1) + fib (n-2)

main :: IO ()
main = run >> run >> run
  where
    run = mapM_ (print . fib) [1..40]

If I compile it with ghc Main.hs, then the computational part of "run" is saved by GHC, so that executing run three times takes roughly the same time as running it once. This was quite a surprise! I was under the impression that monadic effects are not automatically memoised like this.

Also, if I compile it with ghc -O2 Main.hs then the memoisation is lost. (Atleast on my machine with ghc 7.10.3)

How can I predict when something is going to be memoised? Is there some documented rule of thumb somewhere? How does this play with unsafePerformIO and the like?

Upvotes: 1

Views: 97

Answers (1)

MathematicalOrchid
MathematicalOrchid

Reputation: 62818

Here run is a constant expression. So, like any other constant expression, it only gets evaluated once. Oh, the I/O actions it encodes get executed three times, but the expression (or rather, its subexpressions) evaluate only once.

My guess (and it's only a guess) is that not naming it would probably cause it to be re-evaluated each time. As in

main = do
  mapM_ (print . fib) [1..40]
  mapM_ (print . fib) [1..40]
  mapM_ (print . fib) [1..40]

would probably evaluate it multiple times. But I'm not 100% certain.

Now, if run was a function:

main = run 40 >> run 40 >> run 40
  where
    run n = mapM_ (print . fibs) [1..n]

then it would probably evaluate multiple times. I think GHC would avoid keeping the result of an arbitrary function call like that.

Upvotes: 1

Related Questions