Memoization and typeclasses

Question

To keep it simple, I'll use this contrived example class (the point is that we have some expensive data derived from the methods):

class HasNumber a where
  getNumber :: a -> Integer
  getFactors :: a -> [Integer]
  getFactors a = factor . getNumber

Of course, we can make memoizing implementations of this class such as:

data Foo = Foo {
  fooName :: String,
  fooNumber :: Integer,
  fooFactors :: [Integer]
}

foo :: String -> Integer -> Foo
foo a n = Foo a n (factor n) 

instance HasNumber Foo where
    getNumber = fooNumber
    getFactors = fooFactors

But it seems a bit ugly to be required to manually add a 'factors' field to any record that will be a HasNumber instance. Next idea:

data WithFactorMemo a = WithFactorMemo {
    unWfm :: a,
    wfmFactors :: [Integer]
}

withFactorMemo :: HasNumber a => a -> WithFactorMemo a
withFactorMemo a = WithFactorMemo a (getFactors a)

instance HasNumber a => HasNumber (WithFactorMemo a) where
    getNumber = getNumber . unWfm
    getFactors = wfmFactors

This will require lots of boilerplate for lifting all the other operations of the original a into WithFactorMemo a, though.

Are there any elegant solutions?

Answer 1

Here's the solution: lose the typeclass. I have talked about this here and here. Any typeclass TC a for which each of its members take a single a as an argument is isomorphic to a data type. That means that every instance of your HasNumber class can be represented in this data type:

data Number = Number {
    getNumber' :: Integer,
    getFactors' :: [Integer]
}

Namely, by this transformation:

toNumber :: (HasNumber a) => a -> Number
toNumber x = Number (getNumber x) (getFactors x)

And Number is obviously an instance of HasNumber as well.

instance HasNumber Number where
    getNumber = getNumber'
    getFactors = getFactors'

This isomorphism shows us that this class is a data type in disguise, and it should die. Just use Number instead. It may be initially non-obvious how to do this, but with a little experience should come quickly. Eg., your Foo type becomes:

data Foo = Foo {
    fooName :: String,
    fooNumber :: Number
}

Your memoization will then come for free, because the factors are stored in the Number data structure.