Regola di riscrittura GHC specializzata in una funzione per una classe di tipo

Question

Utilizzando GHC RULES pragma, è possibile specializzare una funzione polimorfica per tipi specifici. Esempio dal rapporto Haskell:

genericLookup :: Ord a => Table a b -> a -> b 
intLookup  ::   Table Int b -> Int -> b 

{-# RULES "genericLookup/Int" genericLookup = intLookup #-} 

Ciò renderebbe GHC utilizzare intLookup su una tabella di interi indicizzata e la versione generica in caso contrario, in cui intLookup sarebbe probabilmente più efficiente.

vorrei realizzare qualcosa di simile, utilizzando funzioni come le seguenti (leggermente semplificate) quelli:

lookup :: Eq a => [(a, b)] -> a -> b 
lookupOrd :: Ord a => [(a, b)] -> a -> b 

dove lookupOrd crea un Map dalla lista di input e quindi utilizza Map.lookup, che richiede che a essere un membro di Ord.

Ora vorrei dire che GHC lookupOrd dovrebbe essere usato al posto di lookup ogni volta a è davvero un membro della classe Ord tipo. La seguente regola, tuttavia, non TYPECHECK:

{-# RULES "lookup/Ord" lookup = lookupOrd #-} 

GHC (giustamente) si lamenta che non si può dedurre (Ord a) dal contesto (Eq a). Esiste una regola di riscrittura che mi consenta di eseguire questo tipo di specializzazione basata sulla classe di tipo?

Answer 1

Io non credo che ci sia, e c'è un motivo per cui non è facilmente possibile con l'attuale implementazione del GHC:

Anche se si specifica le regole nella sintassi Haskell, che stanno per essere applicato al linguaggio Core GHC . Lì, i vincoli di classe tipo sono stati trasformati in argomenti del dizionario, in modo che la funzione di

lookup :: Eq a => a -> [(a,b)] -> Maybe b 

è ormai digitare

lookup :: forall a b. Eq a -> a -> [(a, b)] -> Maybe b 

in tutta lookupOrd avrebbe tipo

lookupOrd :: forall a b. Ord a -> a -> [(a, b)] -> Maybe b 

dove Eq a e Ord a hanno diventa tipi di dati ordinari. In particolare, in questa fase, non esiste alcuna nozione di la classe di tipo per un tipo più; tutto ciò che è stato risolto prima.

Così ora assumere il compilatore trova un occorrenza di

lookup (dict :: Eq MyType) (x :: MyType) (list :: [(MyType, String)]) 

Cosa dovrebbe sostituirlo con? Gli hai detto che e list possono essere passati a lookupOrd, ma tale funzione vuole anche un valore di tipo Ord MyType, che non si verifica sul lato sinistro della regola. Quindi GHC deve rinunciare.

una regola come

{-# RULES "lookup/Ord" forall a x. lookup a x = lookupOrd (a::()) x #-} 

opere, anche se, come qui l'argomento problematico (il dizionario Ord) è già fissato nella regola, e non ha bisogno di essere trovata quando si applica la regola.

In linea di principio, altri schemi di compilazione potrebbero consentire le regole del modulo desiderato.

Answer 2

Mentre questa è una vecchia domanda, i futuri utenti di Google potrebbero essere interessati a sapere che c'è un modo per fare ciò che l'OP voleva, usando il pacchetto ifcxt.

È possibile consultare la documentazione per altri esempi, ma in pratica si utilizzerà il secondo esempio, Esempio 2: rendere il codice asintoticamente efficiente, come base.

Con le due funzioni,

lookup :: Eq a => [(a, b)] -> a -> b 
lookupOrd :: Ord a => [(a, b)] -> a -> b 

Si potrebbe fare,

cxtLookup :: forall a. (Eq a, IfCxt (Ord a)) => [(a, b)] -> a -> b 
cxtLookup = ifCxt (Proxy::Proxy (Ord a)) lookupOrd lookup 

che vi permetterà di scegliere la funzione più efficace a seconda di quale typeclasses gli attrezzi struttura dati.

Nota che non so quanto influirà sulle prestazioni, ma immagino che sia banale rispetto al runtime delle funzioni di ricerca, e quindi ne varrà la pena.