Moltiplicazione memorizzabile

Question

La mia applicazione moltiplica i vettori dopo una (costosa) conversione utilizzando una FFT. Di conseguenza, quando scrivo

f :: (Num a) => a -> [a] -> [a] 
f c xs = map (c*) xs 

solo voglio calcolare la FFT di c una volta, piuttosto che per ogni elemento di xs. Non c'è davvero alcuna necessità di memorizzare la FFT di c per l'intero programma, solo nell'ambito locale.

ho tentato di definire la mia Num istanza come:

data Foo = Scalar c 
     | Vec Bool v -- the bool indicates which domain v is in 

instance Num Foo where 
    (*) (Scalar c) = \x -> case x of 
         Scalar d -> Scalar (c*d) 
         Vec b v-> Vec b $ map (c*) v 
    (*) v1 = let Vec True v = fft v1 
      in \x -> case x of 
        Scalar d -> Vec True $ map (c*) v 
        v2 -> Vec True $ zipWith (*) v (fft v2) 

Poi, in una domanda, che io chiamo una funzione simile a f (che funziona su arbitrarie Num s) dove c=Vec False v, e mi aspettavo che questo sarebbe essere altrettanto veloce come se io hackero f a:

g :: Foo -> [Foo] -> [Foo] 
g c xs = let c' = fft c 
     in map (c'*) xs 

la funzione g rende il Memoizzazione di fft c verifica, ed è mu ch più veloce di chiamare f (non importa come definisco (*)). Non capisco cosa c'è che non va con f. È la mia definizione di nell'istanza Num? Ha qualcosa a che fare con f che funziona su tutti i Num, e GHC quindi non è in grado di capire come calcolare parzialmente (*)?

Nota: Ho controllato l'output principale per la mia istanza Num e (*) è effettivamente rappresentato come lambda nidificato con la conversione FFT nel lambda di livello superiore. Quindi sembra che questo sia almeno in grado di essere memoized. Ho anche provato sia l'uso giudizioso e sconsiderato di modelli di scoppio per tentare di forzare la valutazione senza alcun effetto.

Come nota a margine, anche se io riesco a capire come fare (*) Memoize suo primo argomento, c'è ancora un altro problema di come si è definito: Un programmatore voler uso il tipo di dati Foo deve sapere su questa capacità di memorizzazione. Se ha scritto

map (*c) xs 

non si verificherebbe alcuna memorizzazione. (Deve essere scritto come (map (c*) xs)) Ora che ci penso, non sono del tutto sicuro di come sarebbe GHC riscrivere la versione (*c) da quando sono al curry (*) Ma ho fatto un test rapido per verificare che sia (*c) e (c*) funzionare come previsto.: il primo argomento a *, mentre (*c) fa c il secondo argomento a *. Quindi il problema è che non è ovvio come si dovrebbe scrivere la moltiplicazione per garantire la memoizzazione.È questo solo un lato negativo intrinseco alla notazione infisso (e implicita che gli argomenti * sono simmetrici)?

il secondo problema meno pressante è che il caso whe mappiamo (v *) su un elenco di scalari. In questo caso, (si spera) il fft di v sarebbe calcolato e memorizzato, anche se non è necessario poiché l'altro multiplo è uno scalare. C'è un modo per aggirare questo?

Grazie

Answer 1

Credo che il pacchetto stable-memo potrebbe risolvere il tuo problema. Si memoizes valori che non utilizzano l'uguaglianza, ma per identità di riferimento:

Mentre la maggior parte combinatori memo Memoize basato sulla parità, stabile-memo vuol basa sul fatto che lo stesso identico argomento è stato passato alla funzione precedente (cioè, è lo stesso argomento in memoria).

E diminuisce automaticamente i valori memoized quando le chiavi sono garbage collection:

stabile-memo non mantiene le chiavi è visto finora, che consente loro di essere garbage collection se vogliono non più usato. I finalizzatori vengono posizionati per rimuovere le voci corrispondenti dalla tabella dei memo se ciò accade.

Quindi, se si definisce qualcosa come

fft = memo fft' 
    where fft' = ... -- your old definition 

si otterrà più o meno quello che ti serve: Calling map (c *) xs sarà Memoize il calcolo della FFT all'interno della prima chiamata a (*) e viene riutilizzata per le chiamate successive a (c *). E se c è spazzatura, lo è anche fft' c.

Vedi anche this answer per How to add fields that only cache something to ADT?

Answer 2

posso vedere due problemi che possono impedire Memoizzazione:

In primo luogo, f ha un tipo di sovraccarico e funziona per tutti i Num le istanze. Pertanto, f non può utilizzare la memoizzazione a meno che non sia specializzato (che di solito richiede un pragma) o inline (che può avvenire automaticamente, ma è più affidabile con un pragma INLINE).

In secondo luogo, la definizione di (*) per Foo esegue il pattern matching sul primo argomento, ma f moltiplica con una sconosciuta c. Quindi, all'interno di f, anche se specializzato, non può verificarsi alcuna memoizzazione. Ancora una volta, dipende molto dal fatto che f sia in linea e che sia fornito un argomento concreto per c, in modo che possa apparire effettivamente la funzione di inlining.

Quindi penso che sarebbe di aiuto vedere esattamente come stai chiamando f. Si noti che se f viene definito utilizzando due argomenti, è necessario fornire due argomenti, altrimenti non può essere sottolineato. Aiuterebbe inoltre a vedere la definizione attuale di Foo, come quella che stai citando c e v che non sono nel campo di applicazione.