Is there an automatic way to memoise global polymorphic values in Haskell?

Question

Polymorphic "constants", like 5 :: Num a => a, aren't really constants but functions of a dictionary argument. Hence, if you define

primes :: Num n => [n]
primes = ...

^{Bad example of course, there's no good reason here to have it polymorphic... what I'm really interested is if you try to globally memoise a nontrivial polymorphic function, with e.g. memo-tries.}
then this sequence won't be shared between calls from different sites, which isn't nice in terms of performance. (Isn't this the main reason the Haskell standard blessed us with the Dreaded Monomorphism Restriction?)

The only way I can see how to enforce sharing is to have a monomorphic "tag" sitting around for every instance of the constraining class. E.g.

erastothenes :: Num n => [n]
erastothenes = ...

class (Num n) => HasPrimes n where
  -- | @'primes' ≡ 'erastothenes'@
  primes :: [n]

integerPrimes :: [Integer]
integerPrimes = erastothenes

instance HasPrimes Integer where
  primes = integerPrimes

... which isn't nice in terms of elegance.

Is there any nicer way to implement such a memoisation?

Answer 1

It's fairly impossible for a fairly technical reasons. Type classes are open so, the polymorphic constant can't at compile time necessarily "see" how many types satisfy the constraint so it can't allocate that many monomorphic thunks. On the other side, a type class certainly can't see all the possible constants that it might generate, so the monomorphic thunks cannot be allocated in the type class dictionary.

You will have to explicitly mention any types at which you want a monomorphic thunk allocated.

Answer 2

One could add Typeable constraint to n and use a different memoization table for every ground type n. You probably would need to exploit Dynamic and cast a lot for this, which is suboptimal. It also feels a bit hackish, too.

In a dependently typed language, of course, one can model a map (n : Num) -> [n] which would not require the castss from Dynamic. Maybe something like that can be simulated exploiting GADTs and some kind of reification machinery.

Answer 3

If you enable ConstraintKinds and ExistentialQuantification (or GADTs) you can reify type class dictionaries:

{-# LANGUAGE ConstraintKinds, ExistentialQuantification #-}

data Dict a = a => Dict

If we try this out

fibs :: Num n => [n]
fibs = 1 : 1 : zipWith (+) fibs (drop 1 fibs)

fibs' :: [Integer]
fibs' = fibs


fibsWithDict :: Dict (Num n) -> [n]
fibsWithDict Dict = fs
  where
    fs = 1 : 1 : zipWith (+) fs (drop 1 fs)

fibs'' :: [Integer]
fibs'' = fibsWithDict Dict

in GHCi we see

λ> :set +s
λ> 
λ> fibs !! 29
832040
(2.66 secs, 721235304 bytes)
λ> 
λ> fibs !! 29
832040
(2.52 secs, 714054736 bytes)
λ> 
λ> 
λ> fibs' !! 29
832040
(2.67 secs, 713510568 bytes)
λ> 
λ> fibs' !! 29
832040
(0.00 secs, 1034296 bytes)
λ> 
λ> 
λ> fibs'' !! 29
832040
(0.00 secs, 1032624 bytes)

So fibs'' is the only implementation of the three that immediately memoizes.

Note that we have to pattern match on the Dict constructor. Otherwise, we will get an error about n not being constrained to have a Num instance (like you would expect if our signature was just fibsWithDict :: a -> [n]).

This is a full solution since you can consider fibsWithDict Dict to be an expression that memoizes immediately at any type you throw at it (as long as it's an instance of Num). For example:

λ> (fibsWithDict Dict !! 29) :: Double
832040.0
(0.00 secs, 1028384 bytes)

EDIT: It looks like this explicit dictionary passing isn't necessary here and can be done implicitly by using ScopedTypeVariables with a local binding:

{-# LANGUAGE ScopedTypeVariables #-}

fibsImplicitDict :: forall a. Num a => [a]
fibsImplicitDict
  = let fs :: [a]
        fs = 1 : 1 : zipWith (+) fs (drop 1 fs)
    in
    fs

(Thanks to bennofs for the insight here!)