Esiste un modo per vincolare i tipi di unione?

Question

In Haskell, esiste un modo per raggruppare diversi vincoli di tipo, in modo che l'unione sia soddisfatta se uno di essi è soddisfatto?

Per esempio, supponiamo ho avuto un GADT parametrizzato da un DataKind, e volevo alcuni costruttori per restituire solo i valori per alcuni costruttori della data genere, la pseudo-Haskell sarebbe:

{-# LANGUAGE GADTs #-} 
{-# LANGUAGE KindSignatures #-} 
{-# LANGUAGE DataKinds #-} 
module Temp where 

data Color = White | Red | Blue | Yellow | Green | Tawny | Purple | Black 

data Fruit (c :: Color) where 
    Banana :: (c ~ Green | c ~ Yellow | c ~ Black) => Fruit c 
    Apple :: (c ~ Red | c ~ Green)    => Fruit c 
    Grape :: (c ~ Red | c ~ Green | c ~ White)  => Fruit c 
    Orange :: (c ~ Tawny)       => Fruit c 

posso cercare di attuare le o utilizzando typeclasses:

{-# LANGUAGE GADTs #-} 
{-# LANGUAGE KindSignatures #-} 
{-# LANGUAGE DataKinds #-} 
module Temp where 

data Color = White | Red | Blue | Yellow | Green | Tawny | Purple | Black 

data Fruit (c :: Color) where 
    Banana :: BananaColor c => Fruit c 
    Apple :: AppleColor c => Fruit c 
    Grape :: GrapeColor c => Fruit c 
    Orange :: OrangeColor c => Fruit c 

class BananaColor (c :: Color) 
instance BananaColor Green 
instance BananaColor Yellow 
instance BananaColor Black 

class AppleColor (c :: Color) 
instance AppleColor Red 
instance AppleColor Green 

class GrapeColor (c :: Color) 
instance GrapeColor Red 
instance GrapeColor Green 
instance GrapeColor White 

class OrangeColor (c :: Color) 
instance OrangeColor Tawny 

ma non è solo questo verboso, è anche un po 'diverso da quello che ho inteso a che l'unione originale è stato chiuso, ma i typeclasses sono tutti aperti. Non c'è niente da impedire a qualcuno di definire

instance OrangeColor Blue 

E perché è aperto, non c'è modo il compilatore potrebbe dedurre che [Apple, Grape, Banana] deve essere di tipo [Fruit Green] a meno che detto.

Answer 1

Non riesco a pensare a un modo per implementare letteralmente o per Constraint s, sfortunatamente, ma se stiamo solo mettendo insieme le uguaglianze, come nel tuo esempio, possiamo rendere più piccante l'approccio alla classe di tipo e renderlo chiuso con famiglie di tipi e booleans sollevati. Funzionerà solo in GHC 7.6 e versioni successive; alla fine, menziono entrambi come sarà più bello in GHC 7.8 e come eseguire il backport a GHC 7.4.

L'idea è questa: Proprio come abbiamo potuto dichiarare una funzione a livello di valore isBananaColor :: Color -> Bool, così anche noi possiamo dichiarare una funzione di tipo a livello IsBananaColor :: Color -> Bool:

type family IsBananaColor (c :: Color) :: Bool 
type instance IsBananaColor Green = True 
type instance IsBananaColor Yellow = True 
type instance IsBananaColor Black = True 
type instance IsBananaColor White = False 
type instance IsBananaColor Red = False 
type instance IsBananaColor Blue = False 
type instance IsBananaColor Tawny = False 
type instance IsBananaColor Purple = False 

Se ci piace, possiamo anche aggiungere

type BananaColor c = IsBananaColor c ~ True 

Abbiamo poi ripetere questo per ogni colore di frutta, e definiscono Fruit come nel tuo secondo esempio:

{-# LANGUAGE GADTs #-} 
{-# LANGUAGE KindSignatures #-} 
{-# LANGUAGE DataKinds #-} 
{-# LANGUAGE ConstraintKinds #-} 
{-# LANGUAGE TypeFamilies #-} 

data Color = White | Red | Blue | Yellow | Green | Tawny | Purple | Black 

data Fruit (c :: Color) where 
    Banana :: BananaColor c => Fruit c 
    Apple :: AppleColor c => Fruit c 
    Grape :: GrapeColor c => Fruit c 
    Orange :: OrangeColor c => Fruit c 

type family IsBananaColor (c :: Color) :: Bool 
type instance IsBananaColor Green = True 
type instance IsBananaColor Yellow = True 
type instance IsBananaColor Black = True 
type instance IsBananaColor White = False 
type instance IsBananaColor Red = False 
type instance IsBananaColor Blue = False 
type instance IsBananaColor Tawny = False 
type instance IsBananaColor Purple = False 
type BananaColor c = IsBananaColor c ~ True 

type family IsAppleColor (c :: Color) :: Bool 
type instance IsAppleColor Red = True 
type instance IsAppleColor Green = True 
type instance IsAppleColor White = False 
type instance IsAppleColor Blue = False 
type instance IsAppleColor Yellow = False 
type instance IsAppleColor Tawny = False 
type instance IsAppleColor Purple = False 
type instance IsAppleColor Black = False 
type AppleColor c = IsAppleColor c ~ True 

type family IsGrapeColor (c :: Color) :: Bool 
type instance IsGrapeColor Red = True 
type instance IsGrapeColor Green = True 
type instance IsGrapeColor White = True 
type instance IsGrapeColor Blue = False 
type instance IsGrapeColor Yellow = False 
type instance IsGrapeColor Tawny = False 
type instance IsGrapeColor Purple = False 
type instance IsGrapeColor Black = False 
type GrapeColor c = IsGrapeColor c ~ True 

-- For consistency 
type family IsOrangeColor (c :: Color) :: Bool 
type instance IsOrangeColor Tawny = True 
type instance IsOrangeColor White = False 
type instance IsOrangeColor Red = False 
type instance IsOrangeColor Blue = False 
type instance IsOrangeColor Yellow = False 
type instance IsOrangeColor Green = False 
type instance IsOrangeColor Purple = False 
type instance IsOrangeColor Black = False 
type OrangeColor c = IsOrangeColor c ~ True 

(Se si desidera, è possibile sbarazzarsi di -XConstraintKinds ei type XYZColor c = IsXYZColor c ~ True tipi, e solo definire i costruttori di Fruit come XYZ :: IsXYZColor c ~ True => Fruit c.)

Ora, che cosa fa questo si acquista, e ciò che non è vero che si compra ? Tra i lati positivi, si ottiene la possibilità di definire il proprio tipo come si desidera, che è sicuramente una vittoria; e dal momento che Color è chiuso, nessuno può aggiungere più tipi di istanze familiari e interromperlo.

Tuttavia, ci sono aspetti negativi. Non ottieni l'inferenza che volevi dirti automaticamente che [Apple, Grape, Banana] è di tipo Fruit Green; la cosa peggiore è che il [Apple, Grape, Banana] ha il tipo perfettamente valido (AppleColor c, GrapeColor c, BananaColor c) => [Fruit c]. Sì, non c'è modo di monomorfizzarlo, ma GHC non riesce a capirlo. Ad essere onesti, non riesco a immaginare nessuna soluzione che ti dia queste proprietà, anche se sono sempre pronto ad essere sorpreso. L'altro ovvio problema con questa soluzione è come lungo è-è necessario definire tutti gli otto casi di colore per ciascuna famiglia di tipi IsXYZColor! (L'uso di un nuovo tipo di famiglia per ciascuno è anche fastidioso, ma inevitabile con soluzioni di questo modulo.)

---

ho già detto che GHC 7.8 renderà questo più bello; lo farà ovviando alla necessità di elencare ogni singolo caso per ogni singola classe IsXYZColor. Come? Bene, Richard Eisenberg et al. introdotto chiuso sovrapposto famiglie di tipo ordinato in HEAD GHC, e sarà disponibile in 7.8. C'è a paper in sumbission to POPL 2014 (e uno extended version) sull'argomento e Richard ha anche scritto an introductory blog post (che sembra avere una sintassi obsoleta).

L'idea è di consentire che le istanze di tipo famiglia siano dichiarate come funzioni ordinarie: le equazioni devono essere tutte dichiarate in un unico posto (rimuovendo l'ipotesi del mondo aperto) e vengono provate in ordine, il che consente la sovrapposizione. Qualcosa di simile

type family IsBananaColor (c :: Color) :: Bool 
type instance IsBananaColor Green = True 
type instance IsBananaColor Yellow = True 
type instance IsBananaColor Black = True 
type instance IsBananaColor c  = False 

è ambigua, perché IsBananaColor Green partite sia il primo e l'ultimo equazioni; ma in una funzione ordinaria, funzionerebbe bene. Così la nuova sintassi è:

type family IsBananaColor (c :: Color) :: Bool where 
    IsBananaColor Green = True 
    IsBananaColor Yellow = True 
    IsBananaColor Black = True 
    IsBananaColor c  = False 

Che type family ... where { ... } blocco definisce il tipo di famiglia nel modo che desidera definirla; segnala che questa famiglia di tipi è chiusa, ordinata e sovrapposta, come descritto sopra. Così, il codice sarebbe diventato qualcosa di simile a quanto segue in GHC 7.8 (non testato, come io non ce l'ho installato sulla mia macchina):

{-# LANGUAGE GADTs #-} 
{-# LANGUAGE KindSignatures #-} 
{-# LANGUAGE DataKinds #-} 
{-# LANGUAGE TypeFamilies #-} 

data Color = White | Red | Blue | Yellow | Green | Tawny | Purple | Black 

data Fruit (c :: Color) where 
    Banana :: IsBananaColor c ~ True => Fruit c 
    Apple :: IsAppleColor c ~ True => Fruit c 
    Grape :: IsGrapeColor c ~ True => Fruit c 
    Orange :: IsOrangeColor c ~ True => Fruit c 

type family IsBananaColor (c :: Color) :: Bool where 
    IsBananaColor Green = True 
    IsBananaColor Yellow = True 
    IsBananaColor Black = True 
    IsBananaColor c  = False 

type family IsAppleColor (c :: Color) :: Bool where 
    IsAppleColor Red = True 
    IsAppleColor Green = True 
    IsAppleColor c  = False 

type IsGrapeColor (c :: Color) :: Bool where 
    IsGrapeColor Red = True 
    IsGrapeColor Green = True 
    IsGrapeColor White = True 
    IsGrapeColor c  = False 

type family IsOrangeColor (c :: Color) :: Bool where 
    IsOrangeColor Tawny = True 
    IsOrangeColor c  = False 

Evviva, siamo in grado di leggere senza addormentarsi dalla noia! In effetti, noterai che sono passato alla versione esplicita IsXYZColor c ~ True per questo codice; L'ho fatto perché perché lo standard per i quattro sinonimi in più è diventato molto più ovvio e fastidioso con queste definizioni più brevi!

---

Tuttavia, andiamo nella direzione opposta e rendere questo codice più brutto. Perché? Bene, GHC 7.4 (che è, ahimè, quello che ho ancora sulla mia macchina) non supporta le famiglie di tipi con tipo di risultato non-*. Cosa possiamo fare invece? Possiamo usare classi di tipi e dipendenze funzionali per fingere. L'idea è che al posto di IsBananaColor :: Color -> Bool, abbiamo una classe di tipo IsBananaColor :: Color -> Bool -> Constraint e aggiungiamo una dipendenza funzionale dal colore al booleano. Quindi IsBananaColor c b è soddisfacente se e solo se IsBananaColor c ~ b nella versione più bella; perché Color è chiuso e abbiamo una dipendenza funzionale da esso, questo ci dà comunque le stesse proprietà, è solo più brutto (anche se per lo più concettualmente così). Senza ulteriori indugi, il codice completo:

{-# LANGUAGE GADTs #-} 
{-# LANGUAGE KindSignatures #-} 
{-# LANGUAGE DataKinds #-} 
{-# LANGUAGE ConstraintKinds #-} 
{-# LANGUAGE FunctionalDependencies #-} 
{-# LANGUAGE FlexibleContexts #-} 

data Color = White | Red | Blue | Yellow | Green | Tawny | Purple | Black 

data Fruit (c :: Color) where 
    Banana :: BananaColor c => Fruit c 
    Apple :: AppleColor c => Fruit c 
    Grape :: GrapeColor c => Fruit c 
    Orange :: OrangeColor c => Fruit c 

class IsBananaColor (c :: Color) (b :: Bool) | c -> b 
instance IsBananaColor Green True 
instance IsBananaColor Yellow True 
instance IsBananaColor Black True 
instance IsBananaColor White False 
instance IsBananaColor Red False 
instance IsBananaColor Blue False 
instance IsBananaColor Tawny False 
instance IsBananaColor Purple False 
type BananaColor c = IsBananaColor c True 

class IsAppleColor (c :: Color) (b :: Bool) | c -> b 
instance IsAppleColor Red True 
instance IsAppleColor Green True 
instance IsAppleColor White False 
instance IsAppleColor Blue False 
instance IsAppleColor Yellow False 
instance IsAppleColor Tawny False 
instance IsAppleColor Purple False 
instance IsAppleColor Black False 
type AppleColor c = IsAppleColor c True 

class IsGrapeColor (c :: Color) (b :: Bool) | c -> b 
instance IsGrapeColor Red True 
instance IsGrapeColor Green True 
instance IsGrapeColor White True 
instance IsGrapeColor Blue False 
instance IsGrapeColor Yellow False 
instance IsGrapeColor Tawny False 
instance IsGrapeColor Purple False 
instance IsGrapeColor Black False 
type GrapeColor c = IsGrapeColor c True 

class IsOrangeColor (c :: Color) (b :: Bool) | c -> b 
instance IsOrangeColor Tawny True 
instance IsOrangeColor White False 
instance IsOrangeColor Red False 
instance IsOrangeColor Blue False 
instance IsOrangeColor Yellow False 
instance IsOrangeColor Green False 
instance IsOrangeColor Purple False 
instance IsOrangeColor Black False 
type OrangeColor c = IsOrangeColor c True 

Answer 2

Di seguito è riportato il mio tentativo di codificare il problema. L'idea principale è quella di rappresentare la frutta come classe tipo e vari tipi di frutta come tipi che implementano questa classe di tipo

data Color = White | Red | Blue | Yellow | Green | Tawny | Purple | Black 

class Fruit a where 
    getColor :: a -> Color 

data Banana where 
    GreenBanana :: Banana 
    YellowBanana :: Banana 
    BlackBanana :: Banana 

instance Fruit Banana where 
    getColor GreenBanana = Green 
    getColor YellowBanana = Yellow 
    getColor BlackBanana = Black 

data Apple where 
    GreenApple :: Apple 
    RedApple :: Apple 

instance Fruit Apple where 
    getColor GreenApple = Green 
    getColor RedApple = Red 

vostre domande ultima riga indica che si desidera qualcosa di tipo [Fruit Green] che significa, ovviamente, che Fruit Green dovrebbe essere un digita dove il verde nel codice sopra è un costruttore di valori. Dobbiamo fare Green come un tipo, qualcosa come illustrato di seguito:

data Red = Red 
data Green = Green 
data Black = Black 

data Fruit c where 
    GreenBanana :: Fruit Green 
    BlackBanana :: Fruit Black 
    RedApple :: Fruit Red 
    GreenApple :: Fruit Green 


greenFruits :: [Fruit Green] 
greenFruits = [GreenBanana, GreenApple]