GHC: Are there consistent rules for memoization for calls with fixed values? : <p>In my quest to understand and harness GHC automatic memoization, I've hit a wall: when pure functions are called with fixed values like <code>fib 42</code>, they are sometimes fast and sometimes slow when called again. It varies if they're called plainly like <code>fib 42</code> or implicitly through some math, e.g. <code>(\x -&gt; fib (x - 1)) 43</code>. The cases have no seeming rhyme or reason, so I'll present them with the intention of asking what the logic is behind the behavior.</p>

<p>Consider a slow Fibonacci implementation, which makes it obvious when the memoization is working:</p>

<pre><code>slow_fib :: Int -&gt; Integer
slow_fib n = if n &lt; 2 then 1 else (slow_fib (n - 1)) + (slow_fib (n - 2))
</code></pre>

<p>I tested three basic questions to see if GHC (version 8.2.2) will memoize calls with fixed args:</p>

<ol>
<li>Can <code>slow_fib</code> access previous top-level calls to <code>slow_fib</code>?</li>
<li>Are previous results memoized for later non-trivial (e.g. math) top-level expressions?</li>
<li>Are previous results memoized for later identical top-level expressions?</li>
</ol>

<p>The answers seem to be:</p>

<ol>
<li>No</li>
<li>No</li>
<li>Yes [??]</li>
</ol>

<p>The fact that the last case works is very confusing to me: if I can reprint the result for example, then I should expect to be able to add them. Here's the code that shows this:</p>

<pre><code>main = do
  -- 1. all three of these are slow, even though `slow_fib 37` is 
  -- just the sum of the other two results. Definitely no memoization.
  putStrLn $ show $ slow_fib 35
  putStrLn $ show $ slow_fib 36
  putStrLn $ show $ slow_fib 37

  -- 2. also slow, definitely no memoization as well.
  putStrLn $ show $ (slow_fib 35) + (slow_fib 36) + (slow_fib 37)
  putStrLn $ show $ (slow_fib 35) + 1

  -- 3. all three of these are instant. Huh?
  putStrLn $ show $ slow_fib 35
  putStrLn $ show $ slow_fib 36
  putStrLn $ show $ slow_fib 37
</code></pre>

<hr>

<p>Yet stranger, doing math on the results worked when it's embedded in a recursive function: this fibonacci variant that starts at Fib(40):</p>

<pre><code>let fib_plus_40 n = if n &lt;= 0
  then slow_fib 40
  else (fib_plus_40 (n - 1)) + (fib_plus_40 (n - 2))
</code></pre>

<p>Shown by the following:</p>

<pre><code>main = do
  -- slow as expected
  putStrLn $ show $ fib_plus_40 0

  -- instant. Why?!
  putStrLn $ show $ fib_plus_40 1
</code></pre>

<p>I can't find any reasoning for this in any explanations for GHC memoization, which typically incriminate explicit variables (e.g. <a href="https://stackoverflow.com/questions/11466284/how-is-this-fibonacci-function-memoized">here</a>, <a href="https://stackoverflow.com/questions/34644761/haskell-memoization">here</a>, <a href="https://stackoverflow.com/questions/38167078/does-this-haskell-function-memoize">and here</a>). This is why I expected <code>fib_plus_40</code> to fail to memoize.</p>
