Memoizzazione indipendente degli argomenti

Question

Ho una simulazione con molte chiamate alle funzioni dello type F = A -> B -> C -> D, dove A .. D sono tipi concreti.

Gli oggetti del tipo A hanno una durata media. (È il genoma di codegolf's ratrace.)

Il calcolo più costoso deriva dal parametro A. Posso facilmente Memoize simili:

f1 :: F 
f1 a = let expensive = trace "expensive computation!" $ expensiveComputation a 
     in \b c -> expensive 

premuto alcuni expensive valori pre-elaborati tramite applicazione parziale:

preProz :: [B -> C -> D] 
preProz = [f1 [], f1 [False], f2 []] 

Le tracce indicano che preProz <*> [[],[[]]] <*> [1,2] non ricalcola i valori per la mia gioia.

Ora ho scoperto che alcuni dei miei F s trarrebbero vantaggio dalla pre-elaborazione B, anche. Questa pre-elaborazione è indipendente da A, e, infatti, memoizing simili ha alcun beneficio

f2 a = let expensive = trace "expensive computation!" $ expensiveComputation a 
     in \b -> let dear = trace "expensive computation!" $ expensiveComputation b 
        in expensive + dear 

perché dear viene ricalcolato, anche la b s uguali.

Che cosa ho bisogno è qualcosa di simile:

(B -> e) -> A -> e -> C -> D 

dove dovrebbe essere memoized e. Il tipo di e è in ordine di sorta qui. Ma questo mi costringe a ricalcolare tutti i valori A per ogni B, che è altrettanto grave, e non posso salvare i e s, che sono privati ​​della funzione.

Come posso memoize lungo 2 parametri in modo indipendente?

Answer 1

Hai bisogno di un funzione che memoizes sia a e b insieme:

f12 a b = ... 
    in \c -> ... 

Quando si desidera Memoize a ma non b, si utilizza f1 a e quando si vuole Memoize entrambi si utilizza f12 a b.

Sarebbe ovviamente opportuno condividere alcune implementazioni tra f1 e f12. Tuttavia, si può fare solo avendo funzioni private che assumono i risultati pre-calcolate al posto dei valori originali:

f1 a = privateA (precomputeA a) 
f12 a b = privateAB (precomputeA a) (precomputeB b) 
privateA a' b = privateAB a' (precomputeB b) 
private AB a' b' c = ... 

Se la precomputation di b dipende dalla precomputation di a, quindi:

f1 a = privateA (precomputeA a) 
f12 a b = let a' = precomputeA a in privateAB a' (precomputeB a' b) 
privateA a' b = privateAB a' (precomputeB a' b) 
private AB a' b' c = ... 

Non ho intenzionalmente usato la composizione delle funzioni e la riduzione dell'et, per rendere le cose più chiare. Ho anche escluso qualsiasi annotazione sulla severità che potresti voler utilizzare per controllare i tempi di valutazione.

Forse la memoizzazione non è proprio il termine giusto qui.Intendi qualcosa come "applicazione parziale con qualche precomputazione".