Determinazione dell'implementazione del metodo in base ai vincoli disponibili

Question

Supponiamo di avere le seguenti funzioni di memorizzazione. (Ignorare il fatto che sono puri per favore.)

memoEq :: Eq a  => (a -> b) -> a -> b 
memoOrd :: Ord a  => (a -> b) -> a -> b 
memoHash :: Hashable a => (a -> b) -> a -> b 

Ora voglio avere un costrutto che mi permette di scegliere il 'migliore' dei suddetti tre funzioni memo. Qualcosa che fa essenzialmente i seguenti:

memo f = case constraint_of_typevar_a_in f of 
    Eq a  -> memoEq 
    Ord a  -> memoOrd 
    Hashable a -> memoHash 

Si può provare questo con le classi di tipo, ma si otterrà casi sovrapposte:

class Memo a where 
    memo :: (a -> b) -> a -> b 

instance Eq a => Memo a where 
    memo = memoEq 

instance Ord a => Memo a where 
    memo = memoOrd 

Ho anche tentato di usare cast per recuperare i vincoli. Mi rendo conto che questo sarebbe successo in fase di esecuzione e come mi è stato detto in #haskell questa è probabilmente una cattiva idea. (Ho omesso i casi per i memoOrd e memoHash per brevità.)

{-# LANGUAGE ImpredicativeTypes, ScopedTypeVariables #-} 
module Main where 

import Data.Typeable 

memo :: forall a b. (Typeable a, Typeable b) => (a -> b) -> Maybe (a -> b) 
memo f = 
    let eqf = cast f :: Eq a => Maybe (a -> b) 
    in case eqf of 
     Just eqf' -> Just $ memoEq eqf' 
     Nothing -> Nothing 

memoEq :: Eq a => (a -> b) -> a -> b 
memoEq = undefined 

memoOrd :: Ord a => (a -> b) -> a -> b 
memoOrd = undefined 

Questo codice genera il seguente messaggio di errore:

cast.hs:8:19: 
Could not deduce (Eq a) arising from an expression type signature 
from the context (Typeable a, Typeable b) 
    bound by the type signature for 
      memo :: (Typeable a, Typeable b) => (a -> b) -> Maybe (a -> b) 
    at cast.hs:6:9-74 
Possible fix: 
    add (Eq a) to the context of 
    the type signature for 
     memo :: (Typeable a, Typeable b) => (a -> b) -> Maybe (a -> b) 
In the expression: cast f :: Eq a => Maybe (a -> b) 
In an equation for `eqf': eqf = cast f :: Eq a => Maybe (a -> b) 
In the expression: 
    let eqf = cast f :: Eq a => Maybe (a -> b) 
    in 
    case eqf of { 
     Just eqf' -> Just $ memoEq eqf' 
     Nothing -> Nothing } 

Spostare il vincolo Eq a all'interno del Maybe dà un errore aggiuntivo che non vi è alcun vincolo Typeable1 su Eq.

Impossibile dedurre (Typeable1 Eq) derivanti da un uso del `cast' dal contesto (tipizzabile una, tipizzabile b)

è ciò che voglio raggiungere possibile, magari utilizzando Template Haskell ? O è completamente impossibile e indesiderabile essere in grado di farlo?

Answer 1

Nell'implementazione GHC delle classi di tipi (e in generale), non è possibile cercare dizionari di classe in fase di esecuzione. L'algoritmo per generare il codice del dizionario è integrato nel motore di inferenza del tipo del compilatore e non esiste un algoritmo corrispondente in alcun codice di runtime. Per quanto ne so, non esiste un database di runtime di tutte le istanze di classe, di cui avresti bisogno per implementare tale algoritmo. Il principio di progettazione dietro questo è che i tipi non sono dati, quindi un programma non può esaminarli.

Inoltre, non è possibile scegliere il metodo di memoizzazione migliore in fase di compilazione poiché il sistema di classe del tipo consente di definire nuove istanze. Poiché non è possibile dimostrare che un tipo è non un membro di Hashable -perché la definizione dell'istanza si trova in un file che non è stato ancora compilato-non è possibile escludere la possibilità che qualsiasi tipo di dato debba essere memoizzato in base nella classe Hashable; la stessa cosa vale per Eq e Ord.

Penso che la soluzione migliore sia scegliere manualmente come ogni tipo viene memoizzato scrivendo le istanze Memo per ogni costruttore di tipi.