memoization y clases de tipos

Question

Para hacerlo simple, voy a utilizar esta clase de ejemplo artificial (el punto es que tenemos algunos datos costosos derivados de los métodos):

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

Por supuesto, podemos hacer implementaciones memoizing de esta clase tales como:

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 

Pero parece un poco feo que se requiere para añadir manualmente un campo 'factores' a cualquier registro que será una instancia de HasNumber. Siguiente 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 

Esto requerirá una gran cantidad de texto modelo para el levantamiento de todas las otras operaciones del original a en WithFactorMemo a, sin embargo.

¿Hay alguna solución elegante?

Answer 1

Aquí está la solución: perder la clase de tipo. He hablado sobre esto here y here. Cualquier tipo de clase TC a para el cual cada uno de sus miembros tome un solo a como argumento es isomorfo para un tipo de datos. Eso significa que cada instancia de la clase HasNumber se puede representar en este tipo de datos:

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

Es decir, por esta transformación:

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

Y Number es, obviamente, una instancia de HasNumber también.

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

Este isomorfismo nos muestra que esta clase es un tipo de datos disfrazado, y debería morir. Simplemente use Number en su lugar. Al principio puede que no sea obvio cómo hacerlo, pero con un poco de experiencia debería llegar rápidamente. ., Por ejemplo, el tipo de Foo se convierte en:

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

Su memoization vendrá entonces de forma gratuita, ya que los factores se almacenan en la estructura de datos Number.