reuse/memoization of global polymorphic (class) values in Haskell

Question

I'm concerned with if and when a polymorphic "global" class value is shared/memoized, particularly across module boundaries. I have read this and this, but they don't quite seem to reflect my situation, and I'm seeing some different behavior from what one might expect from the answers.

Consider a class that exposes a value that can be expensive to compute:

{-# LANGUAGE FlexibleInstances, UndecidableInstances #-}

module A

import Debug.Trace

class Costly a where
  costly :: a

instance Num i => Costly i where
  -- an expensive (but non-recursive) computation
  costly = trace "costly!" $ (repeat 1) !! 10000000

foo :: Int
foo = costly + 1

costlyInt :: Int
costlyInt = costly

And a separate module:

module B
import A

bar :: Int
bar = costly + 2

main = do
  print foo
  print bar
  print costlyInt
  print costlyInt

Running main yields two separate evaluations of costly (as indicated by the trace): one for foo, and one for bar. I know that costlyInt just returns the (evaluated) costly from foo, because if I remove print foo from main then the first costlyInt becomes costly. (I can also cause costlyInt to perform a separate evaluation no matter what, by generalizing the type of foo to Num a => a.)

I think I know why this behavior happens: the instance of Costly is effectively a function that takes a Num dictionary and generates a Costly dictionary. So when compiling bar and resolving the reference to costly, ghc generates a fresh Costly dictionary, which has an expensive thunk in it. Question 1: am I correct about this?

There are a few ways to cause just one evaluation of costly, including:

• Put everything in one module.
• Remove the Num i instance constraint and just define a Costly Int instance.

Unfortunately, the analogs of these solutions are not feasible in my program -- I have several modules that use the class value in its polymorphic form, and only in the top-level source file are concrete types finally used.

There are also changes that don't reduce the number of evaluations, such as:

• Using INLINE, INLINABLE, or NOINLINE on the costly definition in the instance. (I didn't expect this to work, but hey, worth a shot.)
• Using a SPECIALIZE instance Costly Int pragma in the instance definition.

The latter is surprising to me -- I'd expected it to be essentially equivalent to the second item above that did work. That is, I thought it would generate a special Costly Int dictionary, which all of foo, bar, and costlyInt would share. My question 2: what am I missing here?

My final question: is there any relatively simple and foolproof way to get what I want, i.e., all references to costly of a particular concrete type being shared across modules? From what I've seen so far, I suspect the answer is no, but I'm still holding out hope.

Answer 1

Controlling sharing is tricky in GHC. There are many optimizations that GHC does which can affect sharing (such as inlining, floating things out, etc).

In this case, to answer the question why the SPECIALIZE pragma did not achieve the intended effect, let's look at the Core of the B module, in particular of the bar function:

Rec {
bar_xs
bar_xs = : x1_r3lO bar_xs
end Rec }

bar1 = $w!! bar_xs 10000000
--     ^^^ this repeats the computation. bar_xs is just repeat 1

bar =
  case trace $fCostlyi2 bar1 of _ { I# x_aDm -> I# (+# x_aDm 2) }
  --         ^^^ this is just the "costly!" string

That didn't work as we wanted. Instead of reusing costly, GHC decided to just inline the costly function.

So we have to prevent GHC from inlining costly, or the computation will be duplicated. How do we do that? You might think adding a {-# NOINLINE costly #-} pragma would be enough, but unfortunately specialization without inlining don't seem to work together well:

A.hs:13:3: Warning:
    Ignoring useless SPECIALISE pragma for NOINLINE function: ‘$ccostly’

But there is a trick to convince GHC to do what we want: we can write costly in the following way:

instance Num i => Costly i where
  -- an expensive (but non-recursive) computation
  costly = memo where
    memo :: i
    memo = trace "costly!" $ (repeat 1) !! 10000000
    {-# NOINLINE memo #-}
  {-# SPECIALIZE instance Costly Int #-}
-- (this might require -XScopedTypeVariables)

This allows us to specialize costly, will simultanously avoiding the inlining of our computation.