Conversione di un vincolo di classe arbitrario `C a` in` C a Bool`

Question

Quindi ci sono molti vantaggi nell'avere typeclass nel formato C a Bool. Principalmente perché ti permettono di fare qualsiasi operazione logica tra due vincoli quando il normale C a include solo implicitamente tutto.

Se consideriamo ~ un vincolo di classe, questo può essere fatto in questo modo

class Equal x y b | x y -> b 
instance Equal x x True 
instance False ~ b => Equal x y b 

Ma ciò che rende questo caso particolare è il fatto che mettere x x nella testa dell'istanza equivale a x ~ y => e poi x y nella testa. Questo non è il caso per qualsiasi altro tipo. Quindi, se proviamo a fare qualcosa di simile per una classe C otteniamo qualcosa come

class C' x b | x -> b 
instance C x => C' x True 
instance False ~ Bool => C' x b 

Purtroppo questo non funziona in quanto solo uno di quei casi potrà mai essere ritirati perché non discriminare il tipo x quindi qualsiasi tipo corrisponde a entrambe le teste.

Ho anche letto https://www.haskell.org/haskellwiki/GHC/AdvancedOverlap che di nuovo non si applica a nessuna classe C perché richiede di riscrivere tutte le istanze della classe originale. Idealmente, mi piacerebbe che il mio codice funzionasse con GHC.Exts.Constraint e KindSignatures in modo che C possa essere parametrico.

Così, per una classe come questa

class Match (c :: * -> Constraint) x b | c x -> b 

Come faccio a scrivere le istanze in modo che Match c x True se e solo se c x, Match c x False altrimenti?

Answer 1

Questo è impossibile in Haskell a causa del cosiddetto Open World Assumption. Si afferma che l'insieme di istanze per le classi di caratteri è aperto, il che significa che è possibile creare nuove istanze in qualsiasi momento (al contrario di un mondo chiuso, dove deve esistere un insieme fisso di istanze). Ad esempio, mentre la classe di caratteri Functor è definita nel Preludio, posso ancora creare istanze per essa nel mio codice personale che non è nel Preludio.

Per implementare ciò che hai proposto, il compilatore avrebbe bisogno di un modo per verificare se un tipo T è un'istanza di una classe C. Questo, tuttavia, richiede che il compilatore conosca tutte le possibili istanze di quella classe e che non è possibile a causa dell'ipotesi del mondo aperto (durante la compilazione del Preludio, un compilatore non può ancora sapere che successivamente si fa un'istanza di Functor anche ).

L'unico modo per farlo funzionare è considerare solo le istanze che sono attualmente visibili (perché sono state definite nel modulo corrente o in una delle sue importazioni). Ma ciò comporterebbe un comportamento abbastanza imprevedibile: l'insieme di istanze visibili dipende non solo dalle importazioni del modulo, ma anche dalle importazioni delle importazioni poiché non è possibile nascondere le istanze. Quindi il comportamento del tuo codice dipenderà dai dettagli di implementazione delle tue dipendenze.

Se si desidera un mondo chiuso, è possibile invece utilizzare closed type families, che sono stati introdotti in GHC 7.8. Il loro utilizzo, è possibile scrivere:

type family Equal a b :: Bool where 
    Equal x x = True 
    Equal x y = False