Polymorphism and memoization interact in strange ways.

memoizing_fib.hs

import Debug.Trace


noisy0 :: () -> Int
noisy0 () = trace "eval" 0

main = do print (let x = ( noisy0 ()
                         , fst x)
                  in x)                -- evals noisyMempty once
          print (( noisy0 ()
                 , fst ( noisy0 ()
                       , undefined)))  -- evals noisyMempty twice

I simplified the example tremendously, removing all references to fib, arrays, and memoization. What remains is a strange interaction between fix and polymorphism: when r = fix f has polymorphic type, its evaluation strategy is slightly different than that of r = f r. In particular, the fix version evaluates recursive sub-expressions once, while the non-fix version evaluates them twice.

Further simplification: the way in which fix is implemented matters. As you can see, using let allows sub-expressions to be reused. But why? I didn't expect let to be very magic.

further simplification: polymorphism is not needed in order to trigger the difference! I did have to turn noisyMempty into a function, though. Presumably, polymorphism was implicitly causing noisyMempty to behave like a function, whose argument is a type.

At last, an explanation! By repeatedly inlining and simplifying all the definitions, we see that the let-based version of fix has one call to noisy0 and one reference to it, while the non-let-based version has infinitely-many calls to noisy0, but only two of them need to be evaluated in order to compute the result.