Perché il sistema di tipi rifiuta il mio programma apparentemente valido?

Question

mente questo programma:

class Convert a b where 
    convert :: a -> b 

data A = A deriving Show 
data B = B deriving Show 
data C = C deriving Show 
data D = DA A | DB B | DC C deriving Show 

instance Convert A A where convert A = A 
instance Convert A B where convert A = B 
instance Convert A C where convert A = C 
instance Convert B A where convert B = A 
instance Convert B B where convert B = B 
instance Convert B C where convert B = C 
-- There is no way to convert from C to A 
instance Convert C B where convert C = B 
instance Convert C C where convert C = C 

get (DA x) = convert x 
get (DB x) = convert x 
get (DC x) = convert x 

main = do 
    print (get (DC C) :: B) -- Up to this line, code compiles fine. 
    print (get (DB B) :: A) -- Add this line and it doesn't, regardless of having a way to convert from B to A! 

Ci sono casi per convertire C-B e B-A. Tuttavia, GHC registra tipicamente il primo, ma fallisce per quest'ultimo. Su controllo, sembra che non è in grado di dedurre un tipo abbastanza generico per get:

get :: (Convert A b, Convert B b, Convert C b) => D -> b 

Quello che voglio esprimere è: arrivare :: (Convertire a_contained_by_D b) => D -> b, che sembra impossibile. C'è un modo per implementare e compilare una funzione che fa ciò che il mio get tenta di fare, senza cambiare il resto della configurazione?

Answer 1

Se il programma davvero sembrava valida per voi, allora si sarebbe in grado di scrivere il tipo di get che fa il lavoro che vuoi in Haskell, non in handwave. Lascia che ti aiuti a migliorare il tuo handwave e scoprire il motivo per cui stai chiedendo la luna su un bastone.

Quello che voglio esprimere è: get :: (Convert a_contained_by_D b) => D -> b, che sembra impossibile.

Come indicato, non è esattamente il più preciso di cui avresti bisogno. In effetti, è quello che ti dà Haskell ora, in quel

get :: (Convert A b, Convert B b, Convert C b) => D -> b 

è richiesto alcun a che può essere contenuta da D, uno alla volta, per essere convertibile in quel b. Ed è per questo che ottieni la classica logica sysadmin: non è possibile ottenere D a meno che non tutti possano utilizzare b.

Il problema è che è necessario conoscere lo stato non del tipo che potrebbero essere contenuti nelle qualsiasi vecchio D, ma piuttosto il tipo contenuto nel particolare D che si riceve come ingresso. Destra? Si vuole

print (get (DB B) :: A) -- this to work 
print (get (DC C) :: A) -- this to fail 

ma DB B e DC C sono solo due elementi diversi di D, e per quanto riguarda il sistema di tipo Haskell è interessato, all'interno di ogni tipo tutto diverso è lo stesso. Se si desidera discriminare tra gli elementi di D, allora è necessario un tipo -pendent D. Ecco come lo scriverei in handwave.

DInner :: D -> * 
DInner (DA a) = A 
DInner (DB b) = B 
DInner (DC c) = C 

get :: forall x. pi (d :: D) -> (Convert (DInner d) x) => x 
get (DA x) = convert x 
get (DB x) = convert x 
get (DC x) = convert x 

dove pi è la forma vincolante per i dati che vengono trasmessi durante l'esecuzione (a differenza forall) ma su quali tipi possono dipendere (a differenza ->). Ora il vincolo non sta parlando di arbitrari D s ma lo stesso d :: D nella tua mano, e il vincolo può calcolare esattamente ciò che è necessario ispezionando il suo DInner.

Non c'è niente che si possa dire che lo farà andare via ma il mio pi.

Purtroppo, mentre pi sta rapidamente scendendo dal cielo, non è ancora atterrato. Tuttavia, a differenza della luna, può essere raggiunto con un bastone. Senza dubbio ti lamenterai che sto cambiando il setup, ma in realtà sto solo traducendo il tuo programma da Haskell tra il 2017 e Haskell nel 2015. Lo farai get, un giorno, con il tipo che ho subito.

Non c'è nulla che tu possa dire, ma puoi cantare.

Passo 1. Accendi DataKinds e KindSignatures e crea i singleton per i tuoi tipi (o fai in modo che Richard Eisenberg lo faccia per te).

data A = A deriving Show 
data Aey :: A -> * where -- think of "-ey" as an adjectival suffix 
    Aey :: Aey 'A   -- as in "tomatoey" 

data B = B deriving Show 
data Bey :: B -> * where 
    Bey :: Bey 'B 

data C = C deriving Show 
data Cey :: C -> * where 
    Cey :: Cey 'C 

data D = DA A | DB B | DC C deriving Show 
data Dey :: D -> * where 
    DAey :: Aey a -> Dey (DA a) 
    DBey :: Bey b -> Dey (DB b) 
    DCey :: Cey c -> Dey (DC c) 

L'idea è (i) che tipi di dati diventano i tipi, e (ii) che single caratterizzano il tipo di dati di livello che hanno una presentazione fase di esecuzione. Quindi il livello di tipo DA a esiste in fase di esecuzione fornito da a, ecc.

Passaggio 2. Indovina chi viene a DInner. Attiva TypeFamilies.

type family DInner (d :: D) :: * where 
    DInner (DA a) = A 
    DInner (DB b) = B 
    DInner (DC c) = C 

Fase 3. si ottiene qualche RankNTypes, e ora è possibile scrivere

get :: forall x. forall d. Dey d -> (Convert (DInner d) x) => x 
--    ^^^^^^^^^^^^^^^^^^ 
-- this is a plausible fake of pi (d :: D) -> 

Fase 4. Prova a scrivere get e avvitare. Dobbiamo confrontare la prova del tempo di esecuzione che il livello di tipo d sia rappresentabile. Ne abbiamo bisogno per ottenere il livello di tipo d specializzato nel calcolo di DInner. Se avessimo il valore corretto pi, potremmo corrispondere su un valore D che funge da doppio servizio, ma per ora, corrisponde invece a Dey d.

get (DAey x) = convert x -- have x :: Aey a, need x :: A 
get (DBey x) = convert x -- and so on 
get (DCey x) = convert x -- and so forth 

irritante che i nostri x es sono ora single, in cui, a convert, abbiamo bisogno dei dati sottostanti. Abbiamo bisogno di più dell'apparato singleton.

Passaggio 5. Introdurre e creare un'istanza della classe singleton, in modo da "abbassare" i valori di livello di testo (purché conosciamo i loro rappresentanti di runtime). Anche in questo caso, la biblioteca di Richard Eisenberg singletons può Template-Haskell il boilerplate fuori da questo, ma vediamo cosa sta succedendo

class Sing (s :: k -> *) where -- s is the singleton family for some k 
    type Sung s :: *    -- Sung s is the type-level version of k 
    sung :: s x -> Sung s   -- sung is the demotion function 

instance Sing Aey where 
    type Sung Aey = A 
    sung Aey = A 

instance Sing Bey where 
    type Sung Bey = B 
    sung Bey = B 

instance Sing Cey where 
    type Sung Cey = C 
    sung Cey = C 

instance Sing Dey where 
    type Sung Dey = D 
    sung (DAey aey) = DA (sung aey) 
    sung (DBey bey) = DB (sung bey) 
    sung (DCey cey) = DC (sung cey) 

Fase 6. farlo.

get :: forall x. forall d. Dey d -> (Convert (DInner d) x) => x 
get (DAey x) = convert (sung x) 
get (DBey x) = convert (sung x) 
get (DCey x) = convert (sung x) 

essere certi, quando abbiamo corretto pi, quei DAey s saranno effettive DA s e quelli x s non avranno più bisogno di essere sung. Il mio tipo di handwave per get sarà Haskell e il tuo codice per get andrà bene. Ma nel frattempo

main = do 
    print (get (DCey Cey) :: B) 
    print (get (DBey Bey) :: A) 

typechecks bene. Vale a dire, il tuo programma (più DInner e il tipo corretto per get) sembra essere un dipendente affidabile Haskell, e siamo quasi arrivati.

Answer 2

Perché quel codice funzioni, dovrebbe funzionare con qualsiasi argomento dello stesso tipo. Cioè, se

get (DB B) :: A 

opere poi

get anyValueOfTypeD :: A 

deve lavorare, compreso

get (DC C) :: A 

che non può funzionare a causa di un'istanza mancanti da C ad A.

La prima riga

get anyValueOfTypeD :: B 

opere perché noi abbiamo tutti e tre i casi per convertire A, B, C a B.

Io non credo che ci sia alcuna soluzione che permette di lasciare il tipo D così com'è. Se invece puoi modificarlo, puoi utilizzare ad es.

data D a = DA a | DB a | DC a 

(presente che è molto diverso da quello originale), o anche il GADT

data D x where 
    DA :: A -> D A 
    DB :: B -> D B 
    DC :: C -> D C