Come aggiungere campi che memorizzano solo qualcosa in ADT?

Question

Spesso ho bisogno di aggiungere campi a un ADT che memorizza solo alcune informazioni ridondanti. Ma non ho capito completamente come farlo in modo piacevole ed efficiente.

Il modo migliore per mostrare il problema è fare un esempio. Supponiamo che stiamo lavorando con i termini lambda senza tipo:

type VSym = String 

data Lambda = Var VSym 
      | App Lambda Lambda 
      | Abs VSym Lambda 

E di tanto in tanto abbiamo bisogno di calcolare l'insieme di variabili libere di un termine:

fv :: Lambda -> Set VSym 
fv (Var v) = Set.singleton v 
fv (App s t) = (fv s) `Set.union` (fv t) 
fv (Abs v t) = v `Set.delete` (fv t) 

Presto ci rendiamo conto che ripetuti calcoli di fv sono un collo di bottiglia della nostra applicazione. Vorremmo aggiungerlo in qualche modo al tipo di dati. Come:

data Lambda1 = Var (Set VSym) VSym 
      | App (Set VSym) Lambda Lambda 
      | Abs (Set VSym) VSym Lambda 

Ma rende la definizione abbastanza brutta. Quasi lo (Set VSym) occupa più spazio di tutto il resto. Inoltre, interrompe la corrispondenza del modello in tutte le funzioni che utilizzano Lambda. E per peggiorare le cose, se in seguito decidiamo di aggiungere qualche altro campo di memoizzazione, dovremo riscrivere di nuovo tutti i modelli.

Come progettare una soluzione generale che consente di aggiungere tali campi di memoizzazione in modo semplice e discreto? Mi piacerebbe raggiungere i seguenti obiettivi:

1. La definizione data dovrebbe cercare il più vicino possibile a quello originale, in modo che sia facilmente leggibile e comprensibile.
2. Anche le corrispondenze di pattern devono rimanere semplici e leggibili.
3. L'aggiunta di un nuovo campo memoizing entro e non deve rompere il codice esistente, in particolare:
   • di non rompere gli schemi esistenti,
   • di non richiedere modifiche in cui è stata utilizzata la funzione che vogliamo Memoize (come il codice che ha utilizzato fv in questo esempio).

---

descriverò la mia soluzione attuale: Per mantenere la definizione data e delle corrispondenze come poco ingombrante possibile, definiamo:

data Lambda' memo = Var memo VSym 
        | App memo (Lambda' memo) (Lambda' memo) 
        | Abs memo VSym (Lambda' memo) 
type Lambda = Lambda' LambdaMemo 

in cui i dati da memoized è definito separatamente:

data LambdaMemo = LambdaMemo { _fv :: Set VSym, _depth :: Int } 

Quindi come funzione di esecuzione che recupera la parte memoized:

memo :: Lambda' memo -> memo 
memo (Var c _) = c 
memo (App c _ _) = c 
memo (Abs c _ _) = c 

(Questo potrebbe essere eliminato utilizzando campi denominati. Ma poi avremmo anche have to name all the other fields.)

Questo ci permette di raccogliere parti specifiche dal Memoize, mantenendo la stessa firma di fv come prima:

fv :: Lambda -> Set VSym 
fv = _fv . memo 

depth :: Lambda -> Int 
depth = _depth . memo 

Infine, dichiariamo questi costruttori intelligenti:

var :: VSym -> Lambda 
var v = Var (LambdaMemo (Set.singleton v) 0) v 

app :: Lambda -> Lambda -> Lambda 
app s t = App (LambdaMemo (fv s `Set.union` fv t) (max (depth t) (depth s))) s t 

abs :: VSym -> Lambda -> Lambda 
abs v t = Abs (LambdaMemo (v `Set.delete` fv t) (1 + depth t)) v t 

Ora possiamo scrivere in modo efficiente le cose che combinano la corrispondenza del modello con la lettura dei campi memoizzati come

canSubstitute :: VSym -> Lambda -> Lambda -> Bool 
canSubstitute x s t 
    | not (x `Set.member` (fv t)) 
     = True -- the variable doesn't occur in `t` at all 
canSubstitute x s t@(Abs _ u t') 
    | u `Set.member` (fv s) 
     = False 
    | otherwise 
     = canSubstitute x s t' 
canSubstitute x s (Var _ _) 
     = True 
canSubstitute x s (App _ t1 t2) 
     = canSubstitute x s t1 && canSubstitute x s t2 

Questo sembra risolvere:

• La corrispondenza del modello è ancora abbastanza ragionevole.
• Se aggiungiamo un nuovo campo di memoizzazione non interromperà il codice esistente.
• Se decidiamo di memoizzare una funzione con la firma Lambda -> Something, possiamo facilmente aggiungerla come nuovo campo di memoizzazione.

Quello che ancora non mi piace di questo progetto:

• La definizione data non è poi così male, ma ancora mettendo memo ovunque ingombra notevolmente.
• Abbiamo bisogno di costruttori intelligenti per la costruzione di valori, ma usiamo i costruttori regolari per la corrispondenza dei modelli. Non è così male, semplicemente aggiungiamo uno _, ma avere la stessa firma per la costruzione e la decostruzione sarebbe bello. Suppongo che Views o Pattern Synonyms risolverà.
• Il calcolo dei campi memoizzati (variabili libere, profondità) è strettamente accoppiato ai costruttori intelligenti. Poiché è ragionevole presumere che quelle funzioni memoizzate saranno sempre catamorphisms, credo che questo potrebbe essere risolto in una certa misura da strumenti come the fixpoint package.

Qualche idea su come migliorarlo? O ci sono modi migliori per risolvere questo problema?

Answer 1

Penso che tutti i tuoi obiettivi possano essere soddisfatti utilizzando la semplice memoizzazione nella funzione anzichè memorizzando nella cache i risultati nell'ADT stesso. Solo un paio di settimane fa, ho rilasciato il pacchetto stable-memo, che dovrebbe aiutare qui. Controllando i tuoi criteri, non penso che potremmo fare meglio di questo:

1. La definizione dei dati non cambia affatto.
2. La corrispondenza del modello non cambia neanche.
3. Il codice esistente non deve essere modificato semplicemente perché si scrivono più funzioni memoizzate.
   • Nessun motivo esistente viene danneggiato.
   • Nessuna funzione memoized esistente viene interrotta.

Usarlo è molto semplice. Basta applicare memo a qualsiasi funzione che si desidera memoizzare, assicurandosi di utilizzare la versione memoized della funzione ovunque, anche nelle chiamate ricorsive.Ecco come scrivere l'esempio che hai usato nella tua domanda:

import Data.StableMemo 

type VSym = String 

data Lambda = Var VSym 
      | App Lambda Lambda 
      | Abs VSym Lambda 

fv :: Lambda -> Set VSym 
fv = memo go 
    where 
    go (Var v) = Set.singleton v 
    go (App s t) = fv s `Set.union` fv t 
    go (Abs v t) = v `Set.delete` fv t