ristretta monoid valori di tipo di composizione

Question

ho un tipo di dati che è un'istanza di Monoid così posso ottenere composizione piacevole valori:

data R a = R String (Maybe (String → a)) 

instance Monoid (R a) where 
    mempty = R "" Nothing 
    R s f `mappend` R t g = R (s ++ t) (case g of Just _ → g; Nothing → f) 

successiva, non voglio unire tutti i valori R a uno con l'altro, non ha senso nel mio dominio. Così ho introdurre tipo fantasma t:

{-# LANGUAGE DataKinds, KindSignatures #-} 

data K = T1 | T2 
data R (t ∷ K) a = R String (Maybe (String → a)) 

instance Monoid (R t a) where … 

valori Così ho "limitato":

v1 ∷ R T1 Int 
v2 ∷ R T2 Int 
-- v1 <> v2 => type error 

e "senza restrizioni":

v ∷ R t Int 
-- v <> v1 => ok 
-- v <> v2 => ok 

Ma ora ho un problema. Quando si tratta di v30, ad esempio:

• mi avrebbe enorme di dati dichiarazione tipo (data K = T1 | … | T30). Potrei risolvere usando i tipi di livello naturali per ottenere una fonte infinita di tipi fantasma (la cura è peggiore della malattia, non è vero?)
• Dovrei ricordare quale tipo di fantasma per quale valore usare quando si scrive il tipo di firme in dipendenza il codice (che è in realtà fastidioso)

c'è un approccio più semplice per limitare la composizione in qualche modo?

Answer 1

Cercando il ConstrainedMonoid

sono arrivato a un problema molto simile ultimamente, che ho finalmente risolto il modo descritto alla fine di questo post (che non comportano un monoide, ma usando predicati sui tipi). Tuttavia, ho accettato la sfida e ho provato a scrivere una classe ConstrainedMonoid.

Ecco l'idea:

class ConstrainedMonoid m where 
    type Compatible m (t1 :: k) (t2 :: k) :: Constraint 
    type TAppend m (t1 :: k) (t2 :: k) :: k 
    type TZero m :: k 

    memptyC :: m (TZero m) 
    mappendC :: (Compatible m t t') => m t -> m t' -> m (TAppend m t t') 

Ok, c'è l'istanza banale, che in realtà non aggiunge nulla di nuovo (ho scambiato R s argomenti di tipo):

data K = T0 | T1 | T2 | T3 | T4 
data R a (t :: K) = R String (Maybe (String -> a)) 

instance ConstrainedMonoid (R a) where 
    type Compatible (R a) T1 T1 =() 
    type Compatible (R a) T2 T2 =() 
    type Compatible (R a) T3 T3 =() 
    type Compatible (R a) T4 T4 =() 
    type Compatible (R a) T0 y =() 
    type Compatible (R a) x T0 =() 

    type TAppend (R a) T0 y = y 
    type TAppend (R a) x T0 = x 
    type TAppend (R a) T1 T1 = T1 
    type TAppend (R a) T2 T2 = T2 
    type TAppend (R a) T3 T3 = T3 
    type TAppend (R a) T4 T4 = T4 
    type TZero (R a) = T0 

    memptyC = R "" Nothing 
    R s f `mappendC` R t g = R (s ++ t) (g `mplus` f) 

Questo prende purtroppo molte istanze di tipo ridondanti (OverlappingInstances non sembrano funzionare per famiglie di tipi), ma penso che soddisfi le leggi monoidi, a livello di testo e a livello di valore.

Tuttavia, non è chiuso. È più simile a un insieme di diversi monoidi, indicizzati da K. Se è quello che vuoi, dovrebbe bastare.

Se volete maggiori

Diamo un'occhiata ad una variante diversa:

data B (t :: K) = B String deriving Show 

instance ConstrainedMonoid B where 
    type Compatible B T1 T1 =() 
    type Compatible B T2 T2 =() 
    type Compatible B T3 T3 =() 
    type Compatible B T4 T4 =() 

    type TAppend B x y = T1 
    type TZero B = T3 

    memptyC = B "" 
    (B x) `mappendC` (B y) = B (x ++ y) 

Questo potrebbe essere un caso che ha senso nel dominio - tuttavia, non è più un monoide. E se hai provato a crearne uno, otterrà lo stesso risultato dell'istanza sopra, solo con diversi TZero.In realtà sto solo speculando qui, ma la mia intuizione mi dice che le uniche istanze monoid valide sono esattamente quelle come per R a; solo con valori unitari diversi.

Altrimenti, ci si ritroverà con qualcosa non necessariamente associativo (e probabilmente con un oggetto terminale, credo), che è non chiuso in composizione. E se vuoi limitare la composizione allo stesso valore di K s, perderai il valore unitario.

Un modo migliore (IMHO)

Ecco come ho effettivamente risolto il problema (non ho nemmeno pensare di monoidi allora, dal momento che non aveva senso in ogni caso). La soluzione si spoglia essenzialmente fuori tutto tranne il "produttore vincolo" Compatible, che viene lasciato come un predicato su due tipi:

type family Matching (t1 :: K) (t2 :: K) :: Constraint 
type instance Matching T1 T1 =() 
type instance Matching T2 T1 =() 
type instance Matching T1 T2 =() 
type instance Matching T4 T4 =() 

usato come

foo :: (Matching a b) => B a -> B b -> B Int 

Questo ti dà il pieno controllo sulla tua definizione di compatibilità e che tipo di composizione (non necessariamente monoidale) vuoi, ed è più generale. Può essere ampliato a infinite tipologie, troppo:

-- pseudo code, but you get what I mean 
type instance NatMatching m n = (IsEven m, m > n) 

---

Risposte alle ultime due punti:

• Sì, è necessario definire sufficientemente molti tipi nel vostro genere. Ma penso che dovrebbero essere auto-esplicativi comunque. Puoi anche dividerli in gruppi o definire un tipo ricorsivo.

• È principalmente necessario ricordare il significato del tipo di indice in due punti: la definizione del vincolo e, forse, per i metodi di produzione(). Ma penso che non dovrebbe essere il problema, se i tipi sono chiamati bene. (Si può essere molto ridondante, anche se - non ho trovato un modo per evitare che ancora Probabilmente TH avrebbe funzionato..)

Questo potrebbe essere più facile?

Quello che mi piace davvero di essere in grado di scrivere è il seguente:

type family Matching (t1 :: K) (t2 :: K) :: Constraint 
type instance Matching T1 y =() 
type instance Matching x T1 =() 
type instance Matching x y = (x ~ y) 

temo questo ha un serio motivo per non essere consentito; tuttavia, forse, non è implementato ...

MODIFICA: Al giorno d'oggi, abbiamo closed type families, che fanno esattamente questo.