'Share' or 'cache' an expression parameterized by only ambiguous types?

Question

I have a tricky question;

So, I know that GHC will ‘cache’ (for lack of a better term) top level definitions and only compute them once, e.g. :

myList :: [Int]
myList = fmap (*10) [0..10]

Even if I use myList in several spots, GHC notices the value has no params, so it can share it and won’t ‘rebuild’ the list.

I want to do that, but with a computation which depends on a type-level context; a simplified example is:

dependentList :: forall n. (KnownNat n) => [Nat]
dependentList = [0..natVal (Proxy @n)]

So the interesting thing here, is that there isn’t a ‘single’ cacheable value for dependentList; but once a type is applied it reduces down to a constant, so in theory once the type-checker runs, GHC could recognize that several spots all depend on the ‘same’ dependentList; e.g. (using TypeApplications)

main = do
  print (dependentList @5)
  print (dependentList @10)
  print (dependentList @5)

My question is, will GHC recognize that it can share both of the 5 lists? Or does it compute each one separately? Technically it would even be possible to compute those values at Compile-time rather than run-time, is it possible to get GHC to do that?

My case is a little more complicated, but should follow the same constraints as the example, however my dependentList-like value is intensive to compute.

I’m not at all opposed to doing this using a typeclass if it makes things possible; does GHC cache and re-use typeclass dictionaries? Maybe I could bake it into a constant in the typeclass dict to get caching?

Ideas anyone? Or anyone have reading for me to look at for how this works?

I'd prefer to do this in such a way that the compiler can figure it out rather than using manual memoization, but I'm open to ideas :)

Thanks for your time!

Answer 1

As suggested by @crockeea I ran an experiment; here's an attempt using a top-level constant with a polymorphic ambiguous type variable, and also an actual constant just for fun, each one contains a 'trace'

dependant :: forall n . KnownNat n => Natural
dependant = trace ("eval: " ++ show (natVal (Proxy @n))) (natVal (Proxy @n))

constantVal :: Natural
constantVal = trace "constant val: 1" 1


main :: IO ()
main = do
  print (dependant @1)
  print (dependant @1)
  print constantVal
  print constantVal

The results are unfortunate:

λ> main
eval: 1
1
eval: 1
1
constant val: 1
1
1

So clearly it re-evaluates the polymorphic constant each time it's used.

But if we write the constants into a typeclass (still using Ambiguous Types) it appears that it will resolve the Dictionary values only once per instance, which makes sense when you know that GHC passes the same dict for the same class instances. It does of course re-run the code for different instances:

class DependantClass n where
  classNat :: Natural

instance (KnownNat n) => DependantClass (n :: Nat) where
  classNat = trace ("dependant class: " ++ show (natVal (Proxy @n))) (natVal (Proxy @n))

main :: IO ()
main = do
  print (classNat @1)
  print (classNat @1)
  print (classNat @2)

Result:

λ> main
dependant class: 1
1
1
dependant class: 2
2

As far as getting GHC to do these at compile-time, it looks like you'd do that with lift from TemplateHaskell using this technique.

Unfortunately you can't use this within the typeclass definition since TH will complain that the '@n' must be imported from a different module (yay TH) and it's not known concretely at compile time. You CAN do it wherever you USE the typeclass value, but it'll evaluate it once per lift and you have to lift EVERYWHERE you use it to get the benefits; pretty impractical.