Memoizzazione e typeclasses

Question

Per farla semplice, userò questa classe esempio inventato (il punto è che abbiamo alcuni dati costosi derivati ​​da metodi):

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

Naturalmente, possiamo fare implementazioni memoizing di questa classe come ad esempio:

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 

Ma sembra un po 'brutto per essere richiesto di aggiungere manualmente un campo di 'fattori' a qualsiasi record che sarà un esempio HasNumber. Successivo 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 

Ciò richiederà un sacco di testo standard per il sollevamento tutte le altre operazioni dell'originale a in WithFactorMemo a, però.

Ci sono soluzioni eleganti?

Answer 1

Ecco la soluzione: perdere il typeclass. Ho parlato di questo here e here. Qualsiasi classe di caratteri TC a per la quale ognuno dei suoi membri prende un singolo a come argomento è isomorfo a un tipo di dati. Ciò significa che ogni istanza della classe HasNumber può essere rappresentato in questo tipo di dati:

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

Vale a dire, per questa trasformazione:

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

E Number è ovviamente un caso di HasNumber pure.

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

Questo isomorfismo ci dimostra che questa classe è un tipo di dati in incognito, e dovrebbe morire. Basta usare Number invece. Potrebbe essere inizialmente non ovvio come farlo, ma con una piccola esperienza dovrebbe venire rapidamente. . Ad esempio, il tipo di Foo diventa:

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

tuo Memoizzazione verrà poi venire gratuitamente, perché i fattori sono memorizzati nella struttura dati Number.